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

edit

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.

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.