computational-geometry - 从边界中的一点计算可见性多边形

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 的实现是否测试查询点是否在边界上，如果是，则将其视为特例。如果是这样，我是否必须先验地进行这种平移/旋转？

标签： computational-geometrycgal

Answer 1

其实，这是我的错。由于该点位于边界中，因此它既不属于内部面也不属于外部面（当排列是简单多边形时）。因此，我应该使用包含查询点的半边作为参数的方法，而不是使用此版本的“compute_visibility”方法。在这种情况下，它按预期工作。