Day 82:洪水填充
18年11月20日 · 东南大学 刘杰 2000 人阅读
1、需求分析
如下图所示,内圈100所包围的区域为一个封闭区域(同理,内圈100与外圈100之间的区域也为一个封闭区域)。
首先给定一个种子点,比如,该种子点落在内圈100的某个数值0处,那么要做的任务就是找到数值0所联通的最大封闭区域;
然后按照约定的颜色,本例中也就是用约定的数字,如8进行填充,结果如图2所示。当然,实际情况中,封闭区域通常并非标准的矩形,很有可能是曲曲折折的。
想一想我们在ps中常用的一些填充的操作,是不是跟这个需求很类似。
图2
2、算法分析
实现该需求的算法有多种,本文采用的是线性扫描法。如下图所示,本算法主要包括两个循环:
外循环每次从起始查询点列表中弹出(取出并从列表中移除)第一个元素,为内循环提供每次扫描的起始位置;
内循环根据外循环提供的起始位置,向右进行扫描填充,同时向上向下搜索,将潜在的起始查询点到找出并添加到起始查询点列表中。
实际上,可以借助计算机视觉库OpenCV的cv2库,将本算例输出的填充后的二维数据表转化成伪彩色图,则更加形象,类似下图所示,读者可根据兴趣自行拓展该部分内容。
Python3Turtle