从边界点计算可见性多边形

Question

我使用CGAL库从简单多边形P中的点P中计算可见性多边形，其中p位于P的边界，我使用类"Simple_polygon_visibility_2“，当计算可见性多边形时，结果似乎是错误的。我将在附件中同时发送多边形P和由此产生的可见多边形。在本例中，我感兴趣的是从标记为"7“的顶点寻找可见性多边形。如您所见，生成的可见性多边形的边从"4“到"5”(因此，三角形"7-4-5")无效，因为这个三角形不是P的一部分。

我读过乔和辛普森的报纸，他们提到：

“对于边界点z，我们按逆时针顺序对P的顶点进行定向，并将它们标记为z，v_0，v_1，.，v_{n-1}，v_n和z，其中v_0是z的后继顶点，v_n是z的前顶点，我们还假定坐标系被转换和旋转，使z处于原点，v_0位于正x-轴上”

我认为这可能是问题所在，因为我不确定CGAL的实现是否测试查询点是否在边界上，如果是，则将其视为特例。如果是这样的话，我是否必须先验地进行这种平移/旋转？

​

​

Answer 1

其实这是我的错。由于点在边界上，所以它既不属于内面也不属于外部面(当布置是一个简单的多边形时)。因此，与其使用这个版本的"compute_visibility“方法，不如使用包含查询点的半边为参数的方法。在本例中，它按预期工作。