如果在2D平面上有一个没有。所有可能的2D形状（圆形，四边形，三角形，不规则形状...）的障碍，那么你如何实现一种机制来发现周围障碍物的最短路径？我考虑的Visual C ++，因为它提供了许多图形类得出这样的数字。

If on a 2d plane there are a no. of obstacles of all possible 2d shapes(circles, quadrilaterals, triangles, irregular shapes...) then how do you implement a mechanism to find the shortest path around the obstacles? I'm considering visual c++, as it provides many graphical classes to draw such figures.

我取得了相当大

1）首先，我将使用A *搜索（一星），以找到最低成本路径

1) Firstly i'll be using A* search(A-star) to find the path with least cost

2）用最少的排量从直线路径的路径将被视为最佳路径。 （真的不知道虽然）

2) The path with the least displacement from the straight path will be considered for best path. (not really sure though)

3）绕过一个数字，对于如从一开始的最短路径，是一条线从该点：

3) The shortest path to get around a figure, for eg from the start, is a line from that point to :

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）点 - 至少位移可以通过从这些行到对象的最远点上它们各自的两侧比较垂线来确定。 （希望我已经把自己理解的）。

Now coming back to the 2) point- least displacement between 2 or more paths can be determined by comparing perpendiculars from those lines to the farthest points of an object on their respective sides. (hope i've made myself understood) .

那么则 - 我们怎么画垂线的直线路径？

So then- how do we draw perpendiculars to the straight path?

X1，X2，Y1，Y2，k和l 的是已知的。我们只需要找到的 A，B 的。

x1,x2,y1,y2,k and l are known. We just have to find a,b.

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

Slope of the straight path * slope of it's perpendicular = -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 =开方（DX * DX + DY * DY）

I've imagined that by using pythagoras theorem we can find the other equation in terms of the co-ordinates. The lengths of each line can be found by this way: dx = x1-x2 dy = y1-y2 dist = sqrt(dx*dx + dy*dy)

然后通过解决这些2 eqns我们可以找到正确的价值观的 A，B 的。

And then by solving these 2 eqns we can find the correct values of a,b.

我想不出什么further-任何意见或建议？

I can't think of anything further- any ideas or suggestions?

推荐答案

有没有可能是你使用的多边形（即直线段）近似为各种形状？ 这将简化算法的实现了很多。

Is it possible that you use polygonal (i.e. straight line segment) approximations for all shapes? This would simplify the implementation of the algorithm a lot.

假设这确实是可能的：如果你想使用A *，那么你就需要一个曲线图重新presentation 那您可以采取的可能路径。此图的节点是的组合：

Assuming that this is indeed possible: If you want to use A* then you'll need a graph representation of the possible paths that you can take. The nodes of this graph are the combination of:

在此图中的边缘，然后，分别对节点之间仅当

The edges in this graph, then, are between each pair of nodes only if

每个边的图中的长度则这两个顶点将其重新presents之间简单的（欧氏）距离，最短路径始终是这些边缘的一个子集（我认为），你可以找到通过将A *这个图。

The length of each edge in the graph is then simply the (euclidean) distance between the two vertices it represents, and the shortest path is always a subset of these edges (I think), which you can find by applying A* to this graph.

[1] - 减少顶点的数量，可以使所有凹形状凸块（除非这会导致启动 或终点在于这种形状在里面，那么就应保持凹）。

[1] - To reduce the number of vertices, you can make all concave shapes convex (unless this causes the start or end point to lie inside such a shape, then it should be kept concave).

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

[2] - You can use a variety of data structures to speed up these queries, such as kD or quad trees, or maybe use a sweep line algorithm (such as http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm) in combination with a doubly-connected edge list.