algorithm - Ant 能否走向或远离具有多边形障碍物的点？

Question

给定一个多边形 S 和一个位于 S 外部的点 p，想象一只 Ant 只能沿着一条直线朝向或远离 p。

对于某些形状(图 1)，可以选择 p，这样 Ant 至少可以在两种可能性中的一种中畅通无阻地移动:朝向 (T) p 或远离 (A) p。此条件对应于从 p 转换的任何光线恰好与 S 的周界相交 0 或 2 次。

但是，对于相同的形状(图 2)，也可能有一些点会导致阻塞 (B) 区域，在该区域， Ant 无论试图向哪个方向移动都会撞到多边形。对于其他形状(图. 3) 可能没有选择导致没有阻塞区域的p。具有阻挡区域对应于从 p 转换的一些光线与 S 的周界相交超过 2 次。

是否有一种算法可以确定是否存在满足某个给定多边形 S 条件的 p？如果存在这样的点，它是否也可以确定包含它们的区域？

Answer 1

找到多边形障碍物的所有凹角。对于每个角，无限延伸它的两条边。这两条光线之间的扇区，以及(正如 Nico Schertler 指出的那样)该扇区的点反射区域，定义了点必须位于的位置，以便障碍物不会隐藏点光线的角落。

在 L 形障碍物的示例中，有一个凹角。它的相邻边缘(右上)和它的点反射(左下)之间的扇区形成一个区域(以红色表示)，点必须位于该区域。

在 U 形障碍物的示例中，有两个凹角，两个对应区域(红色和蓝色)有重叠(紫色)。该点必须在这个紫色区域中。

在带有 S 形障碍物的示例中，有两个重叠区域(紫色)。该点必须位于这两个区域之一。

在 H 形障碍物的示例中，红色和蓝色区域在 H 的水平光束上方有重叠(紫色)，蓝色和绿色区域在水平光束的右侧有重叠(蓝绿色) ，绿色和黄色区域在水平光束下方有重叠(石灰)，黄色和红色区域在光束左侧有重叠(橙色)；但是，四个区域之间没有整体重叠，也没有满足约束条件的点。