5

Let's say I have two different pcl::PointCloud<pcl::PointXYZL> (altough the point type doesn't really matters), c1 and c2.

I'd like to find the intersection of these two pointclouds. By intersection I mean the pointcloud inter constructed such that a point pi from c1 is inserted in inter if (and only if) a point pj exists in c2 and

pi.x == pj.x && pi.y == pj.y && pi.z == pj.z

At the moment I'm using the following functions to achieve this:

#include <pcl/point_cloud.h>
#include <pcl/point_types.h>

using namespace pcl;

typedef PointXYZL PointLT;
typedef PointCloud<PointLT> PointLCloudT;

bool contains(PointLCloudT::Ptr c, PointLT p) {
    PointLCloudT::iterator it = c->begin();
    for (; it != c->end(); ++it) {
        if (it->x == p.x && it->y == p.y && it->z == p.z)
            return true;
    }
    return false;
}

PointLCloudT::Ptr intersection(PointLCloudT::Ptr c1,
        PointLCloudT::Ptr c2) {
    PointLCloudT::Ptr inter;
    PointLCloudT::iterator it = c1->begin();
    for (; it != c1->end(); ++it) {
        if (contains(c2, *it))
            inter->push_back(*it);
    }

    return inter;
}

I'd like to know if there's a standard (and possibly more efficient) way of doing this?

I haven't found anything about this in the official documentation, but maybe I'm missing something.

Thank you.

2 Answers 2

4

If you're only looking for exact matches, as opposed to approximate matches, you can simply put the points from each point cloud in a std::vector, sort it, then use std::set_intersection to identify the matches.

3
  • Thank you. My only concern about this approach is that they might have different labels, so the vectors should contain only the three spatial coordinates to be correctly compared. Doing so, I lose the label information and I have to retrieve it back in the original pointcloud, going through all the points again I guess. Jul 15, 2015 at 9:50
  • 1
    The vectors can contain original point data. You need to use a custom comparator that only uses coordinates and ignores the labels. Jul 15, 2015 at 9:55
  • That seems appropriate... I'll have a look into it, thanks! Jul 15, 2015 at 14:48
1

This search for points in your contains function can be made a bit more efficient by using an efficient data structure like KD Tree.

Another alternative is to do better bookkeeping earlier in your pipeline, but we would need to know more about what you are trying to achieve at a high level to help you with that.

Edit: As pointed out in the comments, KD Tree is good for approximate spatial searches but the asker wants to do exact point matches. For this a hash table (or some other basic search data structure) may be more efficient.

5
  • It would speed things up, but it would be overkill. A kD-tree isn't a good structure for exact point queries. It's designed for approximate point queries.
    – Sneftel
    Jul 15, 2015 at 14:21
  • My high level task is to compare a segmentation of a pointcloud (computed by an algorithm we are researching) with a given ground truth segmentation. Jul 15, 2015 at 14:47
  • 1
    @FrancescoV. Don't want to stray too far from the original implementation, but if you're segmenting into more than two segments -- and especially if the segments do not have prior associations with segments from ground truth -- you should consider more formalized and powerful statistical methods of measuring divergence. In particular, en.wikipedia.org/wiki/Variation_of_information .
    – Sneftel
    Jul 15, 2015 at 14:55
  • You're right, Sneftel. A hash would be more straightforward and faster.
    – D.J.Duff
    Jul 16, 2015 at 0:00
  • I'm computing VOI as well, but I would like to evaluate also Precision and Recall (and F-score); for those I'll need the intersection. Jul 16, 2015 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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