Create unique identifier from close coordinates

Question

Suppose that I have the following list of coordinates:

[(35.0, 811.0), (37, 820), (66, 80), (88.0, 674.0), (97, 343), (98, 343), (126, 984), (132.0, 784.0), (133.0, 457.0), (165.0, 481.0), (193, 92), (206, 645), (206, 646), (256, 409), (304, 255), (305, 255), (360, 889), (456.0, 689.0), (500, 147), (501, 147), (528.0, 822.0), (536, 483), (536, 509), (542, 872), (560, 512), (605, 755), (605, 756), (663, 144), (664, 144), (727.0, 426.0)]

These coordinates are the centeroid of some shapes, and some of them are very close (different in x or y) like (304, 255), (305, 255). All I want to do is categorizing such coordinates in one set. And for that aim I want to create a unique identifier from this points.

First of all you might think about subtraction or multiplication or pow or etc. but since there is a lot of coordinate in my array and some of them might have same result for aforementioned operations I can't use this trick.

So the question is that, is there any mathematical solution for this task? so that I can create a unique identifier for (304, 255) and (305, 255) ?

PS. I'm using python programming language and Numpy.

Answer 1

I found a solution which I think works in this case. Since all this close coordinates are different in unity part like 140 and 139 we can subtract 9 from this numbers and get the round then it would be a unique number for each of them:

>>> lst = [(35.0, 811.0), (37, 820), (66, 80), (88.0, 674.0), (97, 343), (98, 343), (126, 984), (132.0, 784.0), (133.0, 457.0), (165.0, 481.0), (193, 92), (206, 645), (206, 646), (256, 409), (304, 255), (305, 255), (360, 889), (456.0, 689.0), (500, 147), (501, 147), (528.0, 822.0), (536, 483), (536, 509), (542, 872), (560, 512), (605, 755), (605, 756), (663, 144), (664, 144), (727.0, 426.0)]

>>> [(round((i-9)/10),round((j-9)/10)) for i,j in lst]
[(3.0, 80.0), (2.0, 81.0), (5.0, 7.0), (8.0, 67.0), (8.0, 33.0), (8.0, 33.0), (11.0, 97.0), (12.0, 78.0), (12.0, 45.0), (16.0, 47.0), (18.0, 8.0), (19.0, 63.0), (19.0, 63.0), (24.0, 40.0), (29.0, 24.0), (29.0, 24.0), (35.0, 88.0), (45.0, 68.0), (49.0, 13.0), (49.0, 13.0), (52.0, 81.0), (52.0, 47.0), (52.0, 50.0), (53.0, 86.0), (55.0, 50.0), (59.0, 74.0), (59.0, 74.0), (65.0, 13.0), (65.0, 13.0), (72.0, 42.0)]
>>> 

We can use set function to preserve the uniuqe items :

>>> set([(round((i-9)/10),round((j-9)/10)) for i,j in lst])
set([(35.0, 88.0), (19.0, 63.0), (12.0, 78.0), (65.0, 13.0), (72.0, 42.0), (59.0, 74.0), (11.0, 97.0), (16.0, 47.0), (18.0, 8.0), (2.0, 81.0), (8.0, 67.0), (53.0, 86.0), (12.0, 45.0), (52.0, 50.0), (8.0, 33.0), (24.0, 40.0), (45.0, 68.0), (5.0, 7.0), (29.0, 24.0), (3.0, 80.0), (49.0, 13.0), (52.0, 47.0), (52.0, 81.0), (55.0, 50.0)])

As we can see one of the close coordinates has gone. And we can categorize them by passing the aforementioned formula as the key to itertools.groupby function:

>>> from itertools import groupby
>>> 
>>> [list(g) for _,g in groupby(lst , key = lambda x: (round((x[0]-9)/10),round((x[1]-9)/10)))]
[
[(35.0, 811.0)],
[(37, 820)],
[(66, 80)],
[(88.0, 674.0)],
[(97, 343), (98, 343)],
[(126, 984)], 
[(132.0, 784.0)],
[(133.0, 457.0)],
[(165.0, 481.0)],
[(193, 92)],
[(206, 645), (206, 646)],
[(256, 409)],
[(304, 255), (305, 255)],
[(360, 889)],
[(456.0, 689.0)],
[(500, 147), (501, 147)],
[(528.0, 822.0)],
[(536, 483)],
[(536, 509)],
[(542, 872)], 
[(560, 512)],
[(605, 755), (605, 756)],
[(663, 144), (664, 144)],
[(727.0, 426.0)]]

Answer 2

I suppose the coordinates have their own practical limits here in terms of range. If they do, a simple function can generate a unique number for each coordinate, essentially mapping the 2 dimensional coordiantes into one dimension.

#!/usr/bin/python3

min_x = 0
max_x = 10
coords = [(5,5),(8,9),(4,5),(3,2)]

def coord_to_hash(x,y):
    return (y * (max_x - min_x)) + x

for c in coords:
    print(coord_to_hash(c[0],c[1]));

The mapping looks like this: