Сортировка вершин клеточных вершин для вычисления многоугольника
================================================================

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

Вот что у меня так далеко:

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

Найдены углы для одной ячейки![]()

Сначала я использовал этот метод:

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

У кого-нибудь есть предложение или намек, как это можно сделать самым простым способом? Учтите, что точки многоугольника уже находятся в правильном порядке, а углы вороноя перепутаны и их нужно отсортировать по точкам многоугольника.

Моя идея:

Найти первую точку многоугольника в углах ячейкиидите вдоль направления многоугольника и посмотрите, находится ли точка вороной вершины на этой линии.если да: получить конечную точку найденного ребра вороного и найти общие ребра вороного.если найдены общие ребра, всегда выбирайте самый правильныйделай, пока не достигнешь первой точкиЭто единственный способ сделать это?

**РЕДАКТИРОВАТЬ - ОБНОВИТЬ**

Хорошо, теперь у меня есть половина ответа.

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

Но это не всегда работает. Вот примеры, когда это работает, а когда нет. Проблема в том, что на вогнутых краях угол от центорида к углу иногда меньше того, который мне действительно нужен. Любое предложение о том, как это исправить?

**Здесь работает** ![]()

**Здесь не работает ...** ![]()

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