查找多边形中花费最少的路径

我正在尝试在多边形内部查找其路径，以考虑其成本。查找多边形中花费最少的路径

在我的具体情况中，我有一个角色只应该比较直，也就是说，移动到北部，东部，南部或西部的角度应该不会超过几度。

理想情况下，我会分配一个随偏差而增加的成本。我认为这是一个图论相关的问题，但我不知道如何在多边形中做到这一点...

图中的红色虚线路径是常规算法产生的;绿色是关于我想要的。 编辑：我搞砸了一下这幅画;澄清：红色路径是多边形内最短路径，我希望绿色路径是角度约束下可能的最短路径。

（为了澄清，如果我的多边形看起来像(1)，我希望的路径是这样(2)，不是单纯的点之间的直线）

(1) ,-------------------+  (2) ,-------------------+ 
    /    (B) |   /    (B) | 
    /     |  /   / | 
+--+      | -> +--+    / | 
|      +-+  |    / +-+ 
| (A)     |  | (A)-------------+  | 
+-----------------------+  +-----------------------+

来源

2014-07-10 user1449556

A *可能适合您的角度限制 – sp2danny

是您的空间离散还是连续？ –

@VikramBhat它是连续的，并且作为一组点/顶点或三角化出现 – user1449556

这实在是更多的评论，但我不能评论，因为它需要50个声望......奥托，我不认为有满意的答案问题，因为它没有很好的定义。但对于一个有趣的问题+1 :-)

给出红色虚线的算法从您的路径的起点和终点之间的直线开始（它不完全位于多边形内）。然后，沿着直到你碰到一个角落，并将其作为你的新起点。（请注意，您绘制的红色虚线并不是最短的路径。）现在，您的绿线基本上是红线，用于替换您不喜欢的（错误的角度）棋子，但路径较长，但由于某种原因更好（好角度）。这也是给你下面例子的“正确”答案。从（A）到（B）的直线开始，这是最短路径，位于多边形内部。现在用更有利的角度更换这条线。（这可能会迫使你在一般情况下需要转多圈......）

只是有些想法。

来源

2014-07-10 11:02:26 1k5

再次我不能评论其他答案，所以我会评论我自己的......而如果你的情况比你所描述的情况更复杂（如你的多边形内所有形状的障碍物），John Doe的第一个答案是非常好的。对于一个简单的多边形，John Doe的第二个答案基本上和我的一样，除了他更喜欢采用随机路径而不是我的确定性方法:-) – 1k5

感谢您的输入！ “不是很好定义”是什么意思？ – user1449556

这是数学家代表你说的并不是非常精确的指定你正在寻找的路径类型。特别是我有点困惑：（1）红色路径实际上并不是最短的，这就是我认为你在寻找的东西;（2）绿色路径的水平部分延伸到左边的角落，这使得它比必要的稍长。是否有一个原因？ – 1k5

运行Rapidly exploring random tree algorithm但限制探测方向在平行于轴线的几个方向内，并且通过选择较大的增量距离来保持转弯数量较低。基本上根据你的意愿添加任何启发式。

Rapidly-Exploring Random Trees: A New Tool for Path Planning是关于快速探索随机树木的开创性论文。

来源

2014-07-10 11:15:38

我会在这里添加另一个答案，因为它与我的另一个有很大的不同。从常规路径寻找算法的结果开始，运行随机优化以使适应度函数最大化，该适应度函数通过添加顶点，移动顶点并删除顶点来描述路径的“相对平直度”（以及短度和其他度量，如果您愿意的话）一条路径，同时仍然保持路径有效。

常见的随机优化方法包括Simulated Annealing。

来源

2014-07-10 11:19:51

查找多边形中花费最少的路径

回答

相关问题