Joe*_*out 4 algorithm polygon computational-geometry geometry-surface
我有一堆共面点在 3D 空间中定义了一个多边形。这些总是以相同的方式缠绕（例如顺时针）。我需要确定包含该多边形的平面的有符号法线，即，知道该多边形的“向上”方向。
起初这似乎很容易：取两条边（顶点差）并计算叉积。但是如果边缘恰好是共线的（你得到一个零幅度的叉积），那就失败了。
然后我尝试遍历顶点列表，直到找到与第一条边成相当大角度的第二条边。这在凸多边形上可靠地工作，但如果我最终得到的两条边没有定义多边形内部的三角形，它可能会在非凸多边形上失败（指向相反的方向）。
我知道如果我先对多边形进行三角剖分，那么我可以轻松可靠地检查任何三角形的面……但问题是我的三角剖分库需要知道平面法线。所以，鸡蛋必须先于鸡。
如何在非凸多边形中选取两条边（或三个顶点）来可靠地定义多边形面向的方向？
如果我是你，我会通过以下方式完成：
请注意，在第 2 步之后，您将获得一个具有正确方向的法向向量，其大小为2 S，其中S是多边形的面积。这就是为什么它应该工作的原因，除非您的多边形面积为零或几乎为零。
顺便说一下，这里使用 C 点只是为了使远离原点的小多边形的计算更精确一些。您可以选择C = 0，有效地将其从计算中删除。