# How to efficiently filter out points geometrically close to each other?

I have a list of points from an image, and I have a method to measure the distance between two points.

Is there a more efficient way - than the naive approach - to remove points from that list that are too close (the 2D coordinates) to each other?

I wouldn't like to remove them all, if I had 4 points which were close, I would choose one point to keep and remove the other 3.

edit retag close merge delete

Sort by » oldest newest most voted

I assume the "naive" approach you're talking about is O(N^2), that is comparing each point in list A to list B. If you use a KD-tree like structure it'll run close to O(logN). OpenCV has a wrapper around FLANN, which does this. Another library that I use frequently for these tasks is libANN from http://www.cs.umd.edu/~mount/ANN only because I'm more familiar with it than FLANN.

more

I am assuming that you have all the points as a list, say, [[11,20],[22,30],[57,60],[10,21]] and want to get rid of [11,21].

We write two functions in order to remove the points which are close together.

def not_satisfy2(a,k,critical):
flag=False
cx2,cy2 = k
for i in a:
cx1,cy1 = i
if(abs(cx1-cx2) < critical and abs(cy1-cy2) < critical):
flag=True
break
return flag


This function is a helper function for the below function.

def edit_list(a,length_of_a,critical):
l = []
l.append(a[0])
i=1
while(i < length_of_a):
if(not_satisfy2(l,a[i],critical)==True):
i+=1
else:
l.append(a[i])
i+=1

return l


So, basically what it does is for every candidate to be added to the edited list L, it checks if there is a point already present in the vicinity of the new candidate. If that is the case, it ignores the point and moves forward without appending it to the list. If there is no point in the vicinity of the new candidate, it appends the point to the new list.

You can set the distance below which you define points to be "too close" using the parameter critical.

more

Official site

GitHub

Wiki

Documentation