Pull to refresh

Comments 10

Было бы интересно посмотреть, как этот изящный алгоритм работает в тех самых сложных случаях

Попробуйте на желаемых кривых. Времени накидать полноценную программу не было.
Пример кода
from math import sqrt


def b3(x0, y0, x1, y1, x2, y2, x3, y3, d):
    px = (x3 - x0) / 3
    py = (y3 - y0) / 3
    mx1 = x1 - x0 - px
    my1 = y1 - y0 - py
    mx2 = x2 - x3 + px
    my2 = y2 - y3 + py
    d1 = sqrt(mx1 ** 2 + my1 ** 2)
    d2 = sqrt(mx2 ** 2 + my2 ** 2)
    if d1 < d and d2 < d:
        print(f' {x3} {y3}', end='')
    else:
        x01 = (x0 + x1) / 2
        y01 = (y0 + y1) / 2
        x12 = (x1 + x2) / 2
        y12 = (y1 + y2) / 2
        x23 = (x2 + x3) / 2
        y23 = (y2 + y3) / 2
        x012 = (x01 + x12) / 2
        y012 = (y01 + y12) / 2
        x123 = (x12 + x23) / 2
        y123 = (y12 + y23) / 2
        x0123 = (x012 + x123) / 2
        y0123 = (y012 + y123) / 2
        b3(x0, y0, x01, y01, x012, y012, x0123, y0123, d)
        b3(x0123, y0123, x123, y123, x23, y23, x3, y3, d)


def b3svg(x0, y0, x1, y1, x2, y2, x3, y3, d):
    print('<svg version="1.1" xmlns="http://www.w3.org/2000/svg" width="500" height="500">')
    print('<rect x="0" y="0" width="500" height="500" fill="white" stroke="none" />')
    print(f'<path d="M {x0} {y0} L', end='')
    b3(x0, y0, x1, y1, x2, y2, x3, y3, d)
    print('" fill="none" stroke="black" stroke-width="1" />')
    print('</svg>')


if __name__ == '__main__':
    # Сюда вписать координаты нужной кривой и перенаправить вывод в файл
    b3svg(50, 250, 300, 50, 200, 450, 450, 250, 0.1)


Прошу заметить, цели мои и автора приведённой мной статьи несколько различаются. Автор работал над растеризацией, поэтому проверял плавность при помощи эквидистанты. Я же ориентировался на звук станка и моей целью было нахождение простого метода аппроксимации траектории движения инструмента.
Вы неверно уловили суть статьи. Деление кривой действительно осуществляется по алгоритму де Кастельжо. Алгоритм показывает, как делить кривую, а вот когда остановить деление — есть в моей статье. У меня написано о том, что мерять, чтобы понять, стоит ли дальше делить, или уже нарисовать прямой отрезок. Также мой метод использует всего одну метрику, которая например работает без принудительного первого деления пополам, как это сделано у автора приведённой мною статьи. Мой метод проще, дешевле по вычислениям и собран в одну короткую функцию.

А видели статью Flattening quadratic Béziers, где автор предложил способ не рекурсивного разбиения квадратичных кривых, а аналитический метод?

Не видел. Пробежался по ней но ничего не понял. Не столько из-за того, что английский я знаю не идеально, сколько из-за сложности идеи по сравнению с моей. Мой простой адаптивный метод уже достаточно сильно оптимизирует деление кривой. Дальнейшие доработки ощутимо усложняют деление, не давая сопоставимой усилиям отдачи. Кривая стала немного плавней, это видно. В этом подход работает лучше. Но и плавность простого метода тоже хорошая.


Мне не очень нравится другой подход. Например было 32 точки — стало 26 точек. При этом эти 26 точек стоили нам большего процессорного времени. Мы сэкономили дисковое пространство, но потратили больше времени. Что ценнее, думаю, и так понятно. По крайней мере для меня в моих задачах.

Перед написанием статьи я зашёл на страницу и обнаружил, что ссылки на программу и её исходный код мёртвые, поэтому теперь можно только почитать.

"Программа" — часть семплов знаковой в узких кругах библиотеки рендера шрифтов с субпиксельной точностью Antigrain Geometry, AGG. Очень качественная как с точки зрения реализации различных алгоритмов растеризации, так и с точки зрения кода (мощное обощенное программирование с поправкой на C++ 98). После смерти автора (Максим Шеманарев, McSeem2 на форумах рсдн-а) библиотека долго висела в бесхозном состоянии на исходном домене, пока добрые люди (спасибо им!) не перенесли на sourceforge:
http://agg.sourceforge.net/antigrain.com/index.html
.

Ссылки в оригинальной статье (раз, два, три) чуть ниже подзаголовка «Демо-приложение и некоторые замечания» мёртвые. Я не искал так подробно, что там с AGG. Оказывается Максим умер… Когда я читал статью в первый раз, ссылки были рабочие и я успел поиграться с примерами. Действительно, теперь всё лежит на SourceForge.
Добавил ссылку в статью.
Спасибо Вам за ссылку, добрый человек!
Only those users with full accounts are able to leave comments. Log in, please.