如何生成每个点之间距离最小的 3 维随机点？

Question

我将在 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; 
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,'.');

如何根据这些条件有效地生成积分？

Answer 1

我仔细研究了你的算法，得出的结论是它永远不会起作用——至少如果你真的想在这个领域获得一百万分的话。有一张简单的图片可以解释为什么不这样做 - 这是您需要测试的点数图（使用 RSA 技术）以获得一个额外的“好”点。正如您所看到的，这在几千个点处渐近（我针对 200k 点运行了一个稍微快一点的算法来生成此结果）：

我不知道你是否曾经尝试过计算当你完美排列球体时可以容纳的点的理论数量，但我开始怀疑这个数字比 1E6 小很多。

我用于研究此问题的完整代码及其生成的输出可以在此处找到。我从来没有达到我在之前的回答中描述的技术......您描述的设置中还有太多其他内容。

编辑：我开始认为即使有“完美”的安排，也可能不可能达到 100 万分。我给自己做了一个简单的模型如下：

想象一下，您从“外壳”（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 脚本从外壳开始并逐步进入：

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

其输出是：

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

这似乎证实了无论你如何尝试，你确实无法达到一百万......