CODEWITHSUNDEEP
pythonpython-3.xmatplotlib
Amarth Gûl
Amarth Gûl

Reputation: 1090

Strange result sorting points by distance in python

I got a list of points by extracting the edge of a image, like that:enter image description hereBut it is not well ordered, so if I connect it as a line, it will be:enter image description here

Thus I want to sort this list if points. Like, start with point_0, find which one has the shortest distance with it, say, point_3, then find which one's closest to point_3 then continue... To sort the points, I wrote this:

import matplotlib.pyplot as plt
import numpy as np
import math
def dist(now, seek):
    return math.sqrt((now[0] - seek[0])**2 + (now[1] - seek[1])**2)

def sortNearest(x, y):
    if len(x) != len(y):
        raise Exception('Error! Array length do not match!')
        return False
    xNew = []; yNew = []

    nearest = 0 #record which point is nearest
    now = [x[0], y[0]] #start point index
    seekValue = 0
    while len(x) > 0:
        distance = (max(x) - min(x)) + (max(y) - min(y))
        for seek in range(len(x)): # other
            temp = dist(now, [x[seek], y[seek]])
            if temp < distance and temp != 0.0:
                distance = temp
                seekValue = x[seek]
        xNew.append(now[0]); 
        yNew.append(now[1]); 

        if len(x) > 0:
            x.remove(now[0])
            y.remove(now[1])
        if len(x) > 0:
            nearest = x.index(seekValue)
            now = [x[nearest], y[nearest]]
    x = list(xNew); y = list(yNew)
    return xNew, yNew

x, y = getBorder('large.png', maxRes = 125)
x, y = sortNearest(x, y)

But that doesn't work well, I came up with this:enter image description here Which is obviously incorrect, if I zoom in, see:enter image description here If my code runs what I want, point_644 should connect 620 or 675, any but 645... What's wrong with it?

Upvotes: 2

Views: 586

Answers (3)

Ramon Crehuet
Ramon Crehuet

Reputation: 4017

I think what you want to do can be optimized with numpy and scipy:

import numpy as np
import scipy.spatial.distance as distance
import matplotlib.pyplot as plt

points = np.random.random((6,2))
dists =distance.pdist(points)
m=np.argsort(distance.squareform(dists))[:,1:]
order = [0,m[0,0]]
next_point = order[-1]
while len(order)<len(points):
    row = m[next_point]
    i = 0
    while row[i] in order:
        i += 1
    order.append(row[i])
    next_point = order[-1]
order.append(0)
ordered=points[order]
plt.plot(ordered[:,0], ordered[:,1], 'o-')

The idea underlying this code is the following. First you calculate all the distances. Then you use argsort to get the indices that would order each row. You can remove the first column, as each point is closest to itself. We know that. Then you look which is the next closest point and you add it to the list order if the point is not there yet. You then go to the row corresponding to this point, and look for the next point. And so on.

If what you are only interested in is just sorting the enclosing set of points, you can use ConvexHull to find them:

ch = ConvexHull(points)
plt.plot(points[ch.vertices,0], points[ch.vertices,1], 'o-')

Upvotes: 1

mauve
mauve

Reputation: 2763

I don't know how I would do this in python 3.x, so please forgive changes that I have not made from python 2.7. You'll also want to figure out what point you'd like to start with: 

def find_distance(point1, point2):
    distance = sqrt(square(point1[0]-point2[0]) + square(point1[1] - point2[1]))
    return distance

x, y = getBorder('large.png', maxRes = 125)
points_in_border = [(i,j) for i, j in zip(x,y)] 
current_point = points_in_border.pop([0])
points_in_order = [current_point]


while len(points_in_border) > 0:
    min_distance = 10000
    for point in points_in_border:
        if find_distance(current_point, point) < min_distance:
            closest_point = point
            min_distance = find_distance(current_point, point)
     points_in_border.remove(closest_point)
     current_point = closest_point
     points_in_order.append(closest_point)

Upvotes: 1

jasonharper
jasonharper

Reputation: 9621

Well, point 644 cannot connect to point 620, because 620 is already part of your path.

As for why it connects to 645 instead of the closer 675: in your loop, you aren't actually remembering the index of the closest point, you're only remembering its x coordinate. After the loop, you then locate an arbitrary point with the same x coordinate - it could be anywhere on a vertical line going through the desired point.

Upvotes: 3

Related Questions