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

Question

Как найти пересечения между двумя (или более) трехмерными плоскими многоугольниками (для простейшего случая все они выпуклые)?Ищу алгоритмы, способные обеспечить линию пересечения, если она есть.Обратите внимание, что методы, предложенные для бесконечных плоскостей, бесполезны.

Answer 1

Существует 2 случая:

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

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

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

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

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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