Блог

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

Для этой цели я использовал алгоритм триангуляции Делоне — Боуэра Уотсона. Благодаря этому я могу генерировать точки и правильно соединять ребра, включенные в диаграмму Вороного. К сожалению, в моем случае мне нужен список полигонов (каждый из которых содержит список своих ребер).

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

Есть ли какой-нибудь способ сделать это? Или мне следует использовать другой алгоритм для получения списка полигонов Вороного? Я не нашел подходящего решения этой проблемы в Интернете, если оно есть, буду благодарен за ссылку

• Выберите E произвольное ребро
• Добавьте вершины в E в многоугольник
• Выберите точку P немного в стороне от E
• Если точка внутри плоскости
  • Выберите одну вершину выбранного ребра
  • Выберите E2 новое ребро из вершины с наименьшим углом со стороны с точкой P
  • Добавьте вторую вершину в E2 в многоугольник
  • Повторяйте последние два шага, пока не достигнете другой вершины в E
  • Добавьте полигон в решение, если он еще не включен
• Повторите с точкой на другой стороне края
• Повторяйте до тех пор, пока все края не будут обработаны