How to adjust a cloud point to meet the minimum distance requirement?
6 views (last 30 days)
Given a 3D point cloud with many dense local clusters, how can it be adjusted such that these local clusters are expanded in a way to meet the minimum inter-point distance requirement? An "artificial-potential"-based algorithm that introduces repulsive "forces" between points could surely solve the problem with iteration towards time infinity, however, does there exist any analytical solution that enables one-shot computation to increase solution speed? An intuitive description of the problem could be formulated as follows: Given the required minimum inter-point distance R, imagine that each point in the cloud represents the center of a spherical balloon with radius R/2, and some balloons are initially squeezed together such that their contact surface deforms to be locally flat instead of spherical. How will the balloons move when the initial external pressure is gently removed, such that all originally compressed balloons end up in point-touch with each other?
John D'Errico on 15 Nov 2021
Edited: John D'Errico on 15 Nov 2021
Sorry, but no. There is no analytical solution that would provide the clustering that you wish to achieve. You can use clustering tools like kmeans to do so, but these are typically iterative methods, and will rely on you telling the tool how many such clusters to expect. As well, they will typically require starting estimates for the centers of the clusters.
There are mutliple variations of clustering algorithms, all iterative. They use various schemes for inter-point distance computations, etc. Look at the stats toolbox tool kmeans. While you could write your own code, this is not at all a good idea, since people have been developing clustering algorithms for many years now. I recall seeing talks on the topic from 40 years ago.