How to adjust a cloud point to meet the minimum distance requirement?

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?

[KSSV]

Do you have any code so far? It should be possible to achieve what you said. For precise help you need give more information on the problem.

[Yingao Zhang]

Not yet, I have developed the iteration based approach in Simulink using While Iterator Subsystem: Repeat subsystem execution during simulation time step while logical expression is true - Simulink (mathworks.com). However, since I'm deploying the algorithm for embedded targets, this approach turned out to be not fast enough to meet realtimeness. I'm wondering if you are familiar with Graph and Network Algorithms - MATLAB & Simulink (mathworks.com), and may help me with a matrix based approach without iteration.

Answer 1

[John D'Errico]

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.

[Yingao Zhang]

Hi, John, I guess my formulation of the question may have resulted in confusion for you. The problem here is not to locate the existing cluster as k-means clustering - MATLAB kmeans (mathworks.com) does, it is instead to de-cluster the point cloud such that no two points are within distance R to each other.

[John D'Errico]

If you know what the clusters are, AND which points are in each cluster, then just compute the smallest interpoint distance to each point in that cluster. Now contract the entire cluster by a factor, towards the center of said cluster.

For example, if

X = randn(100,2);

is one cluster, then use a tool like knnsearch to find the nearest point to every member of that cluster.

[idx,D] = knnsearch(X,X,'K',2);

So the closest point to any in cloud X is itself, and we want to find the distance to the SECOND closest point. The largest such distance is:

max(D(:,2))

ans = 1.2949

So I will now contract the cloud, such that the nearest neighbor is arbitrarily at a distance of 0.5.

newmaxdist = 0.5;
mu = mean(X,1);
Xcon = mu + (X - mu)*newmaxdist/max(D(:,2));

We can see the difference.

plot(X(:,1),X(:,2),'bo',Xcon(:,1),Xcon(:,2),'r.')

My guess is, you really want to do something subtly different, with some sort of nonlinear contraction, where points that are far out on the perimeter are moved in more closely. Clearly that will require carefully written code on your part. As clearly, that code does not exist in any form that I know of, but feel free to write it, and then if you are successful, I hope you may choose to post it on the File Exchange. My guess is you will find it a tricky thing to do in general, something that will require a great deal of iterative power, and one that probably has mutliple locally sub-optimal solutions. The final "optimal" solution might arguably be one that has the same number of points in some sort of spherical close packing.

If you wish to do this for many clusters in combination using some sort of scheme as you describe, again, feel free to write it. You will certainly not find some ready made tool that does what you want. Anyway, I'm not sure that you really do know exactly what you want, since you have only described an ad hoc, intuitive scheme. Trying to turn that into mathematics and worse, into code, is probably a nasty problem. But until you do manage to descibe exactly what you are looking for in mathematics, you cannot write code.

[Yingao Zhang]

Thanks, John, thank you so much for your detailed explanation. And I'm deeply sorry for the critical typo that I made in my comment to your first reply: "to de-cluster the point cloud such that NO two points are within distance R to each other". What I would like to do is nonlinear expansion instead of contraction. Let me give a concrete example here: Image there's a minimum distance threshold of 0.5, and see the first example on https://www.mathworks.com/help/stats/pdist.html, where the pairwise distance of three 2D points are computed:

Z = 3×3

         0    0.2954    1.0670
    0.2954         0    0.9448
    1.0670    0.9448         0

See here the edge distance (2,1) between point 1 and point 2 is only 0.2954 which doesn't meet the minimum distance requirement of 0.5, thus they have to be moved apart from each other by 0.5 - 0.2954 = 0.2046. To achieve this we can hold point 1 still and move point 2 only by 0.2046, or inversely by holding point 2 still, or move 50% for each point, namely by 0.2046/2 = 0.1023 for each. Then comes naturally the question of, what is the best percentage allocation?

The tricky part is that, for example, three points, A, B, and C, are on the same line on the 2D surface, with dist(A, B) = 0.2, dist(B, C) = 0.2, and dist(A, C) = 0.4. Under this occasion, since B is in the middle of A and C, we have to hold B still and compensate the deficiency of dist(A, B) by moving A only by another 0.5 - 0.2 = 0.3, the same for dist(B, C) with its deficiency compensated by the movement of C only.

The real-life application of this math problem is collision avoidance of swarm aerial robots. Using flight dynamics, I can predict where each drone will be in 5 seconds. Will they be too near to each other in 5 seconds? If so, I would compensate it by moving its expected command location in 5 seconds to be the output of the algorithm in question, with its no command flight dynamics prediction as input.

Returning back to the question above: what is the best percentage allocation? For moving point 1 and point 2 apart based on the https://www.mathworks.com/help/stats/pdist.html example above? Using the balloon analogy in the question itself, since the minimum distance threshold is 0.5, we image points 1, 2, and 3 are centers of three spherical balloons with a natural radius of 0.5/2 = 0.25. Since dist(1, 3) = 1.0670 > 0.5 and dist(2, 3) = 0.9448 > 0.5, balloon 3 is in contact with neither balloon 1 nor balloon 2, which make it out of worry. But, dist(1, 2) is only 0.2954, which means balloons 1 and 2 with 0.25 natural radius are squeezed together, which makes their center only 0.2954/2 = 0.1477 to their middle flat contact surface. How will balloons 1 and 2 move if the external force that squeezes them together now is gradually released? Since balloons 1 and 2 are not in contact with any third balloon, they will move each by (0.5 - 0.2954)/2 = 0.1023, which ends the two balloons in desired point contact with each other. However, what if there are balloons 3, 4, 5, 6, ..., that is all in initial squeezed surface contacts with each other?

I believe the mathematical solution to the question above that predicts the ballooning behavior will also be optimal for the drone swarm collision avoidance use. Since the deficiency in the inter-drone distance is alleviated by movements of all drones together, like the release of squeezed balloons, instead of the excessive movements of only several drones.