如何确定一个多边形是位于另一个多边形的上方、下方还是内部?

Question

我正在编写一个BSP树程序。如何将多边形分类为平面上方或下方？

我对矩阵或向量数学了解不多，所以如果答案确实涉及它，你能解释一下它与多边形分类的关系吗？

Answer 1

假设我们有一个n = (n1, n2, n3)法向的平面，并且它与原点的垂直距离为d。

如果你有一个点x在飞机上，那么

x1n1 + x2n2 + x3n3 = -d

如果 D 有正号或负号没有严格定义。但我们可以将其表述为

x1n1 + x2n2 + x3n3 + d = z

如果z>0则在平面上方有一个点。

现在对于多边形 p，我们必须对所有点/顶点执行此操作，让我们保持在 3D 中，我们得到 z 的 3 个值。

if all(z > 0):
p is above
else if all(z < 0):
p is below
else
p is cut by the plane

注意： 根据设置的不同，浮点运算的误差可能相对较高，对于实际在平面上的点，误差甚至高达~1e-2。

---

类似的问题和答案可以在这里找到，还有一些关于替代形式的提示。