algorithm - 如何判断一个形状是否可以通过

Question

我有一个复杂的多边形（可能是凹面的），它的一些边缘标记为入口/出口点。这个多边形内部有可能存在一个或多个任意形状的封锁。我可以使用哪些方法来确定一对入口/出口边缘之间是否存在一定宽度的路径？

通读了这个问题，它看起来像一个家庭作业类型 - 它不是。我只是希望至少有一些我可以追求的线索，因为这对我来说是新的。

Answer 1

看看运动规划——那里有大量的信息。

Answer 2

这取决于路线是否需要有宽度。如果必须通过的对象的大小是有限的，则需要将域多边形与移动对象的多边形的 Minkowski 差值，然后尝试通过它。

精确计算路径的一种方法是计算多边形的可见性图。可见性图的顶点对应于域多边形的顶点（可能在障碍物所在的地方有孔），如果两个顶点可以“看到”彼此，则它们通过边连接。如果存在连接入口和出口的一组边，则该形状是可通过的。您还可以计算诸如最短路径之类的东西。以幼稚的方式计算可见性图并不难，但速度很慢。有非常先进的算法可以做到这一点，但它们（AFAIK）尚未实现。几年前我尝试实施，但结果平庸。他们中的大多数假设顶点在一般位置，使用精确的算术，而实际应用程序将使用浮点数。