Closest plane to a point

Question

I'm working with a set of planes and a set of 3D points.

I want to find the closest plane to each one of the points in my set.

Right now I compute the disance of one point to each of the planes in my plane set and decide wich one is the closest, then I repeat the same process for every point in my point set. This works fine, but the computational cost depends a lot of the number of planes I have, so if I add more planes (usually I work with more than 500 planes) the processing time increase a lot.

Is there a more effcient way to know the closest plane to a point without having to compute the distance to each of the planes?

I'm implementing this using C++ and VTK libraries

The planes are precomputed using information from a 3D tracker and the points are defined by the user.

This block of code computes the point coordinates (voxel) and calls DistanceToPlane to calculate the distance from the voxel to all the planes. After running this the vnl_vector distances should have the closest plane to each point in the poin cloud.

vnl_vector<double> distances;

for(int i=0; i<volumeSize[0]; i++){

std::cout<<"."<<std::flush;

for(int j=0; j<volumeSize[1]; j++){
    for(int k=0; k<volumeSize[2]; k++){

        double voxel[3];
        voxel[0] = i*scale[0]*resolution + volumeOrigin[0];
        voxel[1] = j*scale[1]*resolution + volumeOrigin[1];
        voxel[2] = k*scale[1]*resolution + volumeOrigin[2];

        double distance = maxDistance;                          

        for(int plane=0; plane<volumeImageStack.size(); plane++){               

            double d = imagePlaneStack.at(plane)->DistanceToPlane(voxel);

            if(d<distance)
                 distance = d;

        }

        distances.push_back(distance);
}

The DistanceToPlane() function computes the distance from a point to one plane, this function is called N time (N = number of planes) for each point.This function is implemented in the VTK library.

Thanks

which part of the input changes? the points, planes, both, or none? if the planes are fixed, for example, than it might be worth using a data structure like their 3D arragement — killogre
How are your planes defined? Are you using homogeneous coordinates, two vectors, or a normal and a distance? And the title should change to closest plane to a point cloud. Finally, please show some code. — John Alexiou
Thanks for the response. All of the data changes, the planes are acquired using a 3D tracker hardware and the point set is defined by the user. The planes are defined by two vectors. I think the title should not change since I'm not looking for the closest plane to the point cloud, instead I'm trying to find the closest plane to ONE point inside a point cloud. I will add some code, thanks again — Fabian Torres

er453r er453r · Accepted Answer · 2018-07-14T19:40:03

UPDATE Updated the algorithm to work with any arbitrary planes

I was also looking for the solution to the exact same problem.

The solution requires a limited search space (min/max x/y/z). It is a 3D space partitioning data structure which you can query for closest planes more easily.

Pre-compute the partitioning data:

Divide the search space into X/Y/Z buckets (choose the size reasonably, eg. 1/20 of the the given dimension - this gives you 8000 buckets).
Now, to each each bucket we assign candidate planes to measure against if the point is inside this bucket.
1. First assign all the planes that intersect the bucket as candidates.
2. Now, for each plane that does not intersect the bucket, compute projections of the bucket corners (8 projections)
3. Now, for each such plane check if any other plane is between all the projections and the bucket (such plane is full covered by the other plane).
4. Now, add all planes that are not covered to the bucket candidates.

Now the query part. Given a point:

Find the bucket the point belongs to.
Query linearly only the candidate planes in the bucket.

To understand this algorithm better, try following it on paper for a 2D equivalent (a rectangle surrounded and intersected by multiple lines).

Checking only for corner projections guarantees that a projection of any point inside the bucket will also be contained inside the projection area. If all vertices of the area are covered, so is the entire area.

Closest plane to a point

1 Answers