在3D空间中追踪2D多边形 - 适当的算法？

Question

我目前正在研究一个问题，我需要对3D空间中构成平面多边形的节点进行正确排序（使用类似于右手规则的东西）。到目前为止，我的想法是构建一个转换矩阵将节点转换为x-y平面，然后使用Graham扫描。我需要确保用户只输入凸多边形，所以如果我找到任何“内部”节点，我知道多边形是凹的，可以抛出错误。除了检查凸面之外，格雷厄姆扫描的排序过程将为我排序节点。

我并不熟悉优化的几何算法。这看起来像是一个适当/有效的过程吗？或者有更好的方法：

1）按照一些规则（例如RH规则）和 排列多边形的节点2）确保平面多边形（可能不在x-y平面中）是凸的？

Answer 1

是的，这是一个非常好的解决方案。以下是如何实现它以忽略数字不准确性。

- take any 3 points; these determine the plane, rotate appropriately 
- check that abs(z)<THRESHOLD for all z-coordinates, now you can ignore them 
- perform Graham scan which is O(n log(n)) time 
- return order, else throw error if results.size < #points (non-convex) 

您可能希望充分选择3点相距甚远，或许多点的组合（仍然有它的问题），并作出阈值之间的最大距离的某一部分。

若干假设，这是可证明一样好，你可以做渐近，因为否则的话，你可以使用它来在不到O(n log(n))时间进行比较排序，我们知道这是不可能的，无需额外的知识（中问题映射就是将未排序数组的每个元素X放置在平面中的[X，X^2]位置加上[0，max^2]处的一个点）。