如何高效地确定在三维空间中多边形的法向量？

Question

我有一堆位于三维空间中的共面点来定义一个多边形。这些点总是以相同的方式缠绕（例如顺时针）。我需要确定包含该多边形的平面的有符号法线，即知道该多边形的“上”方向。

起初似乎很容易：取两条边（顶点差值）并计算叉积。但如果边恰好共线（即得到零大小的叉积），则会失败。

然后我尝试在顶点列表中遍历，直到找到与第一条边形成合理大角度的第二条边。对于凸多边形，这可靠地起作用，但如果我最终使用的两个边不定义在多边形内的三角形，则在非凸多边形上可能会失败（指向相反的方向）。

我知道如果先将多边形三角化，那么我可以轻松且可靠地检查任何三角形的朝向......但问题是我的三角化库需要知道平面法线。所以，先有鸡还是先有蛋的问题。

如何选择非凸多边形中的两条边（或三个顶点），以可靠地定义多边形的朝向？

- Joe Strout

---

离题了。这不是一个编程问题。这更像是几何/数学问题。请尝试访问http://math.stackexchange.com。 - Marc B

之所以在这里提问，是因为数学家通常会给出一个不容易实现（或者不清楚如何实现）的答案，例如，“如果连接相邻点的线完全位于多边形内，则顶点是耳朵”…… 这是一个正确的陈述，但对于实际编码并不有帮助。我正在寻求一个可以编写代码的算法。 - Joe Strout

@JoeStrout 我知道你已经得到了一个令人满意的答案，所以我想提醒你，我添加了一种不同（更简单？）的方法，我不确定你是否会“寻找”另一个答案。 - Amit

Answer 1

如果我是你，我会按照以下方式完成它：

1. 在多边形附近选择任何点C（任何顶点或重心）。 2. 对于所有的i（包括最后一个和第一个点对），求和交叉积(P[i] - C) x (P[i+1] - C)。 3. 标准化和向量。

请注意，在第二步之后，您有一个具有适当方向的法向量，其大小为2S，其中S是您的多边形面积。这就是为什么它能够工作，除非您的多边形面积接近于零。

顺便说一句，点C在这里只用于使远离原点的小多边形计算更加精确。您可以选择C = 0，有效地从计算中消除它。

- stgatilov

---

已经测试并确认在所有测试用例中都能正常工作。非常感谢！ - Joe Strout

@YvesDaoust：我不确定你是否完全阅读了问题。你的解决方案不能产生正确的法线方向。此外，它可能是不稳定的（取决于实现方式）。 - stgatilov

Answer 2

stgatilov提供的连续叉积之和不够健壮，请参考健壮的多边形法向量计算。一种健壮的解决方案是找到所有i、j（i < j）的最大叉积(P[i] - C) x (P[j] - C)，并将其标准化。它将对应于多边形中最大的内接三角形。

- kireevtf

---

这可能会导致凹多边形指向错误的方向，对吗？C 的选择是什么？ - Alec Jacobson

Answer 3

1. 从多边形中获取3个不在同一条直线上的点（您可以使用点积检查来避免处于共线段之间的点）。

2. 从这些点创建一个平面（由法向量和原点距离定义：Ax + By + Cz + D = 0）。对于空间中的任意多边形，平面方程都是众所周知的公式。对于任意多边形，该平面的法向量可能指向相反的方向，但在此步骤中这并不重要。

3. 将多边形中的任何线段（两个相邻连接的点）投影到该平面上。现在你有了平面2D空间中的2个点。这也是一个众所周知的操作 - 你只需要得到平面原点（即n * D），以及你可以用平面法向量和投影线段点向量构建出的x和y平面基向量，以获取它们在平面空间中的2D x和y坐标。

4. 在2D空间中取这个线段的2D法向量，非常容易 - 只需将2D向量旋转90度（或-90度，取决于您的坐标系）- 交换（x，y）并否定其中一个坐标。

5. 将新旋转的2D向量转换回3D空间 - 只需使用步骤3中已经拥有的平面原点和x、y基向量。假设这是您的副法线向量。

6. 现在你有了原始线段方向向量（只需减去线段点，假设它是切线）和步骤5中的副法线向量 - 对它们进行叉积，你将得到任意多边形的法向量，无论使用哪个线段来产生它，它都将始终指向正确的方向，因为您声明的点始终沿着相同的方向排列。

- Mr D