Определите, содержит ли один многоугольник другой
(В моих целях «многоугольники» не включают самопересекающиеся многоугольники или многоугольники с отверстиями - только простые (вогнутые или выпуклые) многоугольники.)
Я нашел различные предложения по этой проблеме, которые в основном основаны на следующем:
If there are no intersections between the edges of Polygon1 and the edges of Polygon2, and at least one vertex of Polygon2 is "inside" Polygon1, then Polygon1 contains Polygon2.
(например, см. принятый ответ здесь)
Однако дьявол кроется в деталях:
Включает ли "внутри" Polygon1 "край" Polygon1? Ясно это должен, иначе на диаграмме F (см. изображение, приведенное ниже) Polygon2 (красный) не будет иметь вершина "внутри" Polygon1 (синий) и поэтому не прошла вышеуказанный тест, когда это должно пройти.
Есть ли в "пересечении" двух ребер точку на конце одного? ребер (т.е. вершины)? Если «да», то диаграммы A и E ниже имеют пересечения и поэтому не пройдут тест, когда должны пройти. Но если «нет», то диаграммы B, C и D не пересекаются и поэтому проходят тест, когда они должны потерпеть неудачу.
(NB диаграммы A, B и C имеют вершины Polygon2 на ребрах Polygon1, диаграммы D и E наоборот.)
Я не могу придумать условие для проверки, которое правильно различает эти различные случаи. Буду признателен за любые указатели?
@ 3Dave: очень плохой совет. 1) Триангулировать многоугольник не так просто. 2) Это увеличит сложность до O (N.M) во всех случаях. 3) Это приводит к неразрывному беспорядку: после нахождения всех пересечений треугольника с треугольниками, образующими другой многоугольник, вам нужно проверить, был ли треугольник полностью покрыт.
@YvesDaoust 1) Триангуляция несложная, это хорошо изученная и хорошо задокументированная задача. 2) Увеличивает с чего именно, если у OP на данный момент нет рабочего решения? 3) Не понимаю, что вы подразумеваете под «полностью покрытым».
@ 3Dave: 1) Триангуляция сложна. 2) Увеличение от возможного решения O (N Log N). 3) Вы, кажется, долго не задумывались над проблемой.
@YvesDaoust Вздох. Я уже решал эту проблему раньше и потратил на это довольно много времени. Если вы думаете, что триангуляция сложна, возможно, вы не задумывались над проблемой что.
@ 3Dave: о, я понимаю, вы, наверное, реализовали решение Chazelle. Но продолжайте размышлять о 2) и 3).
Ответы 4
Если мы пытаемся проверить, находится ли многоугольник B внутри многоугольника A:
Как упоминалось в ответе, на который вы ссылались, начните с проверка пересечения линий для каждой пары ребер, по одному от каждого многоугольника. Если какие-либо ребра пересекаются (за исключением вершин, лежащих на ребрах и общих вершинах), B не находится внутри A.
Если вершина V одного многоугольника лежит на ребре другого, рассматривайте это ребро как 2 ребра, а вершину V как новую вершину для этого многоугольника.
Теперь нам осталось подумать только об общих вершинах.
Для каждой общей вершины V:
- Можно сказать, что V имеет ребра EA1 и EA2 (из A) и EB1 и EB2 (из B).
- Получите градиенты всех 4-х краев.
Используйте это, чтобы определить, какие края смежные.
Если EB1 и EB2 не смежны, B не находится внутри A.
Если EB2 лежит на A (то есть EB2 лежит на EA2, т.е. у них одинаковый градиент), мы еще не знаем, находится ли B в A.
В этом случае нам нужно отслеживать, на какой стороне находилась EB1, и перейти к соседней вершине VB (другой вершине EB2) и проверить, находится ли EB3, ребро после EB2, на той же стороне, что и EB1. . Если они по разные стороны, B не находится внутри A.
Если EB3 также находится на A, нам нужно проверить EB4 и так далее, пока мы не найдем тот, которого нет.
Если оба EB1 находятся на EA1, а EB2 - на EA2, нам нужно двигаться в обоих направлениях, чтобы определить, с какой стороны нам нужно быть. Если все ребра B лежат на A, A равно B.
(Примечание: если, например, EB2 лежит на EA1 вместо EA2, вы можете просто переименовать их, чтобы выполнить указанное выше условие)
Все это предполагает, что мы не разрешаем многоугольники, которые пересекаются с самих себя - разрешение этого, вероятно, нарушит это.
Здесь могут быть некоторые нетривиальные детали, но это должно стать хорошей отправной точкой.
Мы можем перемещаться по ребрам в O(|EA| + |EB|) и играть в «catch:», пока текущее ребро одного многоугольника выходит за пределы другого, по крайней мере, в одном измерении, перемещаться по следующему ребру / s другого многоугольника, а затем снова переключаться. Утверждение сдерживания, которое мы можем определить, наблюдая за пересечениями и с какой стороны края находится внутри его многоугольника.
Алгоритм Sweepline (как почти всегда) дает нам наиболее надежное и эффективное решение.
В своей простейшей форме sweepline находит все пересечения отрезков прямой. Расширение его для проверки удержания многоугольника тривиально. Вы просто отслеживаете, какая линия или точка принадлежит каждому многоугольнику. На любом этапе алгоритма пересечение скользящей линии и внутренней части каждого многоугольника представляет собой конечный набор вертикальных сегментов. У вас есть такие кейсы:
- Если есть правильное (то есть не в конечной точке) пересечение ребер на любом этапе, игра окончена.
- В противном случае, если на каждом шаге красный и синий сегменты не пересекаются, то полигоны полностью находятся вне друг друга.
- В противном случае, если на каждом шаге красные сегменты идентичны синим сегментам (т.е. красный набор и синий набор одинаковые), то два многоугольника будут одинаковыми.
- В противном случае, если на каждом шаге каждый красный сегмент полностью находится внутри какого-либо синего сегмента, то красный многоугольник находится внутри синего.
- В противном случае, если на каждом шаге каждый синий сегмент полностью находится внутри некоторого красного сегмента, то синий многоугольник находится внутри красного.
- В противном случае границы полигонов пересекаются.
Это позаботится обо всех крайних случаях. Если вы хотите классифицировать ваши случаи A, E и F как «внутренние», проверьте только пересечение внутренних частей сегментов (т.е. сегменты (0,1) и (1,2) не пересекаются, а (0,1) находится внутри (0,2)). В противном случае просто рассматривайте вышеуказанные случаи как правильные пересечения.
Если на каком-то этапе есть два края, которые коллинеарны и параллельны линии развертки и пересекаются, это может быть немного сложно решить. Однако все граничные случаи могут быть разрешены путем вычисления пересечения гладкой линии и многоугольника не в вершинах (как это нормально для алгоритма гладкой линии), а между вершинами (скажем, в средней точке между текущей вершиной и следующей). Таким образом, когда-либо учитываются только внутренние части многоугольника (не границы).
По сути, алгоритм разбивает наши многоугольники на кучу маленьких трапеций, зажатых между параллельными (скажем, вертикальными) линиями, проведенными через каждую вершину. Очень легко проверить, пересекаются ли эти трапеции, не пересекаются или полностью содержат друг друга. Иллюстрацию можно найти здесь.
Обновлено: уточнены некоторые формулировки. Изменить 2: нашел крайний случай;)
Похоже, у него есть дополнительное преимущество обработки нескольких объектов.
@ גלעדברקן да, это очень мощный алгоритм
Большое спасибо за ответы, особенно @Dukeling и @ n.m.
Я реализовал (на Python) решение sweepline, предложенное @ n.m. и размещаю его здесь на случай, если кто-то еще сочтет его полезным. (Я обнаружил, что это проще кодировать, чем решение Дюклинга.) В моем случае использования я знаю, какой будет содержащий многоугольник (если он есть), поэтому мне не нужно проверять оба способа.
Я протестировал его более чем на двадцати тестовых примерах, включая все те, что показаны на диаграмме выше, и их отражение в y = x. Однако, если кто-то обнаружит какой-либо крайний случай, когда реализация не работает, или какие-либо улучшения эффективности кода, комментарии будут приветствоваться.
Редактировать:
Я удалил код, так как обнаружил ряд случаев, когда он не работал. В конце концов, я выбрал более комплексное решение, которое, учитывая два многоугольника A и B, определяет, содержит ли A B, A находится внутри B, A и B перекрываются, или A и B не пересекаются.
Чтобы ускорить процесс, он начинает с рассмотрения ограничивающих прямоугольников, что исключает некоторые возможности, затем, если ограничивающие прямоугольники равны, он смотрит на области и только затем переходит к алгоритму Sweepline.
Код довольно длинный, поэтому я не включаю его здесь, но если кому-то интересно, вы можете увидеть его как метод positionRelativeTo для PolygonObject в https://github.com/andy31lewis/brySVG. Это было проверено на нескольких сотнях тестовых случаев и кажется довольно надежным.
Вы можете разложить вогнутые многоугольники на набор треугольников (или, возможно, на любой другой выпуклый многоугольник, но с треугольниками легче всего работать). Тогда проверка на пересечение и сдерживание треугольника становится довольно тривиальной.