У меня есть 2 полигона. Я знаю координаты вершин обоих многоугольников. Какой лучший способ проверить, находится ли один полностью внутри другого? Например, алгоритм должен распознавать только черную трапецию, указанную ниже:
collision-detection
vector
geometry
user960567
источник
источник
Ответы:
Существует множество исходных фрагментов для метода, который выполняет тест для « точки внутри многоугольника ». Принцип исходит из теоремы Джордана о кривой для многоугольников ( http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Octavian/compgeom.html ).
Наивным способом было бы: имея этот метод, вызвать его
PointInsidePolygon(Point p, Polygon poly)
:Теоретически, он не должен пропустить ни одного сценария для ваших полигонов, но это не оптимальное решение.
Замечания по делу "Edge"
PointInsidePolygon(..)
должен вернуть true, если точка находится на границе многоугольника (либо лежит на ребре, либо является вершиной)EdgesIntersect(..)
должен вернуть false, еслиinnerEdge
это подмножество (в геометрическом отношении)outerEdge
. В этом случае ребра, очевидно, пересекаются, но для целей алгоритма нам нужно указать, что пересечение не нарушает семантику заisInside
переменнойГенерал Ремакрс :
без проверки пересечения ребер и ребер, как указано в комментариях, подход может возвращать ложные срабатывания для некоторых вогнутых многоугольников (например, V-образного квадрата и прямоугольника - прямоугольник может иметь все свои вершины внутри V-формы, но пересекать его таким образом имея по крайней мере некоторые области снаружи).
после проверки, что по крайней мере одна из вершин внутреннего многоугольника находится внутри внешнего, и если нет пересекающихся ребер, это означает, что искомое условие выполнено.
источник
Попробуйте сделать пересечение линии с каждой красной линией. В псевдокоде:
Однако, как вы можете видеть, это решение будет работать медленнее, если вы добавите больше полигонов для проверки. Другое решение может быть:
Это решение очень быстрое, но оно зависит от вашей реализации (и того, что вы хотите сделать с результатом вашей проверки), какое решение лучше всего подходит для вас.
источник