生成3d随机点，并且它们之间的距离最短? [英] generate 3-d random points with minimum distance between each of them?
问题描述
有.我将用这个特殊字符在matlab中生成10 ^ 6个随机点.这些点应该在半径25的球体内，它们是3-D，所以我们有x，y，z或r，theta，phi.每个点之间有一个最小距离.首先，我决定生成点，然后检查距离，然后忽略不具有这些条件的点.但是，它可能会忽略很多要点.另一种方法是使用RSA(随机顺序加法)，这意味着以点与点之间的最小距离一一生成点.例如，生成第一个点，然后在距点1的最小距离之外随机生成第二个点，然后继续进行直到获得10 ^ 6点.但是要花很多时间，而且我无法达到10 ^ 6分，因为寻找合适的位置来寻找新点的速度会花费很长时间.
现在我正在使用此程序:
Nmax = 10000;R = 25；P = rand(1,3);k = 1;而k ＜Nmaxtheta = 2 * pi * rand(1);phi = pi * rand(1);r = R * sqrt(rand(1));％转换为笛卡尔x = r.* sin(θ).* cos(phi);y = r.*sinθ.* sin(phi);z = r.* cos(theta);P1 = [x y z];r = sqrt((x-0)^ 2 +(y-0)^ 2 +(z-0)^ 2);D = pdist2(P1，P，'欧几里得');欧氏距离％如果D＞ 0.146 * r ^(2/3)P = [P; P1];k = k + 1;结尾i = i + 1;结尾x = P(:，1); y = P(:，2); z = P(:，3);plot3(x，y，z，'.'); 如何在这些条件下有效地生成点?谢谢.
我仔细研究了您的算法，得出的结论是，它永远无法奏效-至少如果您真的想获得一百万分，那至少不会奏效.那个领域.有一张简单的图片说明了为什么不这样做-这是您需要测试(使用RSA的技术)要获得一个额外的好"点的点数的图表.如您所见，这仅在几千个点上渐近(我针对20万个点运行了一个稍快的算法来生成该点):
我不知道您是否曾经尝试过计算出理想排列的点的理论数量，但是我开始怀疑这个数量是否比1E6小很多./p>
我用来调查此问题的完整代码及其生成的输出，可以找到这里.我从来没有达到我先前回答中所描述的技术……您描述的设置中还有太多其他事情要做.
我开始认为，即使采用完美"的安排，也有可能无法达到1M点.我为自己创建了一个简单的模型，如下所示:
想象一下，从外壳"(r = 25)开始，并尝试以相等的距离拟合点.如果将外壳"的面积除以一个排除磁盘"的面积(半径为r_sub_crit)，则可以得出该距离处的点数的(较高)估计值:
numpoints = 4 * pi * r ^ 2//(pi *(0.146 * r ^(2/3))^ 2)〜188 * r ^(2/3) 下一个壳"的半径应小0.146 * r ^(2/3)-但是，如果您认为这些点布置得很仔细，则可能会稍微靠近一点.再次，让我们大方一些，说壳可以比标准小1/sqrt(3).然后，您可以使用简单的python脚本从外壳开始并按自己的方式进行操作:
将scipy导入为scr = 25npts = 0def rc(r):返回0.146 * sc.power(r，2./3.)而(r> rc(r)):morePts = sc.floor(4/(0.146 * 0.146)* sc.power(r，2./3.))npts = npts +更多分打印更多点，'在r ='处有更多点，rr = r-rc(r)/sc.sqrt(3)打印球体中拟合的总点数:"，npts 此输出为:
在r = 25时有1604.0个点r时增加1573.0点= 24.2793037966r = 23.5725257555时增加1542.0点r上更多1512.0点= 22.8795314897r = 22.2001865995时增加1482.0点r = 21.5343566722时多出1452.0点r = 20.8819072818时增加1422.0点r上的1393.0个其他点= 20.2427039885r上的1364.0个其他点= 19.6166123391r时多1336.0点积分= 19.0034978659r = 18.4032260869时多1308.0点r = 17.8156625053，另加1280.0点r = 17.2406726094时多出1252.0点r时多1224.0点积分= 16.6781218719r上的1197.0点其他点= 16.1278757499r时多1171.0点积分= 15.5897996844r处增加1144.0点= 15.0637590998r时增加1118.0点= 14.5496194041092.0个点在r = 14.0472459873r = 13.5565042228时增加1066.0点r上的1041.0个其他点= 13.0772594652r = 12.6093770509时增加1016.0点r = 12.1527222975时增加了991.0点r = 11.707160503时可多获得967.0点r处943.0个额外的积分= 11.2725569457r时增加919.0点= 10.8487768835r = 10.4356855535时增加896.0分r = 10.0331481711时增加了872.0点r时多850.0点= 9.64102993012r = 9.25919600154时增加827.0点r时805.0个其他点= 8.88751153329r时多783.0点= 8.52584164948r时增加761.0点= 8.17405144976r = 7.83200600865时增加740.0点r = 7.49957037478时增加718.0点r = 7.17660957023时增加698.0点r时多677.0点= 6.86298858965r时多657.0点= 6.55857239952r时多637.0点= 6.26322593726r = 5.97681411037时增加618.0点r时多598.0点= 5.69920179546r = 5.43025383729时增加了579.0点r = 5.16983504778时增加561.0点r时多542.0点= 4.91781020487r时多524.0点= 4.67404405146r时增加506.0点= 4.43840129415r = 4.21074660206时增加489.0点r = 3.9909446055时增加472.0点r时多455.0分= 3.77885989456r = 3.57435701766时增加了438.0点r = 3.37730048004时又增加了422.0个点r = 3.1875547421时增加406.0点r上的390.0个其他点= 3.00498421767r时多375.0点= 2.82945327223r = 2.66082622092时增加360.0点r = 2.49896732654时增加345.0点r = 2.34374079733时增加331.0点r时多316.0点= 2.19501078464r时多303.0点= 2.05264138052r = 1.91649661498下的289.0个其他点r = 1.78644045325时多276.0分r时多263.0点= 1.66233679273r时多250.0点= 1.54404945973r = 1.43144220603时增加了238.0点r = 1.32437870508时增加了226.0点r = 1.22272254805时多214.0点r = 1.1263372394时增加了203.0点r = 1.03508619218时多192.0点r = 0.94883272297时增加181.0点r = 0.867440046252时增加了170.0点r = 0.790771268402时增加160.0点r = 0.718689381062时增加了150.0点r = 0.65105725389时增加140.0点r = 0.587737626612时多131.0分r = 0.528593100237时增加了122.0点r时多113.0点= 0.473486127367r = 0.422279001431时增加105.0分r = 0.374833844693时增加97.0分r = 0.331012594847时还多了89.0分r = 0.290676989951时还有82.0点r时多75.0点= 0.253688551418r = 0.219908564725时增加68.0点r = 0.189198057381时增加61.0点r = 0.161417773651时增加了55.0点r = 0.136428145311时还有49.0点r = 0.114089257597时增加44.0点r = 0.0942608092113时可获得38.0分r = 0.0768020649149时增加33.0点r = 0.0615717987589时增加29.0分r = 0.0484282253244时还有24.0个点r = 0.0372289153633时增加20.0点r = 0.0278306908104时增加17.0分r = 0.0200894920319时增加13.0点r = 0.013860207063时增加10.0点r时增加8.0分= 0.00899644813842r时5.0个其他点= 0.00535025545232球体内拟合的总点数:55600.0 这似乎可以证明，无论您如何尝试，您确实都无法达到一百万...
there. I am going to generate 10^6 random points in matlab with this particular characters. the points should be inside a sphere with radious 25, the are 3-D so we have x, y, z or r, theta, phi. there is a minimum distance between each points. first, i decided to generate points and then check the distances, then omit points with do not have these condition. but, it may omit many of points. another way is to use RSA (Random Sequential Addition), it means generate points one by one with this minimum distance between them. for example generate first point, then generate second randomly out of the minimum distance from point 1. and go on till achieving 10^6 points. but it takes lots of time and i can not reach 10^6 points, since the speed of searching appropriate position for new points will take long time.
Right now I am using this program:
Nmax=10000;
R=25;
P=rand(1,3);
k=1;
while k<Nmax
theta=2*pi*rand(1);
phi=pi*rand(1);
r = R*sqrt(rand(1));
% convert to cartesian
x=r.*sin(theta).*cos(phi);
y=r.*sin(theta).*sin(phi);
z=r.*cos(theta);
P1=[x y z];
r=sqrt((x-0)^2+(y-0)^2+(z-0)^2);
D = pdist2(P1,P,'euclidean');
% euclidean distance
if D>0.146*r^(2/3)
P=[P;P1];
k=k+1;
end
i=i+1;
end
x=P(:,1);y=P(:,2);z=P(:,3); plot3(x,y,z,'.');
How can I efficiently generate points by these condition? thank you.
I took a closer look at your algorithm, and concluded there is NO WAY it will ever work - at least not if you really want to get a million points in that sphere. There is a simple picture that explains why not - this is a plot of the number of points that you need to test (using your technique of RSA) to get one additional "good" point. As you can see, this goes asymptotic at just a few thousand points (I ran a slightly faster algorithm against 200k points to produce this):
I don't know if you ever tried to compute the theoretical number of points you could fit in your sphere when you have them perfectly arranged, but I'm beginning to suspect the number is a good deal smaller than 1E6.
The complete code I used to investigate this, plus the output it generated, can be found here. I never got as far as the technique I described in my earlier answer... there was just too much else going on in the setup you described.
EDIT: I started to think it might not be possible, even with "perfect" arrangement, to get to 1M points. I made a simple model for myself as follows:
Imagine you start on the "outer shell" (r=25), and try to fit points at equal distances. If you divide the area of the "shell" by the area of one "exclusion disk" (of radius r_sub_crit), you get a (high) estimate of the number of points at that distance:
numpoints = 4*pi*r^2 / (pi*(0.146 * r^(2/3))^2) ~ 188 * r^(2/3)
The next "shell" in should be at a radius that is 0.146*r^(2/3) less - but if you think of the points as being very carefully arranged, you might be able to get a tiny bit closer. Again, let's be generous and say the shells can be just 1/sqrt(3) closer than the criteria. You can then start at the outer shell and work your way in, using a simple python script:
import scipy as sc
r = 25
npts = 0
def rc(r):
return 0.146*sc.power(r, 2./3.)
while (r > rc(r)):
morePts = sc.floor(4/(0.146*0.146)*sc.power(r, 2./3.))
npts = npts + morePts
print morePts, ' more points at r = ', r
r = r - rc(r)/sc.sqrt(3)
print 'total number of points fitted in sphere: ', npts
The output of this is:
1604.0 more points at r = 25
1573.0 more points at r = 24.2793037966
1542.0 more points at r = 23.5725257555
1512.0 more points at r = 22.8795314897
1482.0 more points at r = 22.2001865995
1452.0 more points at r = 21.5343566722
1422.0 more points at r = 20.8819072818
1393.0 more points at r = 20.2427039885
1364.0 more points at r = 19.6166123391
1336.0 more points at r = 19.0034978659
1308.0 more points at r = 18.4032260869
1280.0 more points at r = 17.8156625053
1252.0 more points at r = 17.2406726094
1224.0 more points at r = 16.6781218719
1197.0 more points at r = 16.1278757499
1171.0 more points at r = 15.5897996844
1144.0 more points at r = 15.0637590998
1118.0 more points at r = 14.549619404
1092.0 more points at r = 14.0472459873
1066.0 more points at r = 13.5565042228
1041.0 more points at r = 13.0772594652
1016.0 more points at r = 12.6093770509
991.0 more points at r = 12.1527222975
967.0 more points at r = 11.707160503
943.0 more points at r = 11.2725569457
919.0 more points at r = 10.8487768835
896.0 more points at r = 10.4356855535
872.0 more points at r = 10.0331481711
850.0 more points at r = 9.64102993012
827.0 more points at r = 9.25919600154
805.0 more points at r = 8.88751153329
783.0 more points at r = 8.52584164948
761.0 more points at r = 8.17405144976
740.0 more points at r = 7.83200600865
718.0 more points at r = 7.49957037478
698.0 more points at r = 7.17660957023
677.0 more points at r = 6.86298858965
657.0 more points at r = 6.55857239952
637.0 more points at r = 6.26322593726
618.0 more points at r = 5.97681411037
598.0 more points at r = 5.69920179546
579.0 more points at r = 5.43025383729
561.0 more points at r = 5.16983504778
542.0 more points at r = 4.91781020487
524.0 more points at r = 4.67404405146
506.0 more points at r = 4.43840129415
489.0 more points at r = 4.21074660206
472.0 more points at r = 3.9909446055
455.0 more points at r = 3.77885989456
438.0 more points at r = 3.57435701766
422.0 more points at r = 3.37730048004
406.0 more points at r = 3.1875547421
390.0 more points at r = 3.00498421767
375.0 more points at r = 2.82945327223
360.0 more points at r = 2.66082622092
345.0 more points at r = 2.49896732654
331.0 more points at r = 2.34374079733
316.0 more points at r = 2.19501078464
303.0 more points at r = 2.05264138052
289.0 more points at r = 1.91649661498
276.0 more points at r = 1.78644045325
263.0 more points at r = 1.66233679273
250.0 more points at r = 1.54404945973
238.0 more points at r = 1.43144220603
226.0 more points at r = 1.32437870508
214.0 more points at r = 1.22272254805
203.0 more points at r = 1.1263372394
192.0 more points at r = 1.03508619218
181.0 more points at r = 0.94883272297
170.0 more points at r = 0.867440046252
160.0 more points at r = 0.790771268402
150.0 more points at r = 0.718689381062
140.0 more points at r = 0.65105725389
131.0 more points at r = 0.587737626612
122.0 more points at r = 0.528593100237
113.0 more points at r = 0.473486127367
105.0 more points at r = 0.422279001431
97.0 more points at r = 0.374833844693
89.0 more points at r = 0.331012594847
82.0 more points at r = 0.290676989951
75.0 more points at r = 0.253688551418
68.0 more points at r = 0.219908564725
61.0 more points at r = 0.189198057381
55.0 more points at r = 0.161417773651
49.0 more points at r = 0.136428145311
44.0 more points at r = 0.114089257597
38.0 more points at r = 0.0942608092113
33.0 more points at r = 0.0768020649149
29.0 more points at r = 0.0615717987589
24.0 more points at r = 0.0484282253244
20.0 more points at r = 0.0372289153633
17.0 more points at r = 0.0278306908104
13.0 more points at r = 0.0200894920319
10.0 more points at r = 0.013860207063
8.0 more points at r = 0.00899644813842
5.0 more points at r = 0.00535025545232
total number of points fitted in sphere: 55600.0
This seems to confirm that you really can't get to a million, no matter how you try...
这篇关于生成3d随机点，并且它们之间的距离最短?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
