Построение контура кривой Безье

← →
kingdom (2005-01-24 10:45) [0]

Привет всем!

Кто-нибудь занимался построение контура к кривой Безье?

Задача такая, дана кривая Безье 2 или 3 порядка, дано расстояние от кривой до контура.
Нужно построить контур из кривых Безье 2 и 3 порядка соответственно с заданной точностью.
Критерий точности можно выбра самому, главное чтобы он был разумным =)
Напомню, что контур это кривая расстояние между которой и исходной кривой константа.
Достаточно вычислить контур с одной стороны от исходной кривой.

Заранее всем спасибо!

← →
REA (2005-01-24 10:51) [1]

Сплайны рисовал, Безье не рисовал...

← →
MBo © (2005-01-24 11:52) [2]

Если имеется в виду не параллельный перенос кривой, а получение кривых, описывающих край "жирной линии", то эта задача не имеет корректного решения, т.е. эти кривые не являются кривым Безье.

Приближение - строим перпендикуляры нужной длины к кривой (с постоянным шагом по t или меняем шаг в зависимости от кривизны кривой), через полученные точки проводим какие-либо кубические сплайны (в зависимости от требуемой гладкости), переводим сплайны в базис полиномов Бернштейна.

← →
MBo © (2005-01-24 12:28) [3]

В дополнение: "плохими местами" будут те, где радиус кривизны кривой меньше офсета. По крайней мере, в точках, где эти величины совпадают, исходную кривую стоит порезать.

← →
REA (2005-01-24 12:57) [4]

А какая если не секрет предметная область?

← →
kingdom (2005-01-24 18:02) [5]

>MBo
Спасибо за ответ!
Не могу найти формулы кривизны для Кривой Безье

>REA
Пишу графическую библиотеку, нужно что-то типа StrokePath сделать

← →
MBo © (2005-01-25 08:05) [6]

>Не могу найти формулы кривизны для Кривой Безье

из дифф. геометрии - кривизна параметрической плоской кривой (величина, обратная радиусу кривизны):

k=1/R = (X"Y"" - Y" X"")/(X"^2+Y"^2)^3/2
(первые и вторые производные по параметру t)

P.S. встречал упоминание о методе аппроксимации Tiller-Hanson - там, кажется, делают примерно так, как я описал, только сплайны не строят, сразу Безье по неким критериям.
Кроме того, глянь www.truetex.com, описание MetaFog.

← →
kingdom (2005-01-25 12:52) [7]

>MBo
Спасибо! Это мне очень поможет =)
Может у тебя есть ссылка на вывод этой формулы, а то у меня другая получалась.

← →
MBo © (2005-01-25 13:08) [8]

>у тебя есть ссылка на вывод этой формулы
Нет.
Примерно отсюда нужно исходить: кривизна по определению есть предел отношения угла поворота касательной к длине дуги, и
для малых углов Fi~Tan(Fi)=dy/dx

← →
MBo © (2005-01-25 13:42) [9]

вот как получается

k=dFi/dl=(ArcTan(Y"/X"))"/Sqrt(dX^2+dY^2)=(Y"/X")"*ArcTan()"/Sqrt(dX^2+dY^2)=(Y""X"-Y"X"")/(X")^2*(1/(1+(Y"/X")^2)/Sqrt( dX^2+dY^2)=(Y""X"-Y"X"")/(dX^2+dY^2)^3/2

← →
kingdom (2005-01-25 14:17) [10]

Я нашел ошибку, производную неправильно взял,
спасибо!

Буду дальше разбираться =)

← →
kingdom (2005-01-25 16:57) [11]

Странная вещь получается...
Если разбить кривую пополам, то кривизна, например, в точке 0.0 для исходной и новой половинки не совпадает, она уменьшается =(

Как это можно объяснить?

← →
MBo © (2005-01-25 17:10) [12]

1. Не понял, какая точка 0.0 имеется в виду
2. Уверен, что кривую правильно разбиваешь?

← →
kingdom (2005-01-25 17:26) [13]

Подели кривую (q) на левую и правую половину (lq, rq)
q(0) = lq(0)
q(1) = rq(1)
кривизна q в точке 0 не равна кривизне lq в точке 0

← →
kingdom (2005-01-25 17:37) [14]

Короче, я тормозить начал под вечер, все нармально =)))

Я попробовал - совпадает. Убедись, что правильно делишь(отрисовкой всех трех кривых) и покажи код вычисления кривизны.

← →
kingdom (2005-01-25 18:19) [16]

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

Тут без проб трудно посоветовать. пробеги по кривой, скажем, в 5-10 точках, оценивай кривизну. участки с большой кривизной еще подели

← →
kingdom (2005-01-25 18:36) [18]

Вот я и пробую ))
Вопрос в том какую метрику выбрать?
Экспериментировал с k(0) - k(1), плохо работает.
Я думаю есть метрика геометрически обоснованная, буду искать.

MBo спасибо, ты мне очень помог!

Можно подойти к этой проблеме с другого конца. Пусть для каждой точки кривой Безье мы постороили круг с центром в этой точке и радиусом, равным той самой константе, задающей расстояние от контура до кривой. Граница фигуры, которую составляют все эти круги, как раз и будет требуемым контуром.

Чтобы построить такую фигуру, нужно выполнить следующие действия:
1. Построить траекторию на основе кривой Безье (BeginPath/PolyBezier/EndPath).
2. Привести внутреннее представление траектории к ломаной, состоящей из отреков прямых (FlattenPath).
3. Получить координаты узлов этой ломаной (GetPath).
4. Пройтись по всем звеньям ломаной и с помощью LineDDA получить координаты всех промежуточных точек.
5. Для каждой из полученных точек создать регион в виде круга заданного радиуса (CreateEllipticRgn) и объединить все эти регионы в один (CombineRgn).
6. Построить контур полученного региона (FrameRgn). Всё, задача решена.

Метод работает медленно (особенно последний шаг), но даёт очень точные результаты для любой кривой.

Пример действий п. 1-4 можно посмотреть на http://www.delphikingdom.com/asp/viewitem.asp?catalogid=881

← →
kingdom (2005-01-27 15:47) [20]

>Григорьев Антон
Спасибо за ответ

Как ты правильно сказал, этот способ медленный и это не совсем то, что мне надо. Мне не надо рисовать контур, мне надо построить контур.

У меня получился такой алгоритм для кривых Безье 2 степени, берем исходную кривую и строим к ней кривую Безье, которая в точках 0 и 1 находится на заданном расстоянии от исходной и имеет такае же производные как у исходной. Такая кривая определяется однозначно. Расстояние между кривыми в точке 0.5 будет больше заданного, поэтому нужно иметь оценочную функцию, которая скажет велико ли отклонение. Если велико, то делим исходную кривую на две части и повторяем действия, иначе для данного участка исходной кривой контур найден.

Вопрос в том, как выглядит эта оценочная функция?

Построение контура кривой Безье Найти похожие ветки