以最小最近邻距离在 3D 空间中生成随机点 [英] Generate random points in 3D space with minimum nearest-neighbor distance
问题描述
但它们要么在 matlab 中，要么没有完成所需的任务.
But they are either in matlab or does not fullfill the required task.
我必须在一个长度为 N 的盒子内创建 N 个点任意两点之间的距离大于delta.
I have to create N number of points inside a box of length that the distance between any two points is larger than delta.
例如:假设我在 x、y、z 轴上有一个长度为 10 埃的盒子.
我想在这个框中有 200 个随机点，以便最小距离任意两点之间的距离大于 3 埃.
For example:
Let's say I have a box of length 10 Angstrom on x,y,z axis.
I want to have 200 random points inside this box so that minimum distance
between any two points is larger than 3 Angstrom.
尝试:
#!python
# -*- coding: utf-8 -*-#
import numpy as np
np.random.seed(100)
np.set_printoptions(2)
box_length = 10
d = box_length
threshold = 6
num_points = 5
x1, y1, z1 = np.random.random(num_points)* box_length, np.random.random(num_points)* box_length, np.random.random(num_points)* box_length
x2, y2, z2 = np.random.random(num_points)* box_length, np.random.random(num_points)* box_length, np.random.random(num_points)* box_length
# print(len(x1))
# just for checking make ponts integers
for i in range(len(x1)):
x1[i] = int(x1[i])
x2[i] = int(x2[i])
y1[i] = int(y1[i])
y2[i] = int(y2[i])
z1[i] = int(z1[i])
z2[i] = int(z2[i])
print(x1)
print(y1)
print(z1)
print("\n")
pt1_lst = []
pt2_lst = []
for i in range(len(x1)):
a, b, c = x1[i], y1[i], z1[i]
a2, b2, c2 = x2[i], y2[i], z2[i]
dist2 = (a-a2)**2 + (b-b2)**2 + (c-c2)**2
print("\n")
print(a,b,c)
print(a2,b2,c2)
print(dist2)
if dist2 > threshold**2:
pt1 = (a,b,c)
pt2 = (a2,b2,c2)
pt1_lst.append(pt1)
pt2_lst.append(pt2)
print("points")
print(pt1_lst)
print(pt2_lst)
代码问题:此代码将点从点 1 到点 2 进行比较，但不会在点 1 和点 2 内部进行比较.
Problem on Code: This code compares points from points1 to points2 but does not compare within itself inside points1 and points2.
可能有更好的算法来解决这个问题，并向那些致敬带着绝妙想法来解决问题的人.
There might be better algorithms to solve this problem and hats off to those guys who come with the brilliant idea to solve the problem.
谢谢.
附注:我做了一些研究并尝试找到相关链接，但是无法解决问题.还有一些相关的链接是:
PS: I did some research and try to find related links, however was unable to solve the problem. Still some related links are:
更新::
我尝试了下面的 Stefans 代码，它适用于 N= 10，但我尝试了 N = 200 并且使用了非常长的时间(我在 10 分钟后停止了代码).
I attempted Stefans' code below, It works for N= 10 but I tried it for N = 200 and it is using extremely large time ( I stopped the code after 10 minutes).
有没有什么有效的方法可以做到这一点?
Is there any efficient way of doing this?
非常感谢您的帮助！！
从节点 n 使用的所有长度为 L 的路径蟒蛇
使用 Python 在定义的矩形内创建随机点
推荐答案
其他几个解决方案在框中取 n 个随机点，如果任何一对太接近，则丢弃整个集合.这效率不高；找到最坏的违规点并移动它更有效，如下:
Several of the other solutions take n random points in the box, and discard the whole set if any pair is too close. This is not efficient; it's more effective to find the worst offending point and move it, as follows:
import numpy as np
def get_sphere_distribution(n, dmin, Ls, maxiter=1e4, allow_wall=True):
"""Get random points in a box with given dimensions and minimum separation.
Parameters:
- n: number of points
- dmin: minimum distance
- Ls: dimensions of box, shape (3,) array
- maxiter: maximum number of iterations.
- allow_wall: whether to allow points on wall;
(if False: points need to keep distance dmin/2 from the walls.)
Return:
- ps: array (n, 3) of point positions,
with 0 <= ps[:, i] < Ls[i]
- n_iter: number of iterations
- dratio: average nearest-neighbor distance, divided by dmin.
Note: with a fill density (sphere volume divided by box volume) above about
0.53, it takes very long. (Random close-packed spheres have a fill density
of 0.64).
Author: Han-Kwang Nienhuys (2020)
Copying: BSD, GPL, LGPL, CC-BY, CC-BY-SA
See Stackoverflow: https://stackoverflow.com/a/62895898/6228891
"""
Ls = np.array(Ls).reshape(3)
if not allow_wall:
Ls -= dmin
# filling factor; 0.64 is for random close-packed spheres
# This is an estimate because close packing is complicated near the walls.
# It doesn't work well for small L/dmin ratios.
sphere_vol = np.pi/6*dmin**3
box_vol = np.prod(Ls + 0.5*dmin)
fill_dens = n*sphere_vol/box_vol
if fill_dens > 0.64:
msg = f'Too many to fit in the volume, density {fill_dens:.3g}>0.64'
raise ValueError(msg)
# initial try
ps = np.random.uniform(size=(n, 3)) * Ls
# distance-squared matrix (diagonal is self-distance, don't count)
dsq = ((ps - ps.reshape(n, 1, 3))**2).sum(axis=2)
dsq[np.arange(n), np.arange(n)] = np.infty
for iter_no in range(int(maxiter)):
# find points that have too close neighbors
close_counts = np.sum(dsq < dmin**2, axis=1) # shape (n,)
n_close = np.count_nonzero(close_counts)
if n_close == 0:
break
# Move the one with the largest number of too-close neighbors
imv = np.argmax(close_counts)
# new positions
newp = np.random.uniform(size=3)*Ls
ps[imv]= newp
# update distance matrix
new_dsq_row = ((ps - newp.reshape(1, 3))**2).sum(axis=-1)
dsq[imv, :] = dsq[:, imv] = new_dsq_row
dsq[imv, imv] = np.inf
else:
raise RuntimeError(f'Failed after {iter_no+1} iterations.')
if not allow_wall:
ps += dmin/2
dratio = (np.sqrt(dsq.min(axis=1))/dmin).mean()
return ps, iter_no+1, dratio
我尝试了不同的策略来决定移动哪些(另请参阅此答案的编辑历史)；似乎每次迭代移动一个坏点比一次移动多个坏点更有效.它使收敛到填充密度的差异为 0.25 和 0.53.
I experimented with different strategies for deciding which ones to move (see also the edit history of this answer); it appears that moving one bad point with every iteration is much more efficient than trying to move multiple bad points at once. It makes the difference between converging up to fill density 0.25 versus 0.53.
下面针对 dmin=1 和盒子大小 LxLxL 进行基准测试；3.33 对应问题中的大小.每个框大小的最高 n 是最后一个在 3e+4 次迭代中收敛的.d_nn 列是平均最近邻距离.
Benchmarking below for dmin=1 and box size LxLxL; 3.33 corresponds to the size in the question. The highest n for each box size is the last one that converges within 3e+4 iterations. The column d_nn is the average nearest-neighbor distance.
L n n_iter d_nn density
0 3.33 10 9 1.39 0.123
3 3.33 20 40 1.16 0.246
7 3.33 40 5510 1.06 0.493
8 3.33 43 2591 1.03 0.530
9 5.70 10 2 1.73 0.033
14 5.70 60 45 1.22 0.199
16 5.70 150 4331 1.05 0.499
17 5.70 165 25690 1.06 0.549
18 10.00 40 3 1.97 0.030
22 10.00 70 10 1.71 0.053
23 10.00 150 47 1.40 0.113
24 10.00 300 276 1.19 0.225
25 10.00 600 4808 1.07 0.451
27 10.00 720 26418 1.05 0.541
密度值是直径为 dmin 的球体的密度(近似于校正壁效应).随机填充球体的限制约为 0.64；这个算法显然不如将弹珠扔进盒子里.
The density value is the density for spheres of diameter dmin (approximated to correct for wall effects). The limit for random packed spheres is about 0.64; this algorithm clearly doesn't do as well as throwing marbles in a box.
请注意，该问题要求 n=200 在 L=3.33*dmin 框中，这将是 1.84 的填充密度并且永远不会适合.
Note that the question asked for n=200 in an L=3.33*dmin box, which would be a packing density of 1.84 and which would never fit.
为了比较，如果有任何接近对，则丢弃整个试验解决方案的算法的基准:
For comparison, the benchmark for an algorithm which discards the entire trial solution if there is any close pair:
L n n_iter d_nn density
0 3.33 10 52 1.38 0.123
1 3.33 14 224 1.25 0.172
2 3.33 15 24553 1.15 0.185
3 5.70 10 2 2.02 0.033
4 5.70 20 93 1.42 0.066
5 5.70 29 2089 1.36 0.096
6 5.70 30 10886 1.33 0.100
7 10.00 40 10 2.05 0.030
8 10.00 60 1120 1.79 0.045
9 10.00 68 5521 1.66 0.051
11 10.00 70 28545 1.64 0.053
该算法需要更多的迭代，而且迭代本身会变慢，因为每次迭代都需要重新生成和评估所有点和所有距离.
This algorithm takes many more iterations and moreover the iterations themselves ae slower because all points and all distances need to be regenerated and evaluated with every iteration.
这篇关于以最小最近邻距离在 3D 空间中生成随机点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
