文档章节

洪水填充(Flood fill)算法

如比如比
 如比如比
发布于 2015/06/20 04:28
字数 500
阅读 2437
收藏 15

洪水填充(Flood fill)算法

从一个起始节点开始把附近与其连通的节点提取出或填充成不同颜色颜色,直到封闭区域内的所有节点都被处理过为止,是从一个区域中提取若干个连通的点与其他相邻区域区分开(或分别染成不同颜色)的经典算法。

因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。在GNU Go和扫雷中,Flood Fill算法被用来计算需要被清除的区域。


洪水填充算法接受三个参数:起始节点,目标节点特征和针对提取对象要执行的处理。


目前有许多实现方式,基本上都显式的或隐式的使用了队列或者栈。

洪水填充算法实现最常见有四邻域填充法(不考虑对角线方向的节点),八邻域填充法(考虑对角线方向的节点),基于扫描线填充方法。

根据实现又可以分为递归与非递归(基于栈)。

最简单的实现方法是采用深度优先搜索的递归方法,也可以采用广度优先搜索的迭代来实现。

基于递归实现的泛洪填充算法有个致命的缺点,就是对于大的区域填充时可能导致栈溢出错误,

基于扫描线的算法实现了一种非递归的洪水填充算法。


除提出连通区域外,还可以应用于计算从某一节点开始,到可能到达其他所有节点的距离。比如解决像走迷宫这类的问题。


参考资料:

1.图像处理之泛洪填充算法(Flood Fill Algorithm)

http://blog.csdn.net/jia20003/article/details/8908464

2.Flood Fill Algorithm

http://acm.nudt.edu.cn/~twcourse/ConnectedComponentLabeling.html#a1

3.QuickFill: An efficient flood fill algorithm.

http://www.codeproject.com/Articles/6017/QuickFill-An-efficient-flood-fill-algorithm


© 著作权归作者所有

共有 人打赏支持
如比如比
粉丝 126
博文 178
码字总数 286951
作品 0
日本
程序员
私信 提问
加载中

评论(1)

眹希
眹希
谢谢分享
[LeetCode] Flood Fill 洪水填充

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535). Given a coordinate (sr, sc) representing the starti......

机器的心脏
2017/12/05
0
0
PHP 抵御 DDoS 攻击--IOSEC

HTTP Anti Flood/DoS Security Module 是 PHP 抵御 DDOS 洪水攻击模块 测试DEMO:http://www.iosec.org/test.php (demo) IOSEC 可以减弱 Web 应用级别的 HTTP Flood 攻击,可以检测到 HTTP F......

MyLong
2014/12/19
660
0
DDoS

什么是DDoS攻击 DDoS是英文Distributed Denial of Service的缩写,中文意思是“分布式拒绝服务”。那什么又是拒绝服务呢?用户可以这样理解,凡是能导致合法用户不能进行正常的网络服务的行为...

企图穿越
2010/05/19
234
0
详解SYN Flood攻击原理与防范

YN Flood是当前最流行的DoS(拒绝服务攻击)与DDoS(分布式拒绝服务攻击)的方式之一,它是利用TCP协议缺陷,发送大量伪造的TCP连接请求,从而使得被攻击方资源耗尽(CPU满负荷或内存不足)的攻击方...

wcczrx
2017/07/31
0
0
DDOS攻击原理及防护方法论

从 07年的爱沙尼亚DDOS信息战,到今年广西南宁30个网吧遭受到DDOS勒索,再到新浪网遭受DDOS攻击无法提供对外服务500多分钟。 DDOS愈演愈烈,攻击事件明显增多,攻击流量也明显增大,形势十分...

bazhinv
2016/02/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Hibernate SQLite方言

以下代码有参考过github上国外某位大佬的,在发文的最新稳定版Hibernate上是可用的,有时间再仔细分析一下 import org.hibernate.dialect.Dialect;import org.hibernate.dialect.function.S...

CHONGCHEN
今天
3
0
CentOS 7 MariaDB搭建主从服务器

本文编写环境为CentOS7。确保关闭SELinux,关闭防火墙或者防打开指定端口。具体信息如下 #master[root@promote ~]# cat /etc/redhat-release CentOS Linux release 7.6.1810 (Core) [r...

白豆腐徐长卿
今天
10
0
介绍python中运算符优先级

下面这个表给出Python的运算符优先级,从最低的优先级(最松散地结合)到最高的优先级(最紧密地结合)。这意味着在一个表达式中,Python会首先计算表中较下面的运算符,然后在计算列在表上部...

问题终结者
今天
3
0
Spring Boot 2.x基础教程:快速入门

简介 在您第1次接触和学习Spring框架的时候,是否因为其繁杂的配置而退却了?在你第n次使用Spring框架的时候,是否觉得一堆反复黏贴的配置有一些厌烦?那么您就不妨来试试使用Spring Boot来让...

程序猿DD
昨天
10
0
SpringSecurity认证流程源码级详解

SpringSecurity认证流程源码级详解 认证流程说明 认证结果如何在多个请求之间共享 获取认证用户信息

chendom
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部