Определите, содержит ли один полигон другой

Question

(Для моих целей "многоугольники" не включают самопересекающиеся многоугольники или многоугольники с отверстиями - просто простые (вогнутые или выпуклые) многоугольники.)

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

Если между ребрами Polygon1 и ребрами Polygon2 нет пересечений, и хотя бы одна вершина Polygon2 находится «внутри» Polygon1, то Polygon1 содержит Polygon2.

(например, см. Принятый ответ здесь )

Однако, дьявол кроется в деталях:

• Имеет "внутри "Polygon1 include" на ребре "Polygon1?"Ясно, что это должно произойти, в противном случае на диаграмме F (см. Изображение ниже) Polygon2 (красный) не будет иметь вершины «внутри» Polygon1 (синий) и, таким образом, не пройдет вышеуказанный тест, когда он должен пройти.

• Включает ли «пересечение» двух ребер точку в конце одного ребра (то есть вершину)?Если «да», то диаграммы A и E ниже имеют пересечения и поэтому не проходят тест, когда они должны пройти.Но если «нет», то диаграммы B, C и D не имеют пересечений и поэтому проходят тест, когда они должны потерпеть неудачу.

(NB диаграммы A, B и C имеютвершины Polygon2 на ребрах Polygon1, диаграммы D и E, наоборот.)

Я не могу выработать условие для проверки, которое правильно различает эти различные случаи.Буду благодарен за любые указатели?

Answer 1

Большое спасибо за ответы, особенно @Dukeling и @ nm

. Я реализовал (в Python) решение по разметке, предложенное @nm, и выкладываю его здесь на тот случай, если кто-нибудь еще посчитает его полезным.(Я обнаружил, что один из них легче кодировать, чем решение Dukeling.) В моем случае использования я знаю, какой будет содержащий полигон (если он есть), поэтому мне не нужно тестировать в обоих направлениях.

Я проверил это с более чем двадцатью тестами, включая все те, что на диаграмме выше, и их отражения в y = x.Однако, если кто-нибудь заметит какой-либо крайний случай, когда реализация не работает, или какие-либо улучшения в эффективности кода, комментарии будут приветствоваться.

Редактировать:
У меня естьудалил код, так как я обнаружил ряд случаев, для которых он не работал.В конце я остановился на более всеобъемлющем решении, которое, учитывая, что два многоугольника A и B определяют, содержит ли A B, A находится внутри B, A и B перекрываются, или A и B не пересекаются.

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

Код довольно длинный, поэтомуЯ не включаю его здесь, но если кому-то интересно, вы можете увидеть это как positionRelativeTo метод PolygonObject при https://github.com/andy31lewis/brySVG. Это было протестировано с парой сотен тестовых случаев и кажется довольно надежным.

Answer 2

Мы можем пройти по ребрам в O(|EA| + |EB|) и сыграть «catch:», пока текущий край одного многоугольника выходит за край другого хотя бы в одном измерении, перемещаясь вдоль следующего ребра / сторон другого многоугольника,затем переключитесь снова.Утверждение сдерживания, которое мы можем определить путем мониторинга пересечений и того, какая сторона ребра находится внутри его многоугольника.

Answer 3

Алгоритм разметки (как почти всегда) дает нам наиболее надежное и эффективное решение.

В простейшей форме, разметка находит все пересечения отрезков.Тривиально расширить его, чтобы проверить содержание полигонов.Вы просто отслеживаете, какая линия или точка принадлежит каждому многоугольнику.На любом этапе алгоритма пересечение широкой линии и внутренней части каждого многоугольника представляет собой конечный набор вертикальных сегментов.У вас есть следующие случаи:

1. Если на каком-либо шаге имеется правильное (т.е. не в конечной точке) пересечение ребер, игра окончена.
2. В противном случае, если на каждом шаге красные и синие сегменты не пересекаются, полигоны полностью находятся вне друг друга.
3. В противном случае, если на каждом шаге красные сегменты идентичны синим сегментам (т. Е. Красный набори синий набор совпадают), тогда два многоугольника одинаковы.
4. В противном случае, если на каждом шаге каждый красный сегмент полностью находится внутри какого-то синего сегмента, то красный многоугольник находится внутри синего.
5. В противном случае, если на каждом шаге каждый синий сегмент полностью находится внутри какого-либо красного сегмента, то синий многоугольник находится внутри красного.
6. В противном случае границы многоугольника пересекаются.

Этозаботится обо всех крайних случаях.Если вы хотите классифицировать ваши случаи A, E и F как «внутри», проверьте только пересечение внутренних сегментов (т. Е. Сегменты (0,1) и (1,2) не пересекаются, а (0,1) находится внутри(0,2)).В противном случае, просто рассматривайте вышеприведенные случаи как правильные пересечения.

Если на каком-то этапе есть два ребра , которые являются коллинеарными и параллельными линии развертки, и они пересекаются, это может быть довольно сложнопринимать решение.Однако все краевые случаи могут быть решены путем вычисления пересечения линии-полигона не в вершинах (как это нормально для алгоритма линии разметки), а между вершинами (скажем, в средней точке между текущей и следующей вершинами).Таким образом, когда-либо рассматриваются только внутренние полигоны (не границы).

По сути, алгоритм разбивает наши полигоны на несколько маленьких трапеций, расположенных между параллельными (скажем, вертикальными) линиями, проходящими через каждую вершину.Очень легко проверить, пересекаются ли эти трапеции, или не пересекаются, или полностью содержат друг друга.Иллюстрацию можно найти здесь .

Редактировать: уточнил некоторые формулировки.Редактировать 2: найден крайний случай;)

Answer 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, вы можете просто переименовать их, чтобы выполнить указанное выше условие)

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

Возможно, некоторые- тривиальные подробности здесь, но это должно стать достойной отправной точкой.