non-overlapping-circle

KO | EN

gitlite — search

#javascript #ai #typescript #llm #android #rust #docker #nodejs #awesome #kubernetes #vue #ios #mcp #open-source

non-overlapping-circle

(★ 9)

不等圆的packing问题，基于概率策略化的随机游走。在缝隙处可额外进行补充，使更加丰满。

non-overlapping-circle Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# 基于策略化的随机游走，处理不等圆的不重叠随机排列问题
代码: https://github.com/FrozenWhalePP/non-overlapping-circle

## 背景

- 来源于概率论的小作业，发现数学中的随机美。画圆是个很经典的问题，不等圆的packing问题也有很多算法。
## 方法

- 最初想法 
    - 一开始想到，既然前几天刚做了Voronoi图有关的小程序，而Voronoi图划分了一些不重叠的区域，其按照最邻近原则划分平面；每个点与它的最近邻区域相关联，可以做区域的内切圆。了解了一下，Delaunay网格法是解决这类问题的一种算法。
    - Delaunay三角形是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形。Delaunay三角形的外接圆圆心是与三角形相关的Voronoi多边形的一个顶点。由于对内接圆的处理不是很擅长，这里采用另一种思路。
- 采用随机游走策略，使用`python`进行模拟。引入势能场，图中的中心处为势能最低点（势能为0），以图中所有圆的势能和最低为优化目标。
- 初始化一个N×N的网络，初始时，最多加入N×N个圆，每个网格的中心即一个圆的圆心坐标。这保证了圆不会重叠。生成圆的时候，在给出范围内随机化半径大小。
- 每一轮中，对于单个圆，进行随机的移动。
    - 移动的前提是目标位置是有效的，即圆没有越过边界，且不和其他的圆相交。
    - 大概率向着势能0方向移动，小概率方向随机移动，这防止了移动过程中出现的拥挤现象，产生局部障碍。
    - 目标方向使得势能降低，仍保证一定概率移动，是为了给其他的圆进行让路。
    - 移动的步长随机取值，大概率为默认值，小概率增加或者减少。大步长使得跨越围墙或者障碍成为可能，小步长能够更加贴近其他圆。
- 迭代终止的条件是二者之一。
    - 经过连续m轮迭代，所有圆的位置都没有发生变化。
    - 经过共n次迭代，达到计算次数上限。
- 由于每次随机游走，需要遍历所有的圆，在圆的数量较大时，迭代速度较慢。因此可以先通过此方法优化到较好的情况，再进行填充。
- 在缝隙中进行填充。随机取坐标，确保其位置有效或者没有被占据，然后令半径从0开始逐步增加，步长从最大半径开始，以一定的函数进行递减。直到达到其圆心处所允许的最大插入半径，将其插入。
- 如果经过n次尝试插入，均为发现有效位置，则退出。

## 在`randomCircleFig.py`中的更新
- 增加了自定义边界，使用OpenCV提取轮廓，matplotlib.path判断是否在边界内
- 在边界的网格内随机取单元格
- 不使用整个图的势能和，而是使用直接计算单个圆的势能，单个圆有较大概率向着低势能处移动
- 增加了停滞指数，当圆连续停滞时，增加其随机方向的概率，即有更多可能朝着势能升高处移动。这是由于增加边界后的路径变得复杂。

## 可视化

- 使用`matplotlib.pyplot`进行绘图，每个圆的色彩随机取值。
- 可以给出图片，自定义轮廓，进行圆的填充。
    - 在边界上设置一系列圆，充当守卫，他们不会移动，但是会隔离。    
## 结果

- 自定义边界轮廓

- 没有插入填充时候的样例。

- 进行插入填充的样例

non-overlapping-circle

non-overlapping-circle Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

non-overlapping-circle

non-overlapping-circle Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README