Как создать дуги на граничных точках ворона?

Question

Привет, братья по ИТ? Я совершенно новый в 2D-программировании.

Я пишу какое-то 2D-графическое программное обеспечение. И в моем проекте я использовал алгоритм Вороного. И результат правильный, как я ожидал (рис. 1). Затем я хочу добавить некоторую функцию в граничные точки, как (Рис. 2). Поэтому я думаю, что мне нужно реализовать вогнутый корпус на граничных точках, а затем создать на нем дуги.

Pic 1.

Но мой вогнутый корпус не работает правильно из-за параметра вогнутости. Что является лучшим способом, и лучшим алгоритмом для преобразования моего результата программного обеспечения в Pic 2.

Рис 2.

Answer 1

Вы можете создать аба/б растрового изображение с вогнутым корпусом и сравнить его с любой точкой Вороного диаграмма. Я использовал php-функцию imagefilledpolygon в моем графике контура php-реализации: https://cntm.codeplex.com/.

Вы также можете попробовать этот ответ и реконструировать края voronoi на границе, обычно края бесконечности: Colorize Voronoi Diagram.

Answer 2

Вы должны быть в состоянии сделать прогулку вокруг voronoi, ища вершины только с одним смежным краем (не плохая идея, чтобы начать с вершины, которая имеет только один соседний край). Найдите первый, дойдите до следующего, затем соедините края с дугой, повторите, пока ваша спина на первом крае. Алгоритм должен быть довольно эффективным O(N), если voronoi структурирован как граф.

Прогулка:

Гуляют осуществляется угол сортировки края и принимать следующий по часовой стрелке край на тот, который вы начали на.

Например:

Если углы (в градусах) составляют 40, 50, 60, 70, а previus край был в направлении 50, то вы бы следовать за 60 или 40 кромки (в зависимости от того, решили ли вы идти по часовой стрелке или против часовой стрелки), но вы не будете следовать 70 независимо от того, как это ведет внутрь, а не придерживаться снаружи.