给定一个多边形 S 和一个位于 S 外部的点 p，想象一只 Ant 只能沿着一条朝向或远离 p 的直线移动。
对于某些形状(图 1)，可以选择 p，以便 Ant 可以以两种可能性中的至少一种无障碍移动:朝向 (T) p 或远离 (A) p。此条件对应于从 p 转换的任何光线与 S 的周长恰好相交 0 或 2 次。
然而，对于相同的形状(图 2)，也可能有一些点会导致阻塞 (B) 区域，无论 Ant 试图向哪个方向移动，都会在该区域碰撞到多边形。对于其他形状(图 2) 3) 可能无法选择导致不存在阻塞区域的 p。具有阻挡区域对应于从 p 转换的一些光线与 S 的周长相交超过 2 次。
是否有一种算法可以确定是否存在满足某个给定多边形S的条件的p？如果存在这样的点，是否也可以确定包含它们的区域？
最佳答案
找到多边形障碍物的所有凹角。对于每个角，无限延伸其两条边。这两条射线之间的扇区，以及(正如 Nico Schertler 指出的)该扇区的点反射区域，定义了该点必须位于的位置，以便障碍物不会隐藏该点射线的角点。
在 L 形障碍物的示例中，有一个凹角。其相邻边缘(右上角)与其点反射(左下角)之间的扇区形成一个区域(以红色表示)，该点必须位于其中。
在 U 形障碍物的示例中，有两个凹角，并且两个对应区域(红色和蓝色)有重叠(紫色)。该点必须在这个紫色区域内。
在 S 形障碍物的示例中，有两个重叠区域(紫色)。该点必须位于这两个区域之一。
在 H 形障碍物的示例中，红色和蓝色区域在 H 的水平光束上方有重叠(紫色)，蓝色和绿色区域在水平光束右侧有重叠(青色) ，绿色和黄色区域在水平光束下方有重叠(石灰)，黄色和红色区域在光束左侧有重叠(橙色)；但是，四个区域之间不存在整体重叠，也没有满足约束条件的点所在的位置。
关于algorithm - Ant 可以走向或远离有多边形障碍物的点吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37757394/