Ask Your Question

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

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

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

1 answer

Sort by ยป oldest newest most voted

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

Nghia gravatar image

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

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 only because I'm more familiar with it than FLANN.

edit flag offensive delete link more
Login/Signup to Answer

Question Tools


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

Seen: 689 times

Last updated: Sep 18 '12