c++ - 在增量 Convex Hull 3D 期间获取点的地平线

Question

我正在使用 qt 在 c++ 中实现增量 CH 3D，但我无法克服这个问题：

我必须找到给定点的视野：

我有一张地图，其中列出了给定点“pr”的所有可见面的列表，但我不知道如何在不改变算法复杂度的情况下只获得地平线（它是 O(nlogn)）。

我的想法是：对于所有可见面的边缘，检查双胞胎的入射面是否可见。如果它不可见，则将其添加到地平线边缘列表中，但这会改变算法的复杂性（我认为）。

请注意，我有另一个列表，其中包含可以查看给定面部的所有点的集合（也许有帮助）。

真的提前谢谢

Answer 1

如果你有凸多面体，只有 ，你的想法应该这样做（它的复杂性是 O(1)，你已经有了结果）。是的，你会做一个复杂度 O(n) 的额外查找。