如何生成多个互不重叠的不同半径圆（逻辑）

作者：叶飞影 链接：https://www.zhihu.com/question/53012468/answer/133362692 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

-------尊重原著！！！！！！！！！

感觉逻辑很棒就记录一下，怕哪天找不到了！

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