我正在使用Qt在C++中实现增量CH 3D，但无法克服此问题:
我必须找到给定点的视野:
我有一个包含给定点“pr”的所有可见面的列表的Map，但是我不知道如何在不更改算法复杂性的情况下仅获得地平线(它是O(nlogn))。
我的想法是:对于所有可见面孔的边缘，检查双胞胎的入射面孔是否可见。如果不可见，则将其添加到地平线边缘列表中，但是这种更改算法的复杂性(我认为)。
请注意，我还有另一个列表，其中有一组可以查看给定面孔的所有点(也许有帮助)。
真的非常感谢
最佳答案
如果只有凸多边形，则您的想法应该这样做(它的复杂度为O(1)，您已经有结果)。是的，您将使用复杂度O(n)进行额外的查找。