CODEWITHSUNDEEP
point-clouds
mirella melo
mirella melo

Reputation: 81

Removing points from one PCL to another in an efficient way

There are similar questions, but my main concern here is regarding processing time.

I have two PCL, both of type pcl::PointXYZL, this is, there is a label/id info together with each point. I want to remove in PC B all the points existent in A (recognized by the label info).

An iteration of this type takes too much time.

I decide to save the labels from PC A into boost::container::flat_set<int> labels, and set cloud B as std::map<int, pcl::PointXYZL> cloud_B, where the key is the label/id from the point. Then I do:

    for(boost::container::flat_set<int>::iterator it = labels.begin() ; it != labels.end(); ++it){
        if ( auto point{ cloud_B.find( *it ) }; point != std::end(cloud_B)){
            cloud_B.erase(*it);
        }
    }

It is now much much faster, but honestly, I think there may have a more efficient solution.

I also try:

   for(boost::container::flat_set<int>::iterator it = labels.begin() ; it != labels.end(); ++it){
        try{
            cloud_B.erase(*it);
            throw 505;
        }
        catch (...){
            continue;
        }
    }

But it takes more time than the first example I brought.

I appreciated any help with this!

Upvotes: 1

Views: 925

Answers (2)

mirella melo
mirella melo

Reputation: 81

This is my solution so far...

First, I set both clouds as type std::map<int, pcl::PointXYZL>. Remembering that I want to remove from cloud_B all points that are in cloud_A. Then:

std::map<int, pcl::PointXYZL>::iterator it = cloud_B.begin();
for ( ; it != cloud_B.end(); ){
   if (auto point{ cloud_A.find(it->first) }; point != std::end(cloud_A)){ // if the label was found
       it = cloud_B.erase(it);
   }
   else
       ++it;
}

Upvotes: 0

Ardiya
Ardiya

Reputation: 725

Both of your solution are roughly O(n^2) complexity.

Use unordered_set<std::uint32_t> to check if it exist or not. the average case of unordered_set<std::uint32_t>::count is constant, so it should be better than your solution

Sample code(untested) but you get the rough idea.

pcl::PointCloud<pcl::PointXYZL> cloud_a;
pcl::PointCloud<pcl::PointXYZL> cloud_b;

... (fill cloud)

// generate unordered_set<uint32_t> O(n)
std::unordered_set<std::uint32_t> labels_in_cloud_a;
for (int i = 0; i < cloud_a.size(); ++i) {
  labels_in_cloud_a.insert(cloud_a.points[i].label);
}

// indices where in cloud_b where label doesn't exist in labels_in_clouda O(n*1) = O(n)
std::vector<int> indices;
for (int i = 0; i < cloud_b.size(); ++i) {
  if (labels_in_cloud_a.count(cloud_b.points[i].label) == 0) {
    indices.push_back(i);
  }
}

// only indices that doesn't exist in cloud_a will remain. O(n)
pcl::copyPointCloud(cloud_b, indices, cloud_b);

Upvotes: 1

Related Questions