algorithm - 在停留在 "road"的假设下寻找连接两点的最短路径？

Question

我搜索以下问题的名称(以及后来的算法 ;)):找到从点 z0 到 ze 的最短路径，例如路径停留在“道路”上。下图更好地说明了这一点。道路由点 X=(x1,...,xk) 和 Y=(y1,...,yn) 的两个向量定义。我们假设问题并不棘手(即路径 X、Y 不交叉，起点/终点在“道路”上，等等)。我们想找到红线(定义为向量)Z 是连接 z0 和 zend 的最短路径，并且只经过这条路。算法不需要很快。非常感谢任何提示!

更新:评论后我更改了图像，因为它显示了错误的解决方案...:/

Answer 1

根据您的绘制方式，您的道路是一个单调的多边形(也就是说，当您直接面向北方时，Y 总是在您的左侧，而 X 总是在您的右侧)。一旦你对多边形进行了三角剖分，就会有一种算法专门用于在单调三角剖分中寻找最短路径，称为“漏斗算法”。

对于单调的三角剖分，Mark de Berg 的计算几何 中的描述很好，但失败了，http://www.cs.ucf.edu/courses/cot5520/Triangul_monotone.ppt看起来不错。对于漏斗算法，尝试here .