Алгоритм векторного контура

считайте, что красная линия задана как последовательность точек

введите здесь описание изображения

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

Какой алгоритм я могу использовать для достижения этого?


algorithm vector-graphics
person Mat    schedule 20.03.2011    source источник
comment
Каковы критерии внешней формы?   -  person Apalala    schedule 21.03.2011
comment
это должна быть четкая линия (ни одна точка контура не должна лежать где-то на черной области на картинке, а только на ее границе)   -  person Mat    schedule 21.03.2011
comment
@Mat - я думаю, вопрос @Apalala заключался в том, какова связь между красной линией и черной рамкой? Не зная, как они связаны, невозможно определить алгоритм для генерации одного из другого.   -  person Ted Hopp    schedule 21.03.2011
comment
Ах я вижу. черная рамка поддерживает постоянное минимальное расстояние до красной линии. и он сохраняет еще одно минимальное расстояние до любого другого черного контура. ограничение расстояния до других черных контуров доминирует над ограничением красной линии   -  person Mat    schedule 21.03.2011
comment
Что касается правила черного-черного, минимальное расстояние, очевидно, не полностью описывает то, что вы имеете в виду (почему оно не применимо, например, к внутреннему верхнему углу вашей фигуры? А как насчет соседних точек - они, скорее всего, упасть ниже минимального расстояния?). Не могли бы вы более точно определить правило черного-черного?   -  person wnrph    schedule 21.03.2011
comment
хорошо - простое описание будет таким: черная область - это толстая версия красной линии диаметра «ширина», и любая прямая линия, перпендикулярная касательной красной линии, не должна пересекать черную область длиннее, чем «ширина». предыстория: я хочу создать «беговую дорожку» из заданного маршрута, и если этот маршрут где-то приближается к самому себе, между ними должна быть стена. И все это должно быть чистой векторной формой.   -  person Mat    schedule 21.03.2011
comment
Это для чего-то вроде обработки гонок?   -  person daoudc    schedule 31.03.2011

Ответы (1)


arrow_upward
2
arrow_downward

Вам понадобятся два типа алгоритмов компенсации:

  1. Сместите кривую в обоих направлениях, чтобы создать трек
  2. Сместите замкнутую кривую внутрь, чтобы получить один или несколько замкнутых полигонов меньшего размера.

Пусть r будет расстоянием до красной линии, а b желаемой толщиной стены между черными линиями/дорожками.

  • Сместите красную линию на r, используя алгоритм 1. Это может привести к тому, что дорожка будет перекрываться, т. е. иметь области, похожие на капли.
  • Сместите красную линию внутрь, используя алгоритм 2. Используйте бинарный поиск, чтобы найти расстояние d, на котором фигура разделится на две части или исчезнет. Если d > b, то сместите внутрь на d - b, чтобы получить вторую площадь. В противном случае алгоритм не работает.
  • Вычесть вторую площадь из первой.
person daoudc    schedule 31.03.2011