Как проверить принадлежность многоугольника к некоторой области координатной плоскости?

Question

[vampire444]

Пусть на координатной плоскости есть некоторое количество многоугольников. Как я могу проверить, что один или несколько из них принадлежат (или не принадлежат) некоторой заранее известной области.
Более конкретные примеры.

1. Как я могу узнать, что часть многоугольника принадлежит моей области? (красное окно 1)
2. Как я могу узнать, что части нескольких многоугольников находятся внутри моей области? (окно 2)
3. ---//--- , что моей области не принадлежит ни один из многоугольников? (окно 3)
4. ---//--- , что моё окно полностью находится внутри одного или нескольких многоугольников? (окно 4)
5, ---//--- , что моё окно полностью охватывает один или несколько многоугольников и при этом, возможно, захватывает части других многоугольников? (окно 5)

Совсем что-то запутался с этой задачей. В лучшем варианте был благодарен пошаговому алгоритму или алгоритму на каком-нибудь языке программирования или псевдо-языке. Ну или хотя бы просто математическое обоснование как это сделать. За это тоже спасибо скажу :)

Answer 1

[tsarevfs]

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

Получается надо уметь проверять 2 факта:
1 вершина внутри окна -- элементарно, x_min<=x<=x_max && y_min<=y<=y_max
2 сторона многоугольника пересекается со стороной квадрата. Чуть сложнее, но учитывая что стороны квадрата паралельны осям, код будет несложный.

Comments

[vampire444]

Спасибо за столь развёрнутый ответ, он помог всё упорядочить. Но всё же можно чуть подробнее по этому факту: "сторона многоугольника пересекается со стороной квадрата. Чуть сложнее, но учитывая что стороны квадрата параллельны осям, код будет несложный." Подскажите, хотя бы примерно, как это проверять?

[tsarevfs]

vampire444, Ну, например если смотрим на вертикальную сторону окна (xv, yv1) (xv, yv2) и произвольный отрезок (x1, y1) (x2, y2) // в скобках координаты концов
Если xv не попадает в интервал [x1, x2] -- нет пересечения
Иначе решаем уравнение (xv - x1)/(x2 - x1) = (yv - y1)/(y2 - y1) где yv -- y координата пересечения с вертикальной прямой. И остается проверить, что yv попадает в интервал [yv1, yv2].
Нарисуйте картинку, подписав все точки, станет понятней.

Answer 2

[Griboks]

Во многих языках программирования это уже реализовано. Например, Rectangle.Intersects().