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

Question

[Ckworec]

Доброго времени суток! Решаю задачу на поиск пересечения/объединения двух полигональных областей, заданных множеством точек. Для этого хочу создать копии областей с добавленными в них точками пересечения и при обходе области при обнаружении точки пересечения перескакивать на другую область, в случае объединения, и использовать алгоритм Уайлера — Атертона для поиска пересечения. Функция поиска точки пересечения понятна в большинстве случаев, но не во всех, например если стороны областей пересекаются по отрезку, то как определить какую точку брать в качестве точки пересечения?
В данном случае в многоугольник AIJH должны добавится точки B, K, G и в многоугольник ABCDEFGH должна добавится точка K.
Алгоритм Уайлера — Атертона: https://www.geeksforgeeks.org/weiler-atherton-poly...

Answer 1

[Wataru]

Я бы в таком случае добавлял обе вершины от второго многоугольника, которые лежат на первом. Так все новые ребра каждого многоугольника или целиком не пересекаются со вторым, или целиком лежат внутри него, или целиком на его границе.

Т.е. действительно, в вашем случае надо в AIJH добавить точки ABKJH.

Образуются ребра длины 0 - значит повторяющиеся вершины надо просто выкинуть.

Answer 2

[mayton2019]

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

( x1 >= x > x2, y1 >= y > y2 )

Это дает возможновть в любых координатах в int, double e.t.c. считать плотно рядышком стоящие
прямоугольники не пересекающимися вообще.