# How to find the closest point in a Pointcloud to a given point?

Discussion in 'Scripting' started by maxOculavis, Nov 23, 2020.

1. ### maxOculavis

Joined:
Apr 27, 2018
Posts:
8
I'm currently tasked with visualizing a set of sampled measurements on the surface of an object.

I've got:
• the mesh
• a list of samplepoints (xyz coordinates and a measured value)
Currently, i want to find the closest samplepoint to each vertex and assign a color to that vertex based on the samplepoints measurement. What algorithm is suitable for this task?

The points are somewat ordered as in they are taken by the tooling machine, that slowly moves across the surface of the object.

2. ### Ray_Sovranti

Joined:
Oct 28, 2020
Posts:
172
Do you need the distance in actual space or the distance along the mesh surface? That is, If I put a samplepoint on side A of a disc-shaped mesh, should the vertices in the same spot on side B also react?

If you want the distance in actual space, then it's easy to loop through each point, check the distance to each, assign a reference if it's closer than the current closest point; and at the end of the loop, you have the closest point. Not especially efficient but very straightforward.

If it needs to be based on the distance across the mesh surface, then the algorithm will be more involved (though probably also more optimized I'd guess?). For sure you'd need to store or find the selected mesh triangle index and use that to build the desired information.

3. ### Bunny83

Joined:
Oct 18, 2010
Posts:
3,606
Well, how many "sample point" are we talking about? If it's just a "few", just iterate through them and find the closest one. If you have a lot of sample points you probably want to create a quadtree (for 2d) or an octree (for 3d) for your point cloud data to reduces the number of comparisons.

Just to put that into perspective. If you have less than 1000 points in your point cloud, it's probably not worth doing any optimisations unless you need to calculate this every frame. Also it would be great if you can express the number of sample points as a percentage of the number of point cloud data.

lordofduct likes this.
4. ### maxOculavis

Joined:
Apr 27, 2018
Posts:
8
Well the 'pointclod' if you will is 74 thousand points, where as the mesh has about 3k polygons.
And the distance is needed in actual space.
I basically need the cheapest way to colorize each vertex with based on the value of the point that is closest to that vertex.
Also, some vertices are "out of bounds", meaning the measurement tool never sampled the surface of the mesh at this point. Meaning that the closest Point hast to be within a certain range.

Edit: to all interested readers out there,
Since this is to be done ONCE for each pair of model and pointcloud,
you can divide the pointcloud into an easily searchable structure like an octree or sth.

Last edited: Nov 24, 2020
Bunny83 likes this.

Joined:
Sep 26, 2022
Posts:
1