Вычислить Вороного вокруг многоугольника

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

Позвольте мне привести пример:

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

Кто-нибудь знает, как подойти к этой проблеме? Есть ли какой-то алгоритм, который уже делает это или приближается к тому, чего я пытаюсь достичь?

Большое вам спасибо за любой вход!

Ответ 1

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

Посмотрите на пакет Triangle здесь, в качестве ссылки для этого типа подхода. По моему опыту это быстрая и надежная библиотека, хотя она написана в c не java.

Я не уверен, что на этом этапе я понимаю, как точки (центры Вороного) генерируются на вашей диаграмме. Если вы действительно хотите генерировать сетку в многоугольном домене, тогда могут быть другие подходы к рассмотрению, хотя пакет Triangle поддерживает (соответствует) генерация сетки уточнения Delaunay.

EDIT: похоже, вы также можете напрямую составить диаграмму Voronoi для общих сегментов линии, посмотрите библиотеку VRONI, здесь. Обращаясь к вашему комментарию - я не уверен, что вы всегда можете рассчитывать на единую диаграмму Вороного, которая также соответствует общей полигональной границе. Я ожидал бы, что форма полигональной границы наложит максимальную размерность на граничные ячейки Вороного.

Надеюсь, что это поможет.

Ответ 2

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

Что вы хотите сделать, так это убедиться, что вы начинаете с содержащего многоугольника (независимо от того, сгенерирован ли он вами или из другого источника) с ребрами одинаковой длины; фактор дисперсии сделает это более естественным. Вероятно, я бы выбрал 10-20%.

Теперь, когда у вас есть ваш полигон, ограниченный сегментами строк примерно равной длины, у вас есть основа, с которой можно начать генерировать диаграмму Вороного. Для каждого края вашего контейнера:

Определите нормальный край (строка perp, выступающая внутрь от центра этого сегмента).
Используйте край, как скользящую шкалу, на которой размещается новый центр Voronoi node. Расстояние от самого края будет определяться тем, что вы хотите, чтобы ваш средний диаметр "Вороного" был, если все они были взяты за круги. В вашем примере, который выглядит, может быть, 30 пикселей (или что бы ни было эквивалентно в ваших мировых единицах). Опять же, вы должны применить к этому коэффициент дисперсии, чтобы не каждый центр ячейки находился на равном расстоянии от края источника.
Создайте ячейку Voronoi для вашего недавно размещенного центра.
Сохраните исходную точку ячейки Voronoi в списке.

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

Вам может быть интересно, для чего нужен список. Ну, очевидно, что вы еще не закончили, вы создали только часть общей цели, которую вы хотите использовать в Вороном. Как только вы создали эти "граничные" ячейки вашего вогнутого пространства, вы не хотите, чтобы новые ячейки были сгенерированы ближе к границе, чем пограничные ячейки уже, вы только хотите их внутри этой области. Поддерживая список точек источника граничных ячеек, вы можете обеспечить, чтобы все остальные точки, которые вы создаете, были внутри этой области. Это немного напоминает взятие внутренней суммы Минковского, чтобы обеспечить буферную зону. Теперь вы можете рандомизировать остальную часть своих ячеек в этом производном вогнутом пространстве до завершения.

(Caveat emptor: вам нужно быть осторожным с этим предыдущим шагом. Если какие-либо области прохода слишком узкие, границы этого производного пространства будут перекрываться, у вас будет непростой многоугольник, и вы можете Решение заключается в том, чтобы обеспечить максимальную дистанцию размещения от краев не более половины минимальной ширины прохода... или использовать некоторые другие геометрические средства, включая суммирование Минковского как одна из возможностей, гарантировать, что вы не закончите с вырожденным производным полигоном. Вполне возможно, что вы закончите мультиполигон, то есть фрагменты.)

Я еще не применял этот метод, но, несмотря на то, что, конечно, будут ошибки, чтобы работать, я думаю, что общая идея поможет вам начать работу в правильном направлении.

Ответ 3

Ищите бумагу под названием:

" Эффективное вычисление непрерывных скелетов" Kirkpatrick, David G, написанное в 1979 году.

Здесь реферат:

Предложен алгоритм O (n lgn) для построения скелетов произвольных n-строчных многоугольных фигур. Этот алгоритм основан на O (n lgn) для построения обобщенного Вороного диаграмм (наше обобщение заменяет наборы точек наборами строк сегменты, ограниченные пересечением только в конечных точках). Обобщенные Алгоритм диаграммы Вороного использует алгоритм линейного времени для слияние двух произвольных (стандартных) диаграмм Вороного.

"Наборы сегментов линии ограничены, чтобы пересекаться только в конечных точках" - это вогнутый многоугольник, который вы описываете.