Сортировка вершин клеточных вершин для вычисления многоугольника
В настоящее время я пытаюсь получить отсеченные ячейки от пересечения полигон-Вороной.
Вот что у меня так далеко:
У меня есть многоугольник, и я вычислил несколько точек в нем, чтобы вычислить диаграмму Вороного, а красные линии на рисунке ниже - это ребра Вороного. Затем я использовал алгоритм, чтобы получить угловые точки из каждой ячейки, и теперь мне нужно получить углы в правильном направлении (по часовой стрелке), чтобы сгенерировать многоугольник ячейки.
Найдены углы для одной ячейки
Сначала я использовал этот метод:
private List<Vector> sortClockwise(List<Vector> points)
{
points = points.OrderBy(x => Math.Atan2(x.X, x.Y)).ToList();
return points;
}
но в некоторых специальных вогнутых многоугольниках это не работает, и правильный порядок смешивается.
У кого-нибудь есть предложение или намек, как это можно сделать самым простым способом? Учтите, что точки многоугольника уже находятся в правильном порядке, а углы вороноя перепутаны и их нужно отсортировать по точкам многоугольника.
Моя идея:
Найти первую точку многоугольника в углах ячейкиидите вдоль направления многоугольника и посмотрите, находится ли точка вороной вершины на этой линии.если да: получить конечную точку найденного ребра вороного и найти общие ребра вороного.если найдены общие ребра, всегда выбирайте самый правильныйделай, пока не достигнешь первой точкиЭто единственный способ сделать это?
РЕДАКТИРОВАТЬ - ОБНОВИТЬ
Хорошо, теперь у меня есть половина ответа.
Как я уже сказал, у меня есть все вершины, которые принадлежат одной из ячеек вороноя, но порядок все еще испорчен, поэтому я подумал, что могу отсортировать их по углу относительно центроида следующим образом:
private List<Vector> sortClockwiseBySentroid(List<Vector> points, Vector center)
{
points = points.OrderBy(x => Math.Atan2(x.X - center.X, x.Y - center.Y)).ToList();
return points;
}
Но это не всегда работает. Вот примеры, когда это работает, а когда нет. Проблема в том, что на вогнутых краях угол от центорида к углу иногда меньше того, который мне действительно нужен. Любое предложение о том, как это исправить?
Здесь работает
Здесь не работает ...