![cover](https://img-blog.csdnimg.cn/2027c7208a7145e68922edf0f226c13c.png)
洪水填充算法详解
洪水填充算法详解。
- 😜作 者:是江迪呀
- ✒️本文关键词:
算法
、前端
、JavaScript
、HTML
、洪水填充算法
- ☀️每日 一言:
不以物喜,不以己悲
文章目录
效果:
一、前言
当象一个容器
中注水时,无论容器的结构如何复杂,注入的水总是能够绕过障碍物
填满整个区域。有一种算法叫做洪水填充
算法,它是一种图像处理算法
,用于填充封闭区域
。它的工作原理类似于在图像上泼洒颜料,使一个种子像水流一样蔓延,填充连通的区域,直到遇到边界或其他障碍物为止。我们可以将洪水填充算法比喻为在涂色本上填色的过程。假设我们有一个空白的涂色本,上面有很多小格子,每个格子可以涂上不同的颜色。现在,我们想要将某个格子以及和它相连通的所有相同颜色的格子都涂上另一种颜色。非常有趣,下面让我们来一起学习一下洪水填充算法的原理。
二、思路
红色: 起点。
绿色: 可到达的点。
黑色: 障碍物。
2.1 起点
这个起点
我们可以理解为出水口
,扩散的起点。一般都选择中心点
作为起点
。
2.2 检查起点四周
检查起点
的 上
下
左
右
四个方向是否存在障碍物
。如果不是障碍物,则为绿色(表示可到达的点)
并存入待检查队列
中,如果存在障碍物
,颜色不变,不存入待检查队列
。
2.3 填充相邻点
将待检查队列
中的点,填充为红色
,并检查它的四周是否存在可到达
的点:
2.4 继续扩散
循环2.2
、 2.3
步骤继续检查扩散。
2.7 结束
当待检查队列
中没有节点时,证明已经检查
并扩散
完毕了。
图中的两个白色的节点,是不可到达的点。
三、实现
为了更加直观看到洪水填充
算法的执行过程,我们使用JavaScript
和HTML
来实现。完整代码如下:
3.1 HTML + JavaScript代码
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Canvas Grid with Obstacles</title>
<style>
body {
margin: 0;
padding: 0;
display: flex;
justify-content: center;
align-items: center;
height: 100vh;
background-color: #f0f0f0;
}
canvas {
border: 1px solid black;
}
#showTable {
width: 200px;
height: 150px;
border: 1px solid black;
padding: 10px;
}
</style>
</head>
<body>
<canvas id="gridCanvas" width="1500" height="1500"></canvas>
<div id="showTable">
<div>总数量: <span id="totalSquares">2,250,000</span></div>
<div>障碍物数量: <span id="obstacleCount">0</span></div>
<button onclick="randomObstruction()">生成障碍物</button>
<button onclick="startDetect()">开始探测</button>
</div>
<script>
const canvas = document.getElementById("gridCanvas");
const ctx = canvas.getContext("2d");
const size = 10;//网格大小
const gridSize = 150; // 网格数量
const totalSquares = gridSize * gridSize;
const centerPoint = { x: Math.floor(gridSize / 2), y: Math.floor(gridSize / 2) };
const totalSquaresDisplay = document.getElementById("totalSquares");
const obstacleCountDisplay = document.getElementById("obstacleCount");
const detectedCountDisplay = document.getElementById("detectedCount");
let obstacles = [];
function drawSquare(x, y, color) {
ctx.fillStyle = color;
ctx.fillRect(x, y, size, size);
}
//随机生成障碍物
function randomObstruction() {
obstacles = [];
//先清空之前生成的障碍物
ctx.clearRect(0, 0, canvas.width, canvas.height);
drawGrid(); // Redraw the grid lines
const obstacleCount = Math.floor(Math.random() * 301) + 10000;
for (let i = 0; i < obstacleCount; i++) {
const x = Math.floor(Math.random() * gridSize) * size;
const y = Math.floor(Math.random() * gridSize) * size;
obstacles.push({ x, y });
drawSquare(x, y, "black");
}
obstacleCountDisplay.textContent = obstacleCount;
}
//洪水填充
function startDetect() {
const detectedSet = new Set();
const queue = [];
const dx = [0, 1, 0, -1];
const dy = [-1, 0, 1, 0];
let detectedCount = 0;
function isValid(x, y) {
return x >= 0 && x < gridSize && y >= 0 && y < gridSize;
}
queue.push(centerPoint);
detectedSet.add(`${centerPoint.x},${centerPoint.y}`);
while (queue.length > 0) {
const { x, y } = queue.shift();
let canExpand = true;
//上下左右四个方向
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
const key = `${nx},${ny}`;
if (!isValid(nx, ny) || detectedSet.has(key) || obstacles.some(({ x, y }) => x === nx * size && y === ny * size)) {
canExpand = false;
continue;
}
queue.push({ x: nx, y: ny });
detectedSet.add(key);
detectedCount++;
}
if (canExpand) {
detectedCount++;
}
}
//重绘填充后的网格
detectedSet.forEach(coords => {
const [x, y] = coords.split(',').map(coord => parseInt(coord, 10));
setTimeout(() =>{
drawSquare(x * size, y * size, "lightblue");
},500)
});
detectedCountDisplay.textContent = detectedCount;
}
//画网格
function drawGrid() {
for (let i = 0; i < gridSize; i++) {
for (let j = 0; j < gridSize; j++) {
drawSquare(i * size, j * size, "gray");
ctx.strokeStyle = "lightgray";
ctx.strokeRect(i * size, j * size, size, size);
}
}
}
//初始化
drawGrid();
totalSquaresDisplay.textContent = totalSquares;
</script>
</body>
</html>
3.2 效果
下面是,一张布满225W
个网格的画布,执行的洪水填充算法
:
四、应用
洪水填充算法应用很广泛,主要用于图像
、游戏
领取。
4.1 图像填充
windows中的画图工具中的填充功能,其实就是使用洪水填充算法
来实现的。下面填充下咸蛋超人:
我们可以看到再填充咸蛋超人
身体的时候,由于计时器
是个封闭的圆形
所以并没被填充为红色。
4.2 区域分割
在计算机视觉领域,洪水填充算法也被用于图像的区域分割。通过选择一个种子点,洪水填充算法可以将图像中与种子点相连通的相似区域标记出来,从而实现图像的自动分割。
4.3 地图探索
在计算机游戏中,地图探索算法使用洪水填充来寻找从给定位置可到达的所有连通区域,如迷宫游戏或地图探索类游戏。在生成随机地图时,应该避免生成角色
无法到达的死路
。可以通过洪水填充算法
来实现,比如下面这个游戏demo其中地图生成中就使用到了:
洪水填充算法可以用于生成迷宫。在迷宫生成过程中,先随机选择一个种子点,并使用洪水填充算法填充整个迷宫,然后随机移除一些墙壁,最终生成具有迷宫结构的地图。
4.4 区域选择
在图像编辑软件或地图编辑器中,洪水填充算法也可以用于区域选择。用户可以通过选择一个种子点,然后用洪水填充算法将与种子点相连通的区域选中,便于后续的编辑操作。
4.5 游戏地形生成
在游戏开发中,特别是策略游戏或沙盒游戏,洪水填充算法可用于生成游戏地图的地形。通过选择几个种子点,然后使用洪水填充算法填充不同类型的地形,如平原、山地、河流等,可以实现多样化的游戏地图。
4.6 色彩替换
洪水填充算法可以用于实现图片中的色彩替换。用户可以选择一个种子点和目标颜色,然后使用洪水填充算法将所有与种子点相连通且颜色相近的区域替换成目标颜色。
五、总结
以上就是洪水填充算法
全部的内容了,如果给你了提示、启发或者你感觉很有趣,请帮我点个赞吧!谢谢~
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)