Need an algorithmic idea


As I said … the idea is enough for now.

How to find and remove the minimum points from the cloud so that all the others are more than a given distance from each other?


I use the kdtree for this… keep adding points to the tree while they the fixed distance apart (you have to have an ‘attempts’ variable to stop it trying forever)


adjusting the min distance for 50,000 points

in pseudo code something like

    p = getpoint()
    tree.addpoint p

    while pcount < numpoints and attempts < max_attempts do
          p = getpoint()
          if not tree.within_range p mindist then
               tree.addpoint p
               pcount  += 1 
        else attempts += 1


KdTree was also the first thing that came to my mind … So instead of deleting, you add points from the list, creating a new one until it meets the distance criteria, right?

what is tree.within_range p mindist … is it not almost the same as addpoint?

(PS. For reference - the target cloud is about 50-100 K points)


I mean … it looks like it is possible to combine within_range and add_point in one pass, returning a succeed/failed for add_point?


But what worries me is that not necessarily the “most problematic” points will be eliminated first … or we will have to do several iterations, gradually increasing the minimum distance to what was originally needed.