在圆柱体内创建随机大小的球，并随机将它们连接起来。

Question

在圆柱体内创建随机大小的球，并随机将它们连接起来。

3

我知道这将是一个非常令人困惑的问题，您可以向我询问，我将尝试提供更多细节：
我想在任意位置的圆柱体内创建一组随机连接的球体，这些球体具有随机大小且在某个范围内。每个球体可以与另外五个球体相连。最终，我应该在圆柱体内随机放置球体，其半径在[r_min,r_max]范围内，并通过长度在[L_min,L_max]范围内的线（链接）连接。
到目前为止，我分成了两个步骤来完成这个任务：
第一步，我想在给定圆柱体内创建3D空间中的随机点。
然后我想将它们连接起来。但我只会连接那些满足以下2个标准之间距离的对：

>= 2 *球体的最小半径+链接的最小长度

<= 2 *球体的最大半径+链接的最大长度

然后，我希望随机将球心之间的距离分配给2个球的半径和链接的长度。
到目前为止，我已经弄清楚如何在圆柱体内创建随机点。
我的担忧是，首先，如何确保我有一些连续的连接点簇，从圆柱体的一端到另一端（就像没有留下任何未连接点的间隙）？其次，如何以最有效的方式编写代码？第三，我实际上希望更多地控制参数，简单来说，我希望从一些已经创建的球体集合中随机选择球体并将它们放置在圆柱体内并将它们连接起来？是否可能编写这种代码？
P.S.编程语言不重要，我可以用任何一种语言编写它，我想弄清楚的主要是算法本身。

- qwarck

您可以检查集群的连接组件是否为1，以确定每个球之间是否存在路径。如果不是，则可以连接未连接的组件，或重新运行模拟直到获得单个组件。 - Reblochon Masque

“如何以最高效的方式编写代码”太过宽泛，最好的答案可能是：“需要付出大量的努力和精确性”？ - Reblochon Masque

是不是可以以一种方式编写代码，从而更好地控制参数？ --> 是的。 - Reblochon Masque

你的连通性问题在图论中得到了很好的解决。在你的情况下，只需选择一个起始节点并累积闭包即可。如果还有任何节点留在该集合之外，则说明你的图不连通。你的其余问题需要（1）分别发布；（2）定义得足够清晰，以便提供干净的答案。 - Prune

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Spektre · Accepted Answer

让我们从轴对称圆柱体开始。我认为它应该是这样的：

1.定义：将XY平面作为基础，圆柱体从(0,0,0)开始向上生长到距离l，半径为r。同时，让我定义l0,l1为节点之间的最小和最大距离。

2.创建主路径：从圆柱体的起点到终点放置一系列相连的节点。后面会用到这些节点来扩展集群。这也确保了始末点之间有路径。只需在<l0,~l1>范围内添加一些随机增量到z，并使用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太大，第二个主循环可能会永远循环。因此，您可能需要添加一些结束条件，例如如果连续命中i次而没有i更改，则停止。这是因为l0约束限制了点的最大密度，如果N大于该密度，则无法添加更多点...

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