Пересечение между трехмерными плоскими полигонами

Есть 2 случая:

Оба многоугольника лежат в одной плоскости.

Найти все внутренние точки первого многоугольника.

Произвольно возьмите первый многоугольник, переберите все вершины второго многоугольника и определите, лежат ли они внутри или снаружи первого многоугольника. Сделать это легко для выпуклых многоугольников: см. здесь.

Найдите точки пересечения двух полигонов

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

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

Два многоугольника лежат в разных плоскостях.

Найдите пересечение второго многоугольника с плоскостью первого. Вы можете сделать это, рассмотрев каждое ребро 2-го многоугольника и найдя пересечение между ребром и плоскостью первого многоугольника. Это можно найти, используя формулу пересечения между прямой и плоскостью.

Проверьте, лежат ли найденные вами точки пересечения внутри или снаружи первого многоугольника.

Вот один из способов. Поворачивая один полигон в плоскости XY, вы сводите 3D-задачу к 2D-задаче (в основном), и обычно это не слишком сильно влияет на производительность.

1. Поверните точки первого многоугольника так, чтобы он лежал на плоскости X-Y.
2. Поверните точки второго многоугольника в том же направлении и на ту же величину, что и первый.
3. Проверьте каждую линию во втором многоугольнике и посмотрите, пересекает ли она плоскость X-Y и где. С выпуклым многоугольником это должно произойти дважды, в точках А и В.
4. Найдите все пересечения линии AB с ребрами первого многоугольника. Должно быть 0, 1 или 2 пересечения, если первый многоугольник выпуклый.
5. Случай: нулевые пересечения: линия AB полностью находится внутри или снаружи первого многоугольника. Если внутри, то АВ — линия пересечения плоскостей. Если снаружи, то пересечения нет.
6. Случай: одно пересечение, точка C: либо A, либо B находятся внутри первой плоскости. Эта линия пересечения плоскостей находится внутри точки (A или B) до C.
7. Случай: два пересечения: линия пересечения плоскостей AB
8. Поверните пересекающуюся линию обратно в исходное положение, в обратном порядке по отношению к вращению, сделанному в шаге 1.

Читателю предлагается в качестве упражнения распространить этот метод на невыпуклые многоугольники. :) (На самом деле это довольно просто.)

Один из способов проверить, находится ли точка внутри двумерного многоугольника, — это получить пересечения линии, идущей от этой точки вверх, со всеми ребрами многоугольника. 0 или 2: снаружи. 1: внутри. (Это также работает для невыпуклого многоугольника, используя четные и нечетные значения снаружи и внутри.)

Для случая, когда оба многоугольника лежат в одной плоскости, вот как минимум решение для этого конкретного случая:

http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html

У него даже есть хороший апплет, показывающий алгоритм.