3

如果在二维平面上没有。所有可能的 2d 形状（圆形、四边形、三角形、不规则形状......）的障碍物，那么你如何实现一种机制来找到障碍物周围的最短路径？我正在考虑使用 Visual C++，因为它提供了许多图形类来绘制这些图形。

我已经走了很远

1）首先我将使用 A* 搜索（A-star）来找到成本最低的路径

2) 与直线路径位移最小的路径将被视为最佳路径。（虽然不太确定）

3）绕过一个图形的最短路径，例如从一开始，是从该点到 的一条线：

a) the farthest vertex in case of a polygon/quadrilateral
b) a point on the circumference such that the line drawn would be tangential to the circle, in case of a circle or arc
c) (not sure about irregular figures)

在此处输入图像描述

现在回到 2) 两条或多条路径之间的点最小位移，可以通过比较从这些线到物体各自侧面最远点的垂线来确定。（希望我已经让自己明白了）。

那么 - 我们如何绘制垂直路径？ 在此处输入图像描述

x1,x2,y1,y2,k 和 l是已知的。我们只需要找到a,b。

直线路径的斜率 * 垂直路径的斜率 = -1

=> (y2-y1)/(x2-x1) * (b-l)/(1-k) = -1
hence, b = [(x1-x2)/(y2-y1) * (a-k)] + l

我想象通过使用毕达哥拉斯定理，我们可以根据坐标找到另一个方程。每条线的长度可以这样求：dx = x1-x2 dy = y1-y2 dist = sqrt(dx dx + dy dy)

然后通过求解这两个方程，我们可以找到a,b的正确值。

我想不出任何进一步的想法或建议？

4

3 回答 3

3

是否可以对所有形状使用多边形（即直线段）近似？这将大大简化算法的实现。

假设这确实是可能的：如果您想使用 A*，那么您需要一个可以采用的可能路径的图形表示。该图的节点是以下各项的组合：

  • 所有形状[1]的所有顶点，以及
  • 起点和终点
  • {起点和终点之间的直线段}与所有形状之间的所有交点。

那么，该图中的边仅在每对节点之间

  • 它们对应的两个顶点之间存在一条直线
  • 不与任何形状相交[2]。

图中每条边的长度就是它所代表的两个顶点之间的（欧几里得）距离，最短路径始终是这些边的子集（我认为），您可以通过将 A* 应用于此图来找到它.

[1] - 为了减少顶点的数量，你可以使所有的凹形都凸出（除非这会导致起点或终点位于这样的形状内，否则它应该保持凹形）。

[2] - 您可以使用各种数据结构来加速这些查询，例如 kD 或四叉树，或者可能使用扫描线算法（例如http://en.wikipedia.org/wiki/Bentley%E2 %80%93Ottmann_algorithm ) 结合双连接边列表。

于 2012-11-05T20:24:47.030 回答
0

好吧，我不太确定这是否会有所帮助，但无论如何，每个不规则对象都可以拆分为规则对象的组合，例如圆，只是曲线的半径不断变化。所以你可以认为它是对应于的弧的组合不同的半径。

于 2012-11-06T10:12:51.463 回答
0

对于第二点，如果有点 (l,k)。考虑位于直线 (x1,y1),(x2,y2) 上的两个点，它们与 (l,k) 等距。因此，垂线将是与 (x1,y1) 和 (x2,y2) 等距的所有点的组合。

于 2012-11-06T10:45:46.393 回答