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

Question

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

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

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

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

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

到目前为止，我已经想出了如何在圆柱体内创建随机点

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

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

Answer 1

让我们从轴对齐的圆柱体开始。对于这样的我是这样看的:

1. 定义

   让XY平面是基础，圆柱体开始于 (0,0,0)并向 +Z 方向增长到距离 l半径为 r .也让我定义 l0,l1是节点之间的最小和最大距离。

2. 创建主路径

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

3. 发展集群

   简单地随机取任何已经放置的点添加一个大小为<l0,l1>的随机位移如果仍在圆柱体内并且不太靠近任何其他点，请将其添加到您的数据并将其链接到所选择的点。如果您使用按 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大于你不能添加更多的点...

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