Ask Your Question
1

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

asked 2012-09-18 04:49:26 -0600

Rui Marques gravatar image

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 flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
2

answered 2012-09-18 05:02:54 -0600

Nghia gravatar image

updated 2012-09-18 05:07:06 -0600

Rui Marques gravatar image

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.

edit flag offensive delete link more
0

answered 2019-07-12 03:27:38 -0600

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.

edit flag offensive delete link more

Question Tools

Stats

Asked: 2012-09-18 04:49:26 -0600

Seen: 2,990 times

Last updated: Sep 18 '12