按顺序到达每个点的给定距离内的路径

Question

我有一个二维平面中点的有序列表。我想找到最短路线，使其至少在给定顺序的每个点的距离 X（或更近）以内。我如何找到这条路线？

我知道决定路线（方向在那里改变）的点将位于周长 X 的圆上，以输入点本身为中心，但我没有进一步了解。

我正在 Python 中实现它，但很乐意提供任何理论上的帮助。

示例：（哎呀我数不过来所以跳过了 7）

Answer 1

看来你必须找到距离路线中下一个点 x minimux x points 的点的最小距离。

我会建议找到起点和所有圆 cirumfrence 之间的最短距离，然后选择最短值并再次重复相同的步骤。

所以它会像.

你有 4 个点，你从点 1 开始（起点在圆 1 的圆周上），

使用shortest distance formula from cirumfrence计算最短距离

剩下的 3 个圆（距离将从点 1 到所有 3 个圆的圆周计算），然后 select 到三个的最小距离。

现在移动到第二点（距离最短的那个），对剩下的另外两点重复相同的操作。


circle1(x0,y0)
circle2(xx0,yy0)
circle3(xxx0,yyy0)
circle4(xxxx0,yyyy0)

cirle 1 (x0,y0) is the center and you have **p1** on circumfrence p1(x1,y1) 

from p1 calculate the shortest distance to all three circles like 
distance from p1 to circle2 
Distp1Toc2= sqrt(square(x1-xx0) + square(y1-yy0) -r) // this will give you shortest distance from point 1 to a point on circle2 cirumfrence 

repeat this for circle3 and cirlce4 to calculate **Dist_p1_To_c3** and **Dist_p1_To_c4**  then select the minimum distance

lets consider **Dist_p1_To_c2** is minimum and now from the point Dist_p1_To_c2 again calculate the distance to circle 3 and circle4 to find minimum distance.

Answer 2

也许有一种分析方法，但这个问题肯定可以用凸规划来解决。这是使用输出 EPS 的 cvxpy 的 Python 实现。

import cvxpy as cp
import numpy as np


def objective(points):
    return np.sum(np.linalg.norm(points[1:] - points[:-1]))


def shortest_path(x, centers):
    points = cp.reshape(cp.Variable(centers.size), centers.shape)
    cost = cp.sum(cp.norm(points[1:] - points[:-1], axis=1))
    constraints = []
    for i, center in enumerate(centers):
        constraints.append(cp.SOC(x, points[i] - center))
    prob = cp.Problem(cp.Minimize(cost), constraints)
    prob.solve()
    return points.value


def main():
    x = 0.05
    centers = np.random.random_sample((10, 2))
    points = shortest_path(x, centers)
    print("%!PS-Adobe-3.0 EPSF-3.0")
    print("%%BoundingBox:0 0 504 504")
    print("72 dup translate")
    print("360 dup scale")
    print("0 setlinewidth")
    for center in centers:
        print(*center, x, 0, 360, "arc")
        print("stroke")
    for i, point in enumerate(points):
        print(*point, "lineto" if i else "moveto")
    print("stroke")


if __name__ == "__main__":
    main()

按顺序到达每个点的给定距离内的路径

Path that gets within given distance of each point in order

algorithm

shortest-path

plane

euclidean-distance