Комментарии 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
.
Адаптивное разбиение кривых Безье 2-го и 3-го порядка