如何生成多个互不重叠的不同半径圆？第1页

xie-fei-ying-24 网友的相关建议:

这个问题就算没人邀请，我也一定要答。有一次和公司一个美术扯皮，最后他竟然威胁我说：“我画个圈圈诅咒你！”我立马反击道：“我写个程序，画一大坨圈圈诅咒你！而且我还会用N种方法画。”

（1）第一种方法
写个循环，循环中随机生成一个圈圈的圆心坐标位置、半径。然后判断圈圈是否与已有的圈圈发生碰撞。如果有碰撞让它滚蛋，否则画圈圈。

（2）第二种方法
还是写个循环，循环中随机生成一个圈圈的圆心坐标位置，然后判断这个坐标点是否在已有的圈圈内部，如果是就让它滚蛋，否则计算出与它到距离最近圈圈的距离，并以此画圈圈。

（3）第三种方法

有时需要将一堆指定半径的圈圈，无碰撞的放置在某一空间中。这就需要一套物理碰撞算法，感觉很难，不要怕，圈圈之间的碰撞检测是所有碰撞检测中最容易的。碰到这一情况，首先要找到一个中心点，然后将所有的圈圈按照与该中心点的距离远近进行排序，依次将每一个圈圈朝向党中心靠近，最后实现大和谐。

这种方法中需要克服的一个难点是，如何实现三个圈圈的两两相碰。解决这一问题，需要用到一个数学公式：余弦定理，已知三角形的三边长度，求三个角度。这算是我在实际编程中用过最高深的数学知识之一。

我写的一个小游戏：连泡泡用的就是这一方法。

鼠标左键拖动泡泡到另一个与之相同颜色的泡泡旁边，松开鼠标左键，两个泡泡就会自动合并。将所有相同颜色的泡泡连到一块即过关。挺无聊的一个游戏，玩多了容易得强迫症。

（4）第四种方法

让所有圈圈围向一个中心，这样太过集中，体现了独裁专制，这政治不正确吗。有时可能只是想让圈圈放到一个大框里。这时的处理方式和前一个类似，只是修改一下圈圈的排序方式，让圈圈按照朝向某一方向的远近进行排序，并且朝着该方向移动。

我还写过两个更无聊的小游戏：

掐泡泡，在这个游戏中场景中含有若干个大小颜色不同的泡泡，同色泡泡碰撞后会合并成一个大点的泡泡，当泡泡大到一定程度后会破裂消失。泡泡会不停变多，鼠标也需要不停地点击泡泡。当泡泡挤到最下方时，游戏结束。

打泡泡，和上个游戏类似，场景中含有若干个大小颜色不同的泡泡，界面下方可以发射不同颜色的泡泡，击中同色泡泡后会与之合并成一个大点的泡泡，当泡泡大到一定程度后会破裂消失。同样，当泡泡挤到最下方时，游戏结束。

（5）第五种方法

前四种方法，每添加一个圈圈时，都需要遍历已有圈圈判断是否与之碰撞。当圈圈数目增大时，效率不高啊。第五种方法可以轻松画出大规模的圈圈：

先以固定步长生成规则的正方形网格点；

然后对网格点进行随机移动，移动距离不要超过固定步长;

移动后的网格点为圈圈的圆心;

计算出每一个网格点与其周围8个网格点的最近距离;

最近距离的一半为圈圈的半径；

画圈圈，就这么简单搞定。

发一下该算法的C代码：

       inline void hash22(float px, float py, float& hx, float& hy) {      float n = sinf(px * 7.0f + py * 157.0f);       hx = 2097152.0f*n;     hy = 262144.0f*n;      hx = hx - floorf(hx);     hy = hy - floorf(hy); }  // 查找最近的相邻顶点 float   nearest_dis_2d(float x, float y) {     float ox, oy;     hash22(x, y, ox, oy); // 当前顶点偏移      float d, r = 2.0f;     float vx, vy;     for(int i = -1; i <= 1; i++)     {         for(int j = -1; j <= 1; j++)         {             if (i == 0 && j == 0)             {                 continue;             }              hash22(i + x, j + y, vx, vy);             vx += float(i) - ox;             vy += float(j) - oy;              d = vx*vx + vy*vy;             if (d < r)             {                 r = d;             }         }     }      return sqrtf(r); }  // 使用worley画圈圈 float   circle_worley2d(float x, float y) {     float fx = floorf(x);     float fy = floorf(y);     float gx = x - fx;     float gy = y - fy;      float vx, vy;     float d, r = 3.0f;      float si, sj;     for(int i = -1; i <= 1; i++)     {         for(int j = -1; j <= 1; j++)         {             hash22(i + fx, j + fy, vx, vy);             vx += float(i) - gx;             vy += float(j) - gy;             d = vx*vx + vy*vy;             if (d < r)             {                 r = d;                 si = i + fx;                 sj = j + fy;             }         }     }      d = sqrtf(r) / nearest_dis_2d(si, sj) * 2.0f;     return d; }

代码中调用函数circle_worley2d，输入是平面上的一个二维坐标，返回值为1时，表示该坐标位于圆上。用上面的代码可以生成如下图像：

虽然这种方法对空间的利用率并不高，但它的运算复杂度与圈圈的数目无关。

（6）第六种方法:

上一种方法中,float circle_worley2d(float x, float y)函数,可以很容易地改成三维的

float circle_worley3d(float x, float y, float z)。

用三维的可以生成空间中若干个互相不重叠的球,如下图所示:

并且利用circle_worley3d函数可以实现球面上画圈圈:

当然,扩展到三维后的circle_worley3d函数，可以在任意一个三维图形上画圈圈。下图为将许多圈圈画在一个圈圈上:

（7）终极圈圈诅咒

球面上画圈圈有什么用处呢？可以生成陨石坑。

将生成圈圈的算法迭代个若干次，就能生成一个布满陨石坑的星球：

不过这个球不是我做的，生成它的代码在：Shadertoy.

我生成的球是这样：

当我看到这个星球时，有一种强烈的冲动：把这个球从显示器中拿出来，然后砸在某人脸上。这滋味想想就觉得酸爽。

====================

附上篇国外一大叔写的文章:Random space filling tiling of the plane

如何生成多个互不重叠的不同半径圆？的其他答案点击这里

前一个讨论

NBA 有哪些令人潸然泪下的故事？

下一个讨论

装逼成功真的会让人心情愉悦么？

如何生成多个互不重叠的不同半径圆？第1页

相关话题

前一个讨论

下一个讨论

相关的话题

如何生成多个互不重叠的不同半径圆？ 第1页

相关话题

前一个讨论

下一个讨论

相关的话题

如何生成多个互不重叠的不同半径圆？第1页