algorithm - 3D 平面多边形之间的交集

Question

如何找到两个（或更多）3D 平面多边形之间的交点（最简单的情况下它们都是凸的）？寻找能够提供相交线的算法（如果有的话）。请注意，针对无限平面 - 平面情况提出的方法没有用。

Answer 1

有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

它甚至有一个很好的小程序显示算法。