0
$\begingroup$

I have a master point cloud, which essentially just a list of points with {x,y} coordinates.

The point cloud is HUGE ( like, it can contain more than 1 million points). The problem now is that I have another (sub)set of point clouds, and I need to check whether the points inside the second point clouds are the same with any of the points in the first point clouds, and then remove them from the list.

The characteristics of the second point cloud:

  1. The second point cloud points are usually clustered in a corner of the first point cloud ( but not always).
  2. None of the points from the second point cloud will lie outside of the first point cloud ( the first point cloud always contain every single point of the second point cloud)

The naive algorithm will be something like this:

   public static List<Point> FilterPoints(Lis<Point> master, List<Point> subset)
   {    
    var FilteredPoints = new List<Point>();    
    for(int i=0; i< subset.Count; i++) 
    {
        var isContained = false;
        for(int j=0; j< master.Count; j++)
        {
          if(subset[i].X==master[j].X && subject[i].Y==master[j].Y)
          {
              isContained = true;
              break;
          }
        }
        if(!isContained)
        {
           FilteredPoints.Add( master[i]);
        }   
      } 
     return FilteredPoints; 
}

But is there anyway to improve over the above naive algorithm in terms of speed, given the known characteristics of the both point clouds?

PS: I've also asked about how to make use of C# language characteristics( if any) in order to improve the speed for the above algorithm at SO.

$\endgroup$
  • $\begingroup$ Please do not post the same question on multiple sites. $\endgroup$ – D.W. Sep 18 at 9:40
  • $\begingroup$ @D.W., the question is different-- the emphasis is very different $\endgroup$ – Graviton Sep 18 at 10:30
  • $\begingroup$ I understand. But, I also notice that they are similar enough that you got two answers saying basically the same thing. Would the second poster have posted if they knew that someone else had already posted more or less the same answer? I don't know. This is one of the downsides of cross-posting; it risks wasting answerer's time. $\endgroup$ – D.W. Sep 18 at 14:30
2
$\begingroup$

You should use a set data structure for your subset-list. This would allow querying if it contains a given point in constant time.

Your function, as python-like pseudocode:

def FilterPoints(master, subset):
    # take the list and convert it to a set ( O(|subset|)
    subset_set = set(subset)
    # iterate through master and and the points that are not in subset O(|master|)
    filtered_list = [p for p in master if p not in subset_set]
    return filtered_list

Some points:

  • If master is larger than subset, the algorithm will be $\mathcal O(|master|)$
  • The equivalent of set in C# should be HashSet
$\endgroup$
2
$\begingroup$

If you really do want to test points for equality, then oerpli's solution is ideal. Any standard dictionary data structure will do the job.

However, for completeness, if you need to match points within some small distance (e.g. maybe these are floating point and you're reading one of them from an ASCII file where you can't guarantee precision), then you can use some kind of spatial index instead. Insert one set of points into the index, and then query it with the other set of points.

Something like k-d trees, quadtrees, or R-trees is probably easiest. If the coordinates are bounded, you could also use a space-filling curve approach such as geohash.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.