问题

如何生成多个互不重叠的不同半径圆?

回答
想要生成一系列互不重叠且半径各不相同的圆,这确实是一个需要细致考量的问题,尤其是在计算机图形学或物理模拟的场景下。它不像看起来那么直接,需要一些策略来保证“互不重叠”这个关键条件。下面我将尽可能详细地介绍实现这一目标的方法和需要注意的细节。

问题的核心挑战

生成多个圆的简单方法是随机生成圆的中心坐标和半径,然后将它们绘制出来。然而,最棘手的部分在于如何确保这些圆“不互相重叠”。如果只是简单地随机生成,很有可能会出现圆相互穿插的情况,这就违背了我们的初衷。

核心策略:迭代放置与碰撞检测

解决这个问题的核心思路是:逐个生成圆,并在生成每个新圆时,检查它是否与之前已生成的圆发生了重叠。如果发生重叠,就调整新圆的参数(位置或半径),直到它不再重叠为止。

半径各不相同这一点相对容易处理,在生成新圆时赋予一个随机的半径即可。关键在于“互不重叠”的实现。

具体步骤详解

第一步:确定生成圆的总数和半径范围

在开始之前,你需要明确几个参数:

圆的总数 (N): 你希望生成多少个圆?
半径范围: 你希望圆的半径落在什么区间内?例如,最小半径是 `min_radius`,最大半径是 `max_radius`。确保 `min_radius` 小于 `max_radius`。

第二步:生成第一个圆(作为起始点)

第一个圆生成起来最简单,因为它没有其他圆需要进行碰撞检测。

1. 生成半径: 从你设定的半径范围内随机生成一个半径 `r1`。
2. 生成中心: 同样,在你的画布或工作区域内随机生成一个中心点 `(x1, y1)`。由于是第一个圆,它自然不会与其他圆重叠。
3. 记录圆: 将这个圆的信息(中心 `(x1, y1)` 和半径 `r1`)记录下来,为后续的碰撞检测做准备。

第三步:逐个生成剩余的圆(迭代与碰撞检测)

现在开始处理剩余的 `N1` 个圆。对于每一个新圆,我们需要一个过程来找到一个“合法的”(不重叠)位置和半径。

1. 生成候选半径: 从设定的半径范围内随机生成一个新的半径 `r_new`。
2. 尝试生成一个合法位置 (核心环节):
随机尝试: 这是最直观的方法。在你的工作区域内随机生成一个候选的中心点 `(x_new, y_new)`。
碰撞检测: 检查这个候选的圆(中心 `(x_new, y_new)`,半径 `r_new`)是否与之前所有已生成的圆发生了重叠。
如何检测两个圆是否重叠? 这是核心的几何判断。假设我们有两个圆:
圆 A:中心 `(x_a, y_a)`,半径 `r_a`
圆 B:中心 `(x_b, y_b)`,半径 `r_b`
它们重叠的条件是:两个圆心之间的距离小于它们半径之和。
距离计算公式:`distance = sqrt((x_a x_b)^2 + (y_a y_b)^2)`
重叠条件:`distance < r_a + r_b`
为了避免开平方运算,通常使用距离的平方进行比较,这样更高效:`distance_sq = (x_a x_b)^2 + (y_a y_b)^2`
重叠条件(优化后):`distance_sq < (r_a + r_b)^2`

如果发生重叠: 说明这个候选的中心点 `(x_new, y_new)` 对于当前半径 `r_new` 是无效的。你需要继续尝试新的中心点。回到“随机尝试”这一步,重新生成一个中心点,并再次进行碰撞检测。

如果没有发生重叠: 太好了!这个候选圆是合法的。将它的信息(中心 `(x_new, y_new)` 和半径 `r_new`)记录下来,并添加到已生成圆的列表中。然后,可以开始生成下一个圆。

第四步:处理可能出现的“死锁”或低效问题

上述的“随机尝试”方法在某些情况下可能会非常低效,甚至陷入“死锁”(即很难找到一个合法的随机位置)。想象一下,当画布上已经充满了大大小小的圆时,再想找一个能放得下新圆(尤其是半径较大的新圆)的空隙会变得异常困难。

为了应对这种情况,可以考虑一些优化或替代策略:

1. 增加尝试次数限制: 对于每个新圆,设置一个最大尝试次数。如果尝试了太多次(例如几千次、几万次)仍然找不到合法的随机位置,可能意味着当前的画布状态难以再放置这个半径的圆了。
怎么办?
放弃这个圆: 简单粗暴,但保证了整体的成功率。
减小半径: 如果尝试失败,尝试稍微减小当前候选半径 `r_new`,然后再继续尝试放置。
重新排列: 更复杂的策略是,当遇到困难时,可以考虑将之前生成的某些圆稍微调整一下位置,为新圆腾出空间。但这会增加很多复杂性。
增大工作区域: 如果可能,扩大生成圆的区域,增加找到空隙的可能性。

2. 更智能的放置策略(高级):
基于空隙的放置: 尝试直接识别画布上的空隙,然后将新圆尝试放置在这些空隙的中心附近。这需要更复杂的空间数据结构来管理空隙。
基于“填充”的策略: 想象一下将画布视为一个容器,圆是“填充物”。可以先生成一些较大的圆,然后尝试用较小的圆填充它们之间的空隙。这是一种“打包”问题。
网格划分: 将工作区域划分为网格,并在每个网格单元中尝试放置圆,或者记录每个网格单元被圆占据的程度。

3. 调整半径的生成方式:
先生成小圆: 如果你的目标是生成许多小圆,可以优先生成较小的半径,这样更容易找到不重叠的位置。
考虑圆的分布密度: 如果你希望圆的分布更均匀,可以根据已放置圆的密度来调整新圆的生成位置。

第五步:将生成的圆绘制出来

一旦你成功生成了一系列互不重叠的圆,就可以使用图形库(如 Python 的 Matplotlib, Pygame, 或其他编程语言的相应库)将它们绘制在屏幕上或保存为图片。绘制时,只需要遍历你记录的圆列表,为每个圆指定其中心和半径即可。

总结一下核心流程:

1. 初始化: 定义圆的总数 `N`,半径范围 `[min_r, max_r]`。创建一个列表 `generated_circles` 来存储已成功生成的圆。
2. 生成第一个圆: 随机生成半径 `r1` 和中心 `(x1, y1)`,将其添加到 `generated_circles`。
3. 循环生成剩余圆 (N1 次):
生成候选半径 `r_new`。
循环尝试放置:
随机生成候选中心 `(x_new, y_new)`。
设置一个标志 `is_overlapping = False`。
遍历 `generated_circles` 中的所有已生成圆:
如果 `(x_new, y_new)` 和 `r_new` 与已生成圆 `(x_old, y_old)` 和 `r_old` 重叠(即 `distance_sq((x_new, y_new), (x_old, y_old)) < (r_new + r_old)^2`):
设置 `is_overlapping = True`。
中断内层循环(因为这个中心点不行了)。
如果 `is_overlapping` 是 `False`:
说明找到了一个合法位置!将新圆 `(x_new, y_new, r_new)` 添加到 `generated_circles`。
中断尝试放置的循环(这个新圆已成功生成)。
如果尝试放置循环次数过多: 考虑进行优化或放弃。
4. 绘制 `generated_circles` 中的所有圆。

需要注意的细节和技巧:

边界条件: 确保生成的圆不会超出你的工作区域的边界。在生成中心点时,需要根据圆的半径留出足够的边距。例如,如果工作区域是 `[0, W]` 和 `[0, H]`,那么生成圆心 `x` 时,应该在 `[r, Wr]` 的范围内,`y` 在 `[r, Hr]` 的范围内。
数值精度: 在进行浮点数比较时,有时候会遇到精度问题。虽然对于半径和距离的比较,直接使用 `<` 通常没问题,但在极少数边界情况下,可以考虑稍微引入一个极小的容差(epsilon),例如 `distance_sq < (r_a + r_b)^2 epsilon`,但这通常不是必需的。
效率考虑: 如果需要生成成千上万个圆,效率会变得非常重要。频繁的碰撞检测会消耗大量时间。考虑使用更优化的数据结构(如四叉树或kd树)来加速查找可能发生碰撞的圆,而不是每次都检查所有已生成的圆。
随机数生成器的种子: 如果你需要重现相同的圆的布局,请设置随机数生成器的种子。

这个过程的核心在于迭代放置和碰撞检测。通过反复尝试并验证,最终可以生成满足“互不重叠”和“半径不同”要求的圆的集合。虽然理论上可能存在无法放置的情况(例如,画布太小,半径太大),但通过合理的参数设置和适当的尝试策略,大多数情况下都能得到令人满意的结果。

网友意见

user avatar

这个问题就算没人邀请,我也一定要答。有一次和公司一个美术扯皮,最后他竟然威胁我说:“我画个圈圈诅咒你!”我立马反击道:“我写个程序,画一大坨圈圈诅咒你!而且我还会用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

类似的话题

  • 回答
    想要生成一系列互不重叠且半径各不相同的圆,这确实是一个需要细致考量的问题,尤其是在计算机图形学或物理模拟的场景下。它不像看起来那么直接,需要一些策略来保证“互不重叠”这个关键条件。下面我将尽可能详细地介绍实现这一目标的方法和需要注意的细节。 问题的核心挑战生成多个圆的简单方法是随机生成圆的中心坐标和.............
  • 回答
    生成和管理 Visual C++ 的多版本工程文件是一个非常重要且常见的需求,尤其是在需要支持多个编译器版本、多个目标平台(如 32 位和 64 位)、或者针对不同配置(如 Debug 和 Release)进行构建时。Visual Studio 提供了强大的工具和机制来处理这种情况。本文将详细介绍如.............
  • 回答
    改掉生性多疑的性格,不是一朝一夕的事情,更像是在心里开辟一块新的疆域,需要耐心、勇气和持续的努力。这过程中,你可能会遇到反复,感到沮丧,但请相信,每一点进步都值得肯定。我们先来聊聊“多疑”到底是什么样的感觉。它可能表现为: 时刻在脑海里上演“小剧场”: 别人的一句话、一个眼神,都能让你脑补出无数.............
  • 回答
    抗战后期,随着中国战场战局的扭转,以及太平洋战场日军节节败退,留在中国的日军,尤其是那些被切割、被包围的部队,处境愈发艰难。他们的“负隅顽抗”更多的是一种被动的、绝望的挣扎,而非有组织的、有希望的反攻。兵力与士气: 分散与孤立: 随着盟军在太平洋战场上的推进,日本海军和空军的制空权、制海权几乎丧.............
  • 回答
    抗战胜利前夕,在中国境内,特别是一些偏远地区和交通不便的据点,仍有部分日军在负隅顽抗。这些部队的处境,正如您所说,已经非常窘迫,走向了最后的败亡。以下将从几个方面详细讲述其战败情况和生活窘迫程度:一、战败情况:被围困、补给断绝、节节败退1. 战术上的孤立与围困: 随着中国军队战略反攻的推进,特别是.............
  • 回答
    “多生几个孩子,兄弟姐妹多,长大之后每个孩子都会很轻松”的说法,乍一看似乎很有道理,毕竟人多力量大,可以互相扶持。但深入分析,这种说法过于片面,甚至有些理想化。实际情况要复杂得多,它既有潜在的好处,也存在显著的弊端,而且所谓的“轻松”很大程度上取决于家庭的综合实力和教育方式。下面我将从多个维度来详细.............
  • 回答
    说到兰州有多长,那可真是说来话长,而且一点都不夸张。你得有这个心理准备,因为它不是一两句话能说完的,更不是像一张明信片那样一眼能看完的。兰州的长,那是一种历史沉淀,是一种地理馈赠,更是一种生活肌理,渗透在城市的每一寸呼吸里。你想啊,它依偎着黄河,黄河水从西边奔腾而来,一路婉转,在兰州这儿留下了最慷慨.............
  • 回答
    多细胞生物体内的营养输送,是一个精巧而又至关重要的生命过程,它确保了每一个细胞都能获得生长、代谢和维持生命活动所需的“燃料”和“建材”。不像单细胞生物可以直接从环境中摄取营养,多细胞生物的身体是一个复杂而协同的整体,需要一套专门的机制来完成这场细胞间的“营养接力”。1. 消化与吸收:营养的第一站对于.............
  • 回答
    江苏省提出的“对生育多孩的女性劳动者,给予就业帮扶”的立法意向,无疑是当前社会一个非常值得关注和深入探讨的议题。这背后折射出的,是对女性生育、养育负担的社会化分担的尝试,以及如何保障女性在职场上的权益,促进性别平等的重要考量。要理解这项立法意向的深层含义,我们可以从几个维度来剖析:一、立法初衷与社会.............
  • 回答
    我的天,这绝对是我做过的最诡异的梦,或者……哦,不,这不是梦。就发生在上个星期二的早晨。我像往常一样,在闹钟响了不到五分钟就开始挣扎着爬起来。推开卧室门,我本该看见空荡荡的客厅,然后是厨房里冒着热气的咖啡。但那天,我看见了“我”。准确地说,是另一个我。他就那样坐在我的沙发上,穿着我前一天晚上换下的那.............
  • 回答
    南京红山动物园园长这番话,确实触及了一个很现实也很有深度的问题:动物园在快速变化的社会观念和公众期望下,如何找到自己的生存之道? 单纯从字面上看,他表达了一种略带“委屈”和“无奈”的情绪,似乎在说:“我辛辛苦苦做了调整,结果回应平平,这日子怎么过?”仔细品味一下,这番话背后蕴含着几层意思:1. 公众.............
  • 回答
    古代“一夫一妻多妾”制度为何能存在?几个女人如何生活在一起?在中国的古代社会,婚姻制度并非我们今天所熟知的一夫一妻制,而是“一夫一妻多妾”的形式。这种制度的出现和延续,背后有着深刻的社会、经济、政治和文化根源。而在这制度下,一个男人、一个妻子(正妻)和多个妾室共存的生活模式,也并非如同字面般简单,而.............
  • 回答
    这起悲剧令人心痛,也再次敲响了警钟。在一个本应受到法律保护的调解期内,一名女性就这样被剥夺了生命,而且是在多次遭受家暴的背景下。这绝不是个例,而是无数家庭暴力受害者正在经历的残酷现实。如何真正地保护被家暴者,是我们社会必须正视并采取切实行动的难题。要解决这个问题,我们需要从 事前预防、事中干预、事后.............
  • 回答
    这是一个非常普遍且引人深思的社会现象,其中包含了许多复杂的因素。当一个念了半辈子书的博士,在经济收入和生活幸福感上,被一个工作不错的大专生超越时,其内心感受必然是复杂且多层次的。我们可以从以下几个方面来详细探讨: 博士的心路历程与感受1. 巨大的心理落差与自我价值的质疑: 期望与现实的背离: 博.............
  • 回答
    马斯克的“生育号召”:一场关于人口、未来与责任的深刻讨论埃隆·马斯克,这位以“地球生命延续”为己任的科技巨头,最近又一次抛出了一个引人注目的观点:呼吁人们多生孩子,并且直言不讳地表示,地球正面临着“人口崩溃”的危机,而他自己就是“榜样”。这个论调一出,立刻在社交媒体和公众舆论中掀起了轩然大波,引发了.............
  • 回答
    俞敏洪老师鼓励大家多生孩子,并且提到“小的可以穿旧衣,成本并没有那么高”的说法,这番话在当下社会确实引起了不少讨论。要怎么看这个问题,我觉得得从几个层面去理解。首先,从俞敏洪老师个人的角度来说,他可能是出于他对中国人口结构、未来发展趋势的一种观察和判断。作为一个在教育领域深耕多年的企业家,他肯定对人.............
  • 回答
    “错批马寅初,多生5亿人”这个说法,在我看来,与其说是一种对历史事件的简单定论,不如说是一种对计划生育政策的深刻反思,以及对历史人物贡献的重新评价。它并非一个不容置疑的绝对真理,但它确实触及了一个非常核心的问题:如果当初更重视马寅初的人口论,中国今天的人口结构和发展轨迹,是否会是另一个样子?首先,我.............
  • 回答
    您好!很高兴能就“生、化方向高档次文章越来越多带理论计算”这一现象,和您进行一次深入的探讨。这确实是一个非常值得关注的趋势,而且在我看来,这并非偶然,而是科学发展到一定阶段的必然结果,并且对生命科学和化学研究的未来有着深远的影响。为什么会出现这种现象?我们可以从几个层面来剖析:1. 理解的深度需求.............
  • 回答
    一个经济学家提出“央行多印 2 万亿,用 10 年多生 5000 万孩子”的建议,这绝对是个能让人眼前一亮、甚至有点石破天惊的说法。咱们不妨掰开了揉碎了,好好说道说道这个提议的逻辑、可行性以及它背后可能隐藏的复杂性。提议的逻辑:为什么会冒出这么个点子?表面上看,这个建议似乎是将两个毫不相干的事情——.............
  • 回答
    俄罗斯鼓励生育的政策,特别是对女性提供的长达三年带薪产假以及多次生育的经济激励,可以说是当地社会和政府在应对人口结构挑战的一个重要举措。这项政策背后,既有对家庭的关怀,也有着对国家未来发展的考量。首先,我们来看看这项政策的具体内容。俄罗斯的女性可以享受最多三年的带薪产假。这三年里,母亲可以安心在家照.............

本站所有内容均为互联网搜索引擎提供的公开搜索信息,本站不存储任何数据与内容,任何内容与数据均与本站无关,如有需要请联系相关搜索引擎包括但不限于百度google,bing,sogou

© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有