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?
  2 Comments
Yingao Zhang
Yingao Zhang on 15 Nov 2021
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.

Sign in to comment.

Answers (1)

John D'Errico
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.
  3 Comments
Yingao Zhang
Yingao Zhang on 15 Nov 2021
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.

Sign in to comment.

Categories

Products


Release

R2021b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by