Определение пересечения полигона и включения
У меня есть ряд простого (никакие дыры, никакие самопересечения) полигоны, и я должен проверить, что они не пересекают друг друга (можно полностью содержаться в другом; это хорошо). Я могу проверить это просто проверка на вершину внутреннего из одного полигона по сравнению с другими полигонами.
Я также должен определить дерево вместимости, которое является набором отношений, которые говорят, какой полигон содержит любой данный полигон. Так как никакой полигон не может пересечь никакого другого, затем любой содержавший полигон имеет уникальный контейнер; "следующий больший". Другими словами, если A содержит B, содержит C, то A является родителем B, и B является родителем C, и мы не рассматриваем родителя C.
Вопрос: Как я эффективно определяю отношения включения и проверяю неперекрестный критерий? Я спрашиваю это как один вопрос, потому что, возможно, объединенный алгоритм более эффективен, чем решение каждой проблемы отдельно. Алгоритм должен взять в качестве входа список полигонов, данных списком их вершин. Это должно произвести булевскую переменную B указание, если ни один из полигонов не пересекает никакой другой полигон, и также если B = верный, список пар (P, C), где полигон P является родителем ребенка C.
Это не домашняя работа. Это для проекта хобби, я продолжаю работать.
4 ответа
Во-первых, ваш алгоритм проверки сдерживания не выполняет правильную проверку пересечения. Представьте себе два таких прямоугольника:
+--+
+--+--+--+
| | | |
+--+--+--+
+--+
Вершины будут в точках (1, 2) (1,3) (4,2) (4,3) и (2,1) (3,1) (2,4) ( 3,4) - ни одна вершина не лежит внутри многоугольника, но на самом деле многоугольники пересекаются.
Чтобы проверить наличие такого пересечения, необходимо определить, пересекаются ли ребра полигонов. Для ваших целей, если края пересекаются, но один многоугольник не содержится внутри другого, вы знаете, что они перекрываются недопустимым образом.
Что касается определения дерева сдерживания, один из способов сделать это - отсортировать полигоны от наименьшего к наибольшему по площади. При условии, что многоугольники не перекрываются без включения, тогда любой родительский многоугольник в дереве будет первым содержащим многоугольником, идущим после него в списке.
Edit: Да, также, я советую написать быструю процедуру перекрытия ограничивающего прямоугольника или ограничивающего круга и использовать его, чтобы избежать необходимости выполнять все тесты пересечения линий и удержания вершин.Если и этого недостаточно, вы, вероятно, захотите построить дерево четырехугольников или BSP; это немного усложнит ситуацию, но также полностью избавит от многих проверок пересечений.
Для проверки пересечений вы можете использовать мою бесплатную библиотеку клиперов: http://sourceforge.net/projects/polyclipping/ .
Чтобы проверить герметичность, сначала исключите перекрестки, как указано выше. Затем снова используйте Clipper, добавляя все полигоны - Clipper.AddPolygon (). Затем выполните операцию объединения (логическое ИЛИ) над полигонами - Clipper.Execute (ctUnion, solution). Если свойство Clipper.ForceAlternateOrientation истинно, Clipper вернет в решении внешние многоугольники с ориентацией по часовой стрелке и содержащие многоугольники (отверстия) с ориентацией против часовой стрелки. Тогда это должно быть простым вопросом проверки ориентации многоугольника и применения PointInPolygon из одной вершины в многоугольнике против часовой стрелки к другим многоугольникам по часовой стрелке.
Определить, пересекается ли какой-либо из многоугольников, можно за O(n*log(n)), применив алгоритм Шамоса-Хоуи. В зависимости от того, что возвращает алгоритм Шамоса-Хоуи, многоугольник Pi содержит многоугольник Pj, если любая вершина из Pj находится внутри Pi , что делается за O(n) для двух многоугольников.