algorithm - 哪些是 3d 凸对象切片算法（有哪些复杂性）？

Question

我想知道什么是最快的（就 而言O(N)）算法，具有凸三维对象及其位于某个 XYZ 的左上边界框角可以为其横截面提供由 3d 空间的 3 个点定义的某个平面？

Answer 1

这是一种可能的算法（假设对象是凸多边形实体）：

1. 计算平面与对象每条边之间的交点。如果边与平面共面，则假设它在边的每个端点处相交。
2. 按顺时针顺序对交叉点进行排序。

而已。平面和凸多边形实体之间的交点本身必须是凸多边形，这个简单的算法可以准确地为您提供多边形的点。

由于计算平面和边的交点需要常数时间，所以时间是O(E + K log K)，其中E是实体中的边K数，是交点（最终多边形中的点）的数量。K可能在E最坏情况下的数量级，因此总运行时间O(E log E)在最坏情况下。