Помогите найти алгоритм

[screenshot]

Доброго времени суток.
К модераторам: если я написал не в тот форум или нарушил правило "здесь не решают задачи за вас", то удаляйте.

Есть сугубо практическая задача. Нужно с помощью кривых и сплайнов Безье построить общий алгоритм описывающий "стиль облака" вокруг полигона. Такой алгоритм реализован в Adobe Acrobat Pro для создания этого стиля в некоторых видах аннотаций. Алгоритм строит с помощью кривых "облако" вдоль сторон и с помощью сплайнов неполные окружности вокруг вершин(острые углы). Скриншот его работы:



Заранее спасибо.

-- Вт дек 15, 2009 11:45:36 --

Что-то совсем мало я написал. Самые главные вопросы:

1. Как построить с помощью кривых Безье дуги(которые идут по сторонам). Допустим полуокружности я нашел как построить с помощью двух кривых третьего порядка. Но тут дуги, причем точка начала следующей дуги лежит на предыдущей. Как ее расчитывать... Допустим я возьму прямую и найду точку пересечения с кривой(пока не знаю как). Как тогда рассчитать опорные точки для такой дуги?

2. Что делать с вершинами? Понятно что завязываться надо на угол, но как и что не понятно...

[Circiter]

2screenshot

Цитата:

с помощью кривых и сплайнов Безье построить общий алгоритм описывающий "стиль облака" вокруг полигона.

Обходите многоугольник повершинно в определенном напрвлении. В вершине строите окружность фиксированного радиуса. Смещаетесь на некоторое фиксированное расстояние вдоль стороны (вабираемой с учетом направления обхода) многоугольника и строите ещё одну окружность, etc. При построении каждой следующей окружности находите точки пересечения её с предыдущей окружностью решая систему из двух уравнений окружностей и выбираете в качестве граничных (контрольных) точек дуг решения, лежащие вне многоугольника. При "прорисовке" дуг (создании искомого набора кривых) немного увеличиваете длину каждой дуги в определенном направлении.

Примерно так...

[Circiter]

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

Другими словами, выбрав вершину многоугольника нужно немного отступить от неё вдоль прилежащей стороны (её выбор зависит от направления обхода многоугольника), затем необходимо отступить немного вдоль нормали к стороне и построить контрольную точку. Теперь можно снова отступить от этой точки вдоль текущей стороны на тот же шаг и опять построить точку. Этот процесс продолжается пока проекции контрольных точек на сторону будут принадлежать этой стороне.

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

Осталось учесть те дополнительные штрихи-"наплывы", то есть достроить продолжения дуг на небольшой фиксированный угол.

[Circiter]

Э, нет, так дело не пойдет. Эксперимент показывает, что в "узких" углах таки-и-и-е артефакты появляются, что аж страшно становится... Надо что-нибудь ещё придумать...

[covax]

Circiter в сообщении #271961 писал(а):

затем необходимо отступить немного вдоль нормали к стороне

Circiter в сообщении #271996 писал(а):

что в "узких" углах таки-и-и-е артефакты появляются

А если вообще не отступать, т.е. центры прям на линиях брать, как вы первый раз и написали?
Как-то так оно и получается.

[Circiter]

2covax
К сожалению, ваш рисунок увидеть не удалось (http/403).

Цитата:

А если вообще не отступать, т.е. центры прям на линиях брать, как вы первый раз и написали?

Ну эти центры все равно придется так или иначе учитывать, чтобы правильно выбрать ориентацию дуги (т.е., направлять дуги выпуклостью по направлению от многоугольника).

2screenshot
Можно ещё так попробовать.

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

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

На деле, при "запоминании" окружности, сохранять нужно именно координаты центра окружности и координаты новой контрольной точки дуг (i.e., как уже было сказано, точки пересечения запоминаемой окружности с ранее запомненной с учетом наибольшей удаленности от текущей стороны).

Имея такой список пар точек плоскости уже не составляет труда сформировать список самих дуг.

Кстати, не могли бы вы показать, как себя ведет ваш эталонный алгоритм в "узких" углах.