Path that gets within given distance of each point in order

user_7292139 0
Viewed 248

I have an ordered list of points in a 2D plane. I'd like to find the shortest route such that it gets at least within distance X (or closer) from each point, in the given order. How do I find this route?

I realize that the points that will determine the route (the direction changes there) will lie on circles of perimeter X, centered on the input points themselves, but I didn't get any further.

I'm implementing this in Python, but will be happy for any theoretical help.

Example: (oops I can't count so skipped 7) Example

plane euclidean-distance shortest-path algorithm
2 Answers

Perhaps there's an analytical approach, but this problem certainly can be solved with convex programming. Here's a Python implementation with cvxpy that outputs EPS.

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()

enter image description here

user_21446690

It seems you have to find minimum distance to the point which is x minimux x points away from the next point in the route.

I would suggesting finding the shortest distance between the starting point and all the circles cirumfrence , then choosing the shortest value and again repeating the same step.

So it will be like .

you have 4 points and you start at point 1(starting point which is at the cicumfrence of the circle 1),

calculate the shortest distance using shortest distance formula from cirumfrence

for the rest of the 3 circles (The distance will be calculated from point 1 to the circumfrence of all 3 circles ) and after that select the minimum distance from three.

Now move to point two (the one has the shortest distance) and repeat same for other two points left.


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.
user_138596090
Related