How to adjust a cloud point to meet the minimum distance requirement?
1 回表示 (過去 30 日間)
古いコメントを表示
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 件のコメント
KSSV
2021 年 11 月 15 日
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.
回答 (1 件)
John D'Errico
2021 年 11 月 15 日
編集済み: John D'Errico
2021 年 11 月 15 日
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 件のコメント
John D'Errico
2021 年 11 月 15 日
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))
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.
参考
カテゴリ
Help Center および File Exchange で Labeling, Segmentation, and Detection についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!