在圆柱体内创建随机大小的球体并随机连接它们

Question

我知道这将是一个非常令人困惑的问题，你可以问我，我会尽力提供更多细节：

我想创建一个随机连接的球体网络，其大小在某个范围内是随机的。球体位于任意定位的圆柱体内。
每个球体都可以连接到许多其他球体，比如 5 个。
最后，我应该在圆柱体内随机放置球体，它们的半径在 [r_min,r_max] 范围内，并通过长度在 [L_min,L_max] 范围内的线 (links) 连接。

到目前为止，我采用的方法是将此任务分为两个步骤： 1) 首先，我想在给定圆柱体内的 3D space 中创建随机点。 2）然后我想连接它们。但是我将只连接那些它们之间的距离满足 2 个标准的对：

>=2*球体的最小半径+link的最小长度
<= 2*球体最大半径+link

然后我想将中心之间的距离随机划分为 2 个球体的半径和 link 的长度。

到目前为止，我已经弄明白了如何在圆柱体中创建随机点

我首先关心的是，如何确保从圆柱体的一端到另一端有一些连续的连接点簇（比如在中间不留下任何未连接点的间隙）？其次，如何最高效地编写代码？第三，我实际上想要对参数有更多的控制，简而言之，我想从一些已经创建的球体集合中随机挑选球体并将它们放置在圆柱体内并连接它们？代码可以这么写吗？

P.S。编程语言无所谓，我可以用任何语言编写它，我主要想搞清楚的是算法本身。

Answer 1

让我们从轴对齐的圆柱体开始。为此，我是这样看的：

定义

设 XY 平面为底面，圆柱体从 (0,0,0) 开始，向 +Z 方向延伸至距离 l，半径为 r。另外让我定义 l0,l1 是节点之间的最小和最大距离。
创建主路径

简单地放置一个从圆柱体开始到末端的连接节点链。这些将在以后用于增长集群。这也确保了从开始到结束的路径存在。因此，只需在 <l0,~l1> 范围内向 z 添加一些随机增量，并在比 r 更小的圆圈内使用 x,y 作为随机点以保持在路径上（我使用 10% 的 r).
集群增长

简单地随机取任何已经放置的点，向其添加一个大小为 <l0,l1> 的随机位移，如果仍在圆柱体内并且不太靠近任何其他点，则将其添加到您的数据中并 link到选定的点。如果您使用按 z 排序的点，则可以加快速度，这样您就可以摆脱 O(n) 搜索并改用 O(log(n))。

在此之后，您只需将轴对齐数据转换为您想要的最终位置和方向。例如，如果您将圆柱体定义为 2 个端点和半径，那么您可以计算 l 作为它们的距离，l0,l1 作为它的分数。您还可以使用简单的向量数学从中计算出 3 个垂直基向量（2 个表示 XY 平面，一个表示圆柱轴 Z）让我们称它们为 u,v,w。从那它只是矢量数学转换的问题......你也可以从那些构造4x4变换矩阵并使用它。

这里是 C++ 的小例子：

//---------------------------------------------------------------------------
const int N=200;    // points to generate
double pnt[N][3];   // random point
int    lnk[N];      // -1 or pnt[i] is linked to pnt[lnk[i]]
//---------------------------------------------------------------------------
void vector_mul(double *c,double *a,double *b) // c[3] = cross(a[3],b[3])
    {
    double   q[3];
    q[0]=(a[1]*b[2])-(a[2]*b[1]);
    q[1]=(a[2]*b[0])-(a[0]*b[2]);
    q[2]=(a[0]*b[1])-(a[1]*b[0]);
    for(int i=0;i<3;i++) c[i]=q[i];
    }
//---------------------------------------------------------------------------
void generate(double *p0,double *p1,double r)
    {
    int i,j,k,ok;
    double u[3],v[3],w[3];      // basis vectors
    double a,dx,dy,dz,x,y,z,z0;
    double l;           // cylinder size |p1-p0|
    double l0=0.03;     // min distance between major nodes <0,1>
    double l1=0.06;     // max distance between major nodes <0,1>
    double ll0=l0*l0,ll1=l1*l1,rr=r*r;
    Randomize();
    // basis vectors from endpoints
    for (l=0.0,i=0;i<3;i++){ w[i]=p1[i]-p0[i]; l+=w[i]*w[i]; }  // w = (p1-p0)
    l=sqrt(l); l0*=l; l1*=l;                                    // l=|w| , convert l0,l1 to units
    for (i=0;i<3;i++) w[i]/=l;                                  // w/=|w|
    if (fabs(w[0])<0.75){ u[0]=1.0; u[1]=0.0; u[2]=0.0; }       // u=(1,0,0) or (0,1,0) so it is not paralel to w
     else               { u[0]=0.0; u[1]=1.0; u[2]=0.0; }
    vector_mul(v,u,w);                                          // v = cross(u,w)
    // [axis aligne d cylindric data]
    // random major path
    for (z0=0,i=0;i<N;)
        {
        x=2.0*r*Random()-r; x*=0.1; // use only 10% of x,y deviation to not sray too much
        y=2.0*r*Random()-r; y*=0.1;
        z=z0+l0+(0.75*(l1-l0)*Random()); if (z>l) break;
        // inside cylinder ?
        if ((z<0)||(z>l)) continue;
        if ((x*x)+(y*y)>rr) continue;
        // no point closer than l0 ?
        for (ok=1,j=0;j<i;j++)
            {
            dx=pnt[j][0]-x;
            dy=pnt[j][1]-y;
            dz=pnt[j][2]-z;
            if ((dx*dx)+(dy*dy)+(dz*dz)<ll0){ ok=0; break; }
            }
        if (!ok) continue;
        // add if valid point
        pnt[i][0]=x;
        pnt[i][1]=y;
        pnt[i][2]=z; lnk[i]=i-1; i++; z0=z;
        }
    // grow clusters
    for (;i<N;)
        {
        // random 3D displacement <l0,l1>
        for (;;)
            {
            dx=Random()-0.5;
            dy=Random()-0.5;
            dz=Random()-0.5;
            a=(dx*dx)+(dy*dy)+(dz*dz);
            if (a>1e-3) break;
            }
        a=(l0+((l1-l0)*Random()))/sqrt(a); dx*=a; dy*=a; dz*=a;
        // convert to position
        for (k=0;k<10;k++)
            {
            // add it to random point already placed
            j=Random(i); lnk[i]=j; ok=1;
            x=pnt[j][0]+dx;
            y=pnt[j][1]+dy;
            z=pnt[j][2]+dz;
            // inside cylinder ?
            if ((z<0)||(z>l)){ ok=0; break; }
            if ((x*x)+(y*y)>rr){ ok=0; break; }
            // no point closer than l0 ?
            for (j=0;j<i;j++)
                {
                dx=pnt[j][0]-x;
                dy=pnt[j][1]-y;
                dz=pnt[j][2]-z;
                if ((dx*dx)+(dy*dy)+(dz*dz)<ll0){ ok=0; break; }
                }
            if (ok) break;  // valid point
            }
        if (!ok) continue;
        // add if valid point
        pnt[i][0]=x;
        pnt[i][1]=y;
        pnt[i][2]=z; i++;
        }
    // [convert to final position and orientation]
    for (i=0;i<N;i++)
        {
        x=pnt[i][0];
        y=pnt[i][1];
        z=pnt[i][2];
        for (j=0;j<3;j++) pnt[i][j]=p0[j]+(x*u[j])+(y*v[j])+(z*w[j]);
        }
    }
//---------------------------------------------------------------------------

和用法：

double p0[3]={-1.7,-0.5,-0.2};
double p1[3]={+1.7,+0.5,+0.4};
generate(p0,p1,0.5);

预览：

当心如果你设置太大 N 第二个主循环可以永远循环。 所以你可能想添加一些结束条件，比如如果继续被击中超过2*i 次没有 i 次更改停止。这是因为 l0 约束限制了点的最大密度，如果 N 大于该值，则无法添加更多点 ...

现在，如果你想要随机半径球体而不是点，而不是仅仅添加一些随机半径，但不要忘记通过半径调整内圆柱和最近距离测试...

在圆柱体内创建随机大小的球体并随机连接它们

Create spheres of random sizes inside a cylinder and randomly connect them

algorithm

geometry

connected-components