Давайте начнем с цилиндра, выровненного по оси. Для таких я вижу это так:
определение
пусть XY плоскость будет базой, а цилиндр начинается с (0,0,0) и растет в направлении + Z до расстояния l и имеет радиус r. Также позвольте мне определить l0,l1 как минимальное и максимальное расстояние между узлами.
создать основной путь
Просто поместите цепочку связанных узлов, идущих от начала цилиндра до его конца. Они будут использованы позже, чтобы вырастить кластеры. Это также гарантирует, что путь от начала до конца существует. Поэтому просто добавьте несколько рандомизированных приращений к z в диапазоне <l0,~l1> и используйте x, y в качестве рандомизированной точки внутри некоторого меньшего круга, чем r, чтобы остаться на пути (я использую 10% от r).
рост кластеров
просто случайным образом возьмите любую уже размещенную точку, добавьте к ней случайное смещение размером <l0,l1> и, если она все еще находится внутри цилиндра и не слишком близко к какой-либо другой точке, добавьте ее к своим данным и свяжите с выбранной точкой. Это может быть ускорено, если вы используете точки, отсортированные по z, так что вы можете избавиться от поиска O(n) и использовать вместо него O(log(n)).
После этого вы просто конвертируете данные, выровненные по оси, в конечную позицию и желаемую ориентацию. Например, если вы определите свой цилиндр как 2 конечные точки и радиус, тогда вы можете вычислить l как их расстояние, l0,l1 как его долю. Также вы можете вычислить 3 перпендикулярных базисных вектора из него, используя простую векторную математику (2 представляют плоскость XY и один представляет ось цилиндра Z), назовем их u,v,w. Исходя из этого, нужно преобразовать векторную математику ... Из них можно также создать матрицу преобразования 4х4 и использовать ее.
Вот небольшой пример 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 больше этого значения, вы не можете добавлять больше точек ...
Теперь, если вам нужны сферы со случайным радиусом вместо точек, просто добавьте некоторый случайный радиус, но не забудьте настроить внутренний цилиндр и тесты ближайшего расстояния по радиусу ...