algorithm - 查找由平面包围的体积面

Question

最终，我想实现一个具有以下规范的算法:

输入:N 个 3 维平面(Ax + By + Cz = 每个平面给定的 D)

输出:

1. V 个顶点列表，以及
2. E 个边列表(V 中的对)，以及
3. 面的列表 F(从 E 开始循环)精确地限定了 包围的体积(即，在法线的另一侧) N 个平面

不能保证每个平面都与一个面重合，但可以保证体积始终明确存在(即平面具有良好的法线)。

我知道这属于计算几何领域，但我尝试使用谷歌搜索上面的一些术语，但没有找到任何内容。我认为解决方案应该包括二进制空间分区树。

到目前为止，我已经尝试过简单的方法 - 只是制作一个巨大的 N^2(ish)列表，其中包含平面之间的所有切片，然后针对每个平面检查每个切片，并删除那些在错误一侧的切片至少一架飞机。这是 N^3，当然效率很低，它甚至还没有给出边缘 - 您仍然必须计算边缘的起点和终点在切片上的位置。

任何指向 CG 算法的帮助都会很棒!谢谢!

Answer 1

由于 Preparata and Muller, 1979，有一个 O(n log n) 时间的算法.它使用极性对偶性和高效的 3D 凸包算法。我确定存在它的实现(可能是 qhull？)。