java - 机器人的平滑路径

Question

我正在计算机器人在具有多边形障碍物的平面上的最短路径。一切都运行良好且快速，没有问题。但是，如何平滑路径使其变得弯曲？下面是用直线连接顶点的路径的图片。附言机器人只是一个圆圈。

Answer 1

This paper可能有用。看起来这是一个不平凡的问题。摘要:

Automatic graph drawers need to compute paths among ver- tices of a simple polygon which besides remaining in the interior need to exhibit certain aesthetic properties. Some of these require the incorpo- ration of some information about the polygonal shape without being too far from the actual shortest path. We present an algorithm to compute a locally convex region that “contains” the shortest Euclidean path among two vertices of a simple polygon. The region has a boundary shape that “follows” the shortest path shape. A cubic Bezier spline in the region in- terior provides a “short and smooth” collision free curve between the two given vertices. The obtained results appear to be aesthetically pleasant and the methods used may be of independent interest. They are elemen- tary and implementable. Figure 7 is a sample output produced by our current implementation.