三维平面多边形之间的交集

如何查找两个（或多个）三维平面多边形之间的交集（对于最简单的情况它们都是凸面）？寻求能够提供相交线的算法，如果有的话。注意为无限平面平面情况提出的方法没有用。三维平面多边形之间的交集

来源

2011-06-01 Developer

它们总是共面的吗？如果不是交点可能是点，线或者什么都没有 – 2011-06-01 01:50:57

如果您指的是每个多边形的顶点，那么它们是共面的。然而，多边形是3D的，并且可能不在同一个平面上，也就是说，相交可能是一个点或一条线或无效。 – Developer 2012-04-29 01:22:30

有两种情况：

两个多边形位于相同平面上。

查找第一个多边形的所有内部点。

任意取第一个多边形，循环遍历第二个多边形的所有顶点，并确定它们是位于第一个多边形的内部还是外部。对于凸多边形，这样做很容易：请参阅here。

查找2个多边形

之间的交叉点要查找的交叉点取多边形和环中的一个的每个边缘通过其他多边形的所有边以发现它们相交的任何地方。这可以通过使用intersection of 2 lines的公式找到。

相交区域是由顶点在内部点和相交点形成的多边形。

2个多边形位于不同的平面上。

找到第二个多边形与第一个多边形的交点。您可以通过考虑第二个多边形的每个边，并找到边和第一个多边形的平面之间的交点。这可以使用公式为line and a plane之间的交集找到。

检查您发现的交点是位于第一个多边形的内部还是外部。

来源

2011-06-01 02:00:20

我试过这个算法，两个多边形的一个躺在不同的平面上。尽管我有一些困难来有效地实现所讨论的数学（链接）的代码，但最终它的工作，这只是很重要。我已经尝试过使用CGAL，但是因为编译等方面的严重困难而感到非常失望。我使用的方法总结为首先对多边形进行三角化（这里出现一些困难！），然后找到交点。 – Developer 2011-06-10 10:23:57

对于两个多边形是共面的情况下，那么在这里是至少对于该特定情况下的解决方案：

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

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

来源

2011-06-01 02:04:33 Hyperboreus

该算法仅适用于2D。问题是要求3D多边形。 – 2011-06-01 02:07:41

是的。如果这两个多边形是共面的，这个算法就可以工作。但是，这不是在问题陈述中给出的。问题是每个单独的多边形都是平坦的。它并不是说它们都必须躺在同一架飞机上。 – 2011-06-01 02:09:42

这是一种方法。通过将一个多边形旋转到XY平面，可以将3D问题简化为2D问题（主要是），而且通常不会出现太多的性能问题。

旋转第一多边形的点，使得其位于在X-Y平面内。
旋转第二个多边形的点的方向和数量与第一个相同。
检查第二个多边形中的每一行，看看它是否以及在哪里截取X-Y平面。对于凸多边形，这应该发生两次，在点A和B.
找到AB线与第一个多边形的边的所有交点。如果第一个多边形是凸的，则应该有0,1或2个交点。
案例：零交点：AB线或者完全位于第一个多边形的内部或外部。如果在里面，AB是飞机的相交线。如果在外面，没有交集。
案例：一个交点C点：A或B位于第一个平面内。该平面的相交线是内点（A或B）至C.
案例：两个相交点：平面的相交线是AB
将相交线旋转回原始位置，相反在步骤1中完成旋转。

作为练习，读者可以将此方法扩展到非凸多边形。 :)（其实很简单）

检查点是否在二维多边形内的一种方法是从该点向上的线与该多边形的所有边交点。 0或2：外部。 1：里面。（这也适用于在外部和内部使用偶数和奇数的非凸多边形。）

来源

2011-06-01 02:29:07 xpda

我不知道如何将3D平面投影到所需的（例如xy）平面上。任何帮助？正如我从网上找到的，这个问题也不容易，因为它看起来！ – Developer 2011-06-10 10:27:45

三维平面多边形之间的交集

回答

相关问题