Ordered coordinates

Question

I have a list of 2D unordered coordinates :

How could I find the corresponding row and column for each points? My points are not perfect and small rotation can exist. I'm looking at Opencv findCirclesGrid code but I did not find ordering algorithm.

EDIT: @armatita solution work with set of data but when coordinate have rotation 7°

data = array([[ 95, 146],[72,143],[92,169],[98,123],[75,120],[69,166],[49,140],[89,192],[115,172],[46,163],[52,117],[66,189],[112,194],[121,126],[123,103],[101,100],[78,97],[141,152],[86,215],[138,175]])

def find(arr,threshold):
    rmin = sys.maxint
    for i in range(len(arr)):
        for j in range(i+1,len(arr)):
            diff = abs( arr[i] - arr[j] )
            if diff > threshold and diff < rmin:
                rmin = diff
    return rmin
            
threshold = 10
space = np.array([ find(data[:,0],threshold), find(data[:,1],threshold) ], dtype=np.float32)
print "space=",space
first = np.min(data,axis=0)

order = np.around( ( data - first ) / space )

plt.scatter(data[:,1], data[:,0],c=range(len(data)),cmap="ocean")
for pt in zip(order,data):
    c, rc = ( pt[1], pt[0] )
    plt.text( c[1], c[0]+5, "[%d,%d]" % (rc[1],rc[0]),color='black')
plt.show()

Problem come from space calculation

Surely if you have the coordinates then they are the row and column? You also mention a small rotation, what do you mean by that? Surely a point has no rotation. — timlyo, Mar 17 '16 at 15:45
I think he means the data is not always spaced at constant steps. It has minor changes so you need to give a tolerance. — armatita, Mar 17 '16 at 15:52
Yes this works with rotation because you can rotate your data to fit a regular grid space. You don't need to keep the rotated data, you just need to see in what cell it would be if it was rotated. See: https://en.wikipedia.org/wiki/Rotation_matrix And by the way: editing your post is bad way to ask me a question since I'm not warned everytime you edit your post. — armatita, Mar 18 '16 at 19:13
How to I can derterminate rotation ? My image processing give me juste coordinate list — themadmax, Mar 19 '16 at 17:07

score 2 · Answer 1 · answered Mar 17 '16 at 15:50

2

By putting them inside a pseudo regular grid:

    c = [[ 95, 146],[118, 146],[ 95, 169],[ 95, 123],[ 72, 146],[118, 169],
         [118, 123],[141, 146],[ 95, 100],[ 72 ,123] ,[ 95 ,192],[ 72 ,169]
         ,[141 ,169],[118 ,100],[141 ,123],[ 72 ,100],[ 95 , 77],[118 ,192]
         ,[ 49 ,146],[ 48 ,169]]

    nodesx = 100
    sizex = 20
    sizey = 20
    firstx = 70
    firsty = 40

    new,xt,yt = [],[],[]
    for i in c:
        xo = int((i[0]-firstx)/sizex)
        yo = int((i[1]-firsty)/sizey)
        new.append(nodesx*yo+xo)
        xt.append(i[0])
        yt.append(i[1])

    sortedc = [x for (y,x) in sorted(zip(new,c))]

    import matplotlib.pyplot as plt
    plt.scatter(xt,yt)
    for i in range(len(sortedc)):
        plt.text(sortedc[i][0],sortedc[i][1],str(i))
    plt.show()

,which will result in this (do tell if you don't understand the logic):

answered Mar 17 '16 at 15:50

armatita

12,825
8
48
49

Great! To find firstx and firsty is easy but how to determinate sizex, sizey it can be different to each data set. – themadmax Mar 17 '16 at 16:00
I just realized I've swapped x,y coordinates compared to the poster plot. To solve that just swap the inputs in the plt.scatter and plt.text functions. – armatita Mar 17 '16 at 16:00
Typically to be safe just calculate the distance between all points of a set (distance in x for size x, and distance in y for size y) and select sizes that are smaller than the minimum (minimum distances evidently). – armatita Mar 17 '16 at 16:01
@themadmax It's important to accept answers when they've helped you solve your problem. It shows you appreciate the effort others put into helping you as well show other users the (or a) solution to the problem you have stated. SO is unnecessarily filled with pseudo unanswered questions because OP seem to forget to accept the answers that are given. – armatita Apr 11 '16 at 12:19

score 0 · Answer 2 · edited May 23 '17 at 12:15

0

If you want to sort by the x axis then take your list of coordinate pairs and use sort

>>> a = [(5, 3), (3, 6), (1, 10), (1, 5)]
>>> a.sort()
>>> print a
[(1, 5), (1, 10), (3, 6), (5, 3)]

If you want to sort based on the y co-ordinate, the you can look here Sort tuples based on second parameter

Once you have the sorted list

If you want to check for a minimum delta and merge them

calculate distance of each pair, if within delta merge them. (for example calculate new point as average of the two points)

If a merge happens, distance to next co-ordinate is calculated from merged co-ordinate pair.

Repeat until no change in list.

Sort by y co-ordinate and repeat the merge.

Once both sets of merges are complete you should be left with a valid set of points.

All points within delta of each other will have been merged.

edited May 23 '17 at 12:15

Community

1
1

answered Mar 17 '16 at 15:43

sabbahillel

4,357
1
19
36

Ok, but how I can merge all x for the same column ? in my case all x are not the same. K-nearest neighbours algorithm can merge but I don't known number of column. – themadmax Mar 17 '16 at 15:55
@themadmax I am not sure what you mean by merge. What do you want to do with the ordered list after you have it? – sabbahillel Mar 17 '16 at 16:11
@themadmax I added a description of the method to merge the points within a specified delta of each other. – sabbahillel Mar 17 '16 at 16:23

Ordered coordinates

2 Answers2