Возможно, это не то, что вы искали, но что-то вроде этого может сделать работу.
Предположим, вы можете вычислить список всех точек пересечения p1, p2,…, pk между периметрами из двух полигонов. Пусть v1, v2,…, vn - вершины первого многоугольника, а w1, w2,…, wm - вершины второго многоугольника.
Сначала создадим две упорядоченные коллекции c1 и c2, где c1 содержит p1, p2,…, pk и v1, v2,…, vn, по порядку (чтобы при обходе периметра многоугольника по часовой стрелке вершины появлялись в списке в порядке посещения), а c2 содержит p1, p2,… pk и w1, v2,…, vm упорядочены таким же образом.
Теперь между каждыми двумя соседними p (i% k) и p ((i + 1)% k) существует какое-то совпадение или разрыв. Это перекрытие или разрыв могут быть вырожденными, если вершины, появляющиеся в c1 и c2 между этими двумя точками пересечения, совпадают; в этом случае отслеживаемый полигон имеет нулевую площадь и может быть отброшен. В противном случае мы должны увидеть, определяют ли вершины в c1 и c2, появляющиеся между точками пересечения, зазор или перекрытие.
Если у нас есть простой / дешевый способ проверки, содержится ли точка в исходном многоугольнике просто выберите точку в пространстве (например, центр треугольника, образованного одной из точек пересечения, и каждая из соседних точек в c1 и c2 гарантированно находится внутри пространства) и посмотрите, включена ли эта точка в или c1 или c2 (это не может быть в одном и не в другом; почему?). Если точка включена, то у вас есть совпадение; в противном случае у вас есть пробел.
Действительно, у нас есть легкий путь. Если мы обойдем первый многоугольник по часовой стрелке, то если указанная выше точка (середина описанного так треугольника) находится справа от отрезка, образованного точкой пересечения и смежной с ней вершиной в c1, тогда это совпадение; в противном случае это пробел. Кроме того, вы можете go по часовой стрелке вокруг точек в c2 и использовать то же правило, чтобы сказать.
Чтобы увидеть, находится ли точка слева или справа от вектора:
взять вектор (например, точку пересечения с соседней точкой в c1 или c2)
взять вектор в точку-кандидат (например, центр описанный ранее треугольник)
Вычислить трехмерное перекрестное произведение
Знак z-координаты результирующего вектора дает ответ.
В этом примере:
p1, p2, p3 ~ (3.1, 5.5), (3.3, 4), (3.8, 2)
v1, v2, v3, v4, v5 ~ (1, 0), (1, 8), (4, 4.5), (2, 3), (3.8, 2)
w1, w2, w3, w4 ~ (4, 1), (3, 5), (4, 9), (9, 5)
c1 ~ (v1, v2, p1, v3, p2, v4, p3=v5)
c2 ~ (w1, p3, p2, w2, p1, w3, w4)
pairs of points of intersection adjacent in c1:
x1 = (p1, p2), x2 = (p2, p3), x3 = (p3, p1)
pairs of points of intersection adjacent in c2:
y1 = (p3, p2), y2 = (p2, p1), y3 = (p1, p3)
triangle for x1 has vertices (p1, v3, w2), middle is
~ ((3.1+4+3)/3, (5.5+4.5+5)/3) = (3.3, 5)
vector from p1 to v3 ~ (0.9, -1)
vector from p1 to middle of triangle ~ (0.2, -0.5)
cross product of p1-v3 x middle of triangle vector:
+0.9 -1.0 +0.0
+0.2 -0.5 +0.0
i j k
=> -0.45k
this has a negative sign, so this is an overlap
triangle for x2 has vertices (p2, v4, p3=v5), middle is
~ ((3.3+2+3.8)/3, (4+3+2)/3) = (3, 3)
vector from p2 to v4: (-1.3, -1)
vector from p2 to middle of triangle: (-0.3, -1)
cross product of p2-v4 and middle of triangle vector:
-1.3 -1.0 +0.0
-0.3 -1.0 +0.0
i j k
=> 1.3k
this has a positive sign, so this must be a gap