Алогиритм inset/outset (inflate) bezier

[Idalgo]

Приветствую!

Разыскивается алгоритм создания паралельных кривых. Исходные данные - замкнутая кривая Безье, необходимо получить кривую, отстоящую от исходной на заданое расстояние.
В результате должна быть также замкнутая кривая Безье без "петель".

Аналогичный инструмент в иллюстраторе называется inflate, в inkscape - inset

Нужен либо открытый исходник, либо внятный алгоритм построения.
На данный момент гугль ничем не помог
В исходниках inkscape смотрел, но моих знаний по cpp для понимания не хватает.

[Rzer]

http://code.google.com/p/bezier/ пожалуй единственные изыскания в данной области

[silin]

довольно легко разруливается вариант со сплайном Катмулла-Рома http://silin.su/trash/spline/bin/
такая ли параллельность и точность нужна и для чего это уже другой вопрос
и еще с петлями там не всегда хорошо

[Aquahawk]

А кривая безье у вас по опорным точкам задана? Расстояние как мерять будем меж кривыми, по нормали в точке? В какой точке, на первоначальной кривой или на итоговой? Просто масштабировать ключевые точки и получить подобную фигуру меньшего размера вам не подходит?

[Idalgo]

Сообщение от silin

довольно легко разруливается вариант со сплайном Катмулла-Рома http://silin.su/trash/spline/bin/
такая ли параллельность и точность нужна и для чего это уже другой вопрос
и еще с петлями там не всегда хорошо

Интересный вариант, но в моем случае думаю не подойдет.
Расстояние между кривыми неодинаковое даже при выпуклом контуре.
Но спасибо за полезный пример. Можно применить для сглаживания контуров многоугольников.

Добавлено через 14 минут

Сообщение от Aquahawk

А кривая безье у вас по опорным точкам задана? Расстояние как мерять будем меж кривыми, по нормали в точке? В какой точке, на первоначальной кривой или на итоговой? Просто масштабировать ключевые точки и получить подобную фигуру меньшего размера вам не подходит?

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

[silin]

>> Расстояние между кривыми неодинаковое даже при выпуклом контуре.
ага, но это из-за того, что в примере точки для дубля считаются абы как - просто 'расширением' от геометрического центра
если считать, отступая по нормали, то будет ровно http://silin.su/trash/spline/testSpline1.swf
но непонятки с острыми загибами и петлями остаются канеш,
хотя, имо, их все равно легче преодолеть, чем для безьевого варианта

[Aquahawk]

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

Так безье не проходит через свои опорные точки.
В чём проблема взять какие-то точки вашей кривой, найти в них касательные если они не известны и взять нормали, по нормалям отложить требуетмое расстояние и нарисовать такую же кривую по новым точкам.

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

А вам нельзя просто численно пройтись по кривой по точкам и просчитать нормали и посторить аппроксимацию достаточной точности?