c - Graham 的 3d 扫描，查找一般多边形的面积

Question

我的目标是在给定多边形的无序顶点以及平面方程的情况下，找到具有 n 个顶点的 3d 平面多边形的无符号区域。一旦点按顺时针或逆时针顺序排序，我已经有一个有效的算法来计算面积(来自本网站:http://softsurfer.com/Archive/algorithm_0101/algorithm_0101.htm#3D%20Polygons)

我决定实现 Graham 扫描来重新排序点，2d 情况下有很多示例，但 3d 情况下的示例不多。我认为我最好的选择是要么使用转换矩阵将 3d 点转换为 2d(我不确定该怎么做)，要么在 3d 中使用叉积来确定 3 个点是否形成逆时针转弯。我认为后者会更有效，因为我可以对每个叉积找到的区域求和，并在重新排序点时计算最终答案。

但是我仍然不确定如何在 3d 中实现 Graham 扫描。另外，我是否可以利用我已经知道顶点集是共面的并且它们都必须包含在凸包中以对我有利的事实？

编辑:进一步考虑，我什至需要在这里使用 Graham 的扫描吗？我已经知道所有的点都包含在船体中，所以按角度对它们进行排序还不够吗？最终目标是让点按逆时针/顺时针顺序排列，以便可以计算面积，我认为扫描对于实现这一点是必要的。

Answer 1

所有点线不能平行于所有主轴的平面，所以找到一个不平行于平面的平面并将所有点投影到其中(比如 Ox)。

由于投影方向不平行于平面，因此不会有两点交换位置或重合。现在在 2D 情况下执行凸包 - 您已经知道如何执行此操作。也因为我之前的陈述，3D 中点的顺序将与投影点的顺序相同 - 瞧，没有增加复杂性和相同的算法。

编辑:当然，任何其他投影都可以，但由于平行于其中一个主轴的投影非常简单(只需删除一个坐标)，我建议采用这种方法。