如何判断一个形状是否可以通过
我有一个复杂的多边形（可能是凹的）和它的一些边缘标记为入口/出口点。该多边形内部有可能存在一个或多个任意形状的障碍物。我可以使用什么方法来确定一对入口/出口边缘之间是否存在一定宽度的路径？
通读完这个问题后，它看起来像是一个家庭作业类型——但事实并非如此。我只是希望至少有一些可以追踪的线索，因为这对我来说是新的。
I have a complex polygon (possibly concave) and a few of its edges marked as entry/exit points. there is a possibility that inside this polygon may lie one or more blockades of arbitrary shape. what approaches could I use to determine whether a path of certain width exists between a pair of entry/exit edges?
having read through the question it looks like a homework type - it is not. I just wish to have a at least a few leads I could pursue, as this is new to me.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
查看运动规划 - 那里有大量信息。
Take a look at Motion Planning - there's a wealth of information there.
这取决于路线是否需要有宽度。如果必须移动的对象具有有限的大小，则需要采用域多边形与移动对象的多边形的 Minkowski 差值，然后尝试通过该对象进行路由。
精确计算路径的一种方法是计算多边形的可见性图。可见性图的顶点对应于域多边形的顶点（可能在障碍物所在的地方有孔），并且如果两个顶点可以彼此“看到”，则通过边连接它们。如果存在一组连接入口和出口的边，则该形状是可以通过的。您还可以计算最短路径等内容。以简单的方式计算可见性图并不难，但速度很慢。有非常先进的算法可以做到这一点，但它们（据我所知）尚未实现。几年前我尝试过实施，但效果平平。它们中的大多数使用精确算术假设顶点处于一般位置，而实际应用将使用浮点数。
It depends on if the route needs to have a width to it. If the object that has to move through has a finite size, you need to take the Minkowski difference of your domain polygon with the moving object's polygon, then you try to route through that.
One way to compute paths exactly is to compute the visibility graph of the polygon. The visibility graph has vertices corresponding to the vertices of the domain polygon (possibly with holes where the obstacles are), and two vertices are connected by an edge if they can "see" each other. The shape is passable if there exists a set of edges joining an entry to an exit. You can also compute things like shortest paths. Computing the visibility graph in a naive way is not hard, but slow. There are very advanced algorithms for doing it, but they (AFAIK) have not been implemented. I tried implementing a few several years ago, with only mediocre results. Most of them assume vertices in general position, using exact arithmetic, whereas practical applications would use floating point numbers.