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

Question

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

3

我目前正在解决一个问题，需要按照类似右手定则的方式正确排序组成三维空间中平面多边形的节点。我的想法是构建一个变换矩阵将节点转换为x-y平面，然后使用Graham扫描。我需要确保用户只输入凸多边形，因此如果发现任何“内部”节点，则知道该多边形是凹多边形并会抛出错误。除了检查凸性外，Graham扫描的排序过程也会为我排序节点。

我不太熟悉优化几何算法。这个过程是否合适/高效？还是有更好的方法：

1）按某种规则（例如RH规则）排序多边形的节点 2）确保平面多边形（可能不在x-y平面上）是凸多边形？

- MarkD

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ninjagecko · Accepted Answer

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

- 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个点，或者多个点的组合（仍然存在问题），并将THRESHOLD设置为最大距离的一部分。

在一些假设下，这是可以证明的最优解，因为否则，你可以使用它在少于O(n log(n))的时间内执行比较排序，而我们知道没有额外的知识是不可能的（问题映射将是将未排序数组的每个元素X放置在平面上的位置[X，X ^ 2]加上一个点[0，max ^ 2]）。