Операция на полигоне — как отсортировать найденные вершины
У меня есть два вогнутых многоугольника на входе, представленные в виде двух векторов точек. Я хочу сделать над ним многоугольную операцию — объединение, пересечение и различие. Я нашел точки пересечения между этими полигонами и вставил их в нужное место в каждом полигоне. Затем я даю информацию о своей позиции (Внутренняя — она находится внутри другого многоугольника, Внешняя — вне другого многоугольника, Точка пересечения, где пересекаются два ребра многоугольников) каждой вершине. Теперь я знаю, какие точки создают объединение этих многоугольников (Внешний и Пересечение) и т. Д., Но мне нужно знать, как отсортировать их в правильном порядке. В случае операции пересечения мне нужно разделить эти отсортированные точки на правильное количество наборов, потому что результатом пересечения может быть более одного многоугольника.
Я использую C ++, но мне не обязательно код, мне нужно только, как отсортировать эти конечные точки многоугольника. И я не хочу использовать какую-либо библиотеку для этих операций, потому что у меня уже есть свои собственные функции и я хочу их использовать.
Я посмотрел на этот вопрос Как пересекаются два полигона? а также некоторые другие, но ни один из них не решает окончательную сортировку точек.
Я также читал эту статью http://www.gvu.gatech.edu/~jarek/graphics/papers/04PolygonBooleansMargalit.pdf , но я, вероятно, не понимаю.
Любая помощь будет оценена.
Решение
Если вы будете следовать всем моим рекомендациям из моих комментариев:
- Различают точки пересечения и точки соприкосновения
- Сохраняйте связь между двумя эквивалентами точек пересечения в двух многоугольниках
Решение для союз будет:
- Рассмотрим только внешние, соприкасающиеся и точки пересечения
- Убедитесь, что точки в двух многоугольниках упорядочены в разные направление (один из наборов по часовой стрелке, другой — против часовой стрелки)
- Начните со случайной точки в любом из двух многоугольников.
- Для каждой вершины любого из двух полигонов сохраните, если вы посетили ее
- Каждый раз, когда вы сталкиваетесь с точкой пересечения, продолжайте перемещаться от следующей к следующей точке в другом многоугольнике после эквивалента точки пересечения.
- Если вы вернетесь к точке, с которой вы начали, это закроет один из компонентов соединения двух полигонов. Если не все вершины были пройдены, повторите все это из любой невидимой вершины.
- В конце рассчитайте площадь всех найденных полигонов. Самым крупным по площади будет настоящий союз. Остальные будут дырами в союзе.
Решение для присоединиться будет:
- Рассмотрим только внутренние и точки пересечения
- Убедитесь, что точки в двух многоугольниках упорядочены в тот же самый направление
- Начните со случайной точки в любом из двух многоугольников.
- Для каждой вершины любого из двух полигонов сохраните, если вы посетили ее
- Каждый раз, когда вы сталкиваетесь с точкой пересечения, продолжайте перемещаться от следующей к следующей точке в другом многоугольнике после эквивалента точки пересечения.
- Если вы вернетесь к точке, с которой вы начали, это закроет один из компонентов соединения двух полигонов. Если не все вершины были пройдены, повторите все это из любой невидимой вершины.
РЕДАКТИРОВАТЬКак я уже упоминал, у меня есть чувство, что мой подход к ориентации полигонов нуждается в пересмотре. Тем не менее, при поиске в Интернете я нашел описание алгоритма, который может сделать работу за вас: Алгоритм отсечения Ватти
EDIT2 Еще одна статья описывающий такой алгоритм отсечения.
Другие решения
Других решений пока нет …