Android多边形区域扫描线种子填充算法的示例
作者:吹泡泡的小猫 发布时间:2023-05-25 00:27:24
1.3扫描线种子填充算法
1.1和1.2节介绍的两种种子填充算法的优点是非常简单,缺点是使用了递归算法,这不但需要大量栈空间来存储相邻的点,而且效率不高。为了减少算法中的递归调用,节省栈空间的使用,人们提出了很多改进算法,其中一种就是扫描线种子填充算法。扫描线种子填充算法不再采用递归的方式处理“4-联通”和“8-联通”的相邻点,而是通过沿水平扫描线填充像素段,一段一段地来处理“4-联通”和“8-联通”的相邻点。这样算法处理过程中就只需要将每个水平像素段的起始点位置压入一个特殊的栈,而不需要象递归算法那样将当前位置周围尚未处理的所有相邻点都压入堆栈,从而可以节省堆栈空间。应该说,扫描线填充算法只是一种避免递归,提高效率的思想,前面提到的注入填充算法和边界填充算法都可以改进成扫描线填充算法,下面介绍的就是结合了边界填充算法的扫描线种子填充算法。
扫描线种子填充算法的基本过程如下:当给定种子点(x, y)时,首先分别向左和向右两个方向填充种子点所在扫描线上的位于给定区域的一个区段,同时记下这个区段的范围[xLeft, xRight],然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段,并依次保存下来。反复这个过程,直到填充结束。
扫描线种子填充算法可由下列四个步骤实现:
(1) 初始化一个空的栈用于存放种子点,将种子点(x, y)入栈;
(2) 判断栈是否为空,如果栈为空则结束算法,否则取出栈顶元素作为当前扫描线的种子点(x, y),y是当前的扫描线;
(3) 从种子点(x, y)出发,沿当前扫描线向左、右两个方向填充,直到边界。分别标记区段的左、右端点坐标为xLeft和xRight;
(4) 分别检查与当前扫描线相邻的y - 1和y + 1两条扫描线在区间[xLeft, xRight]中的像素,从xLeft开始向xRight方向搜索,若存在非边界且未填充的像素点,则找出这些相邻的像素点中最右边的一个,并将其作为种子点压入栈中,然后返回第(2)步;
这个算法中最关键的是第(4)步,就是从当前扫描线的上一条扫描线和下一条扫描线中寻找新的种子点。这里比较难理解的一点就是为什么只是检查新扫描线上区间[xLeft, xRight]中的像素?如果新扫描线的实际范围比这个区间大(而且不连续)怎么处理?我查了很多计算机图形学的书籍和论文,好像都没有对此做过特殊说明,这使得很多人在学习这门课程时对此有挥之不去的疑惑。本着“毁人”不倦的思想,本文就罗嗦解释一下,希望能解除大家的疑惑。
如果新扫描线上实际点的区间比当前扫描线的[xLeft, xRight]区间大,而且是连续的情况下,算法的第(3)步就处理了这种情况。如图(4)所示:
图(4) 新扫描线区间增大且连续的情况
假设当前处理的扫描线是黄色点所在的第7行,则经过第3步处理后可以得到一个区间[6,10]。然后第4步操作,从相邻的第6行和第8行两条扫描线的第6列开始向右搜索,确定红色的两个点分别是第6行和第8行的种子点,于是按照顺序将(6, 10)和(8, 10)两个种子点入栈。接下来的循环会处理(8, 10)这个种子点,根据算法第3步说明,会从(8, 10)开始向左和向右填充,由于中间没有边界点,因此填充会直到遇到边界为止,所以尽管第8行实际区域比第7行的区间[6,10]大,但是仍然得到了正确的填充。
如果新扫描线上实际点的区间比当前扫描线的[xLeft, xRight]区间大,而且中间有边界点的情况,算法又是怎么处理呢?算法描述中虽然没有明确对这种情况的处理方法,但是第4步确定上、下相邻扫描线的种子点的方法,以及靠右取点的原则,实际上暗含了从相邻扫描线绕过障碍点的方法。下面以图(5)为例说明:
图(5) 新扫描线区间增大且不连续的情况
算法第3步处理完第5行后,确定了区间[7, 9],相邻的第4行虽然实际范围比区间[7, 9]大,但是因为被(4, 6)这个边界点阻碍,使得在确定种子点(4, 9)后向左填充只能填充右边的第7列到第10列之间的区域,而左边的第3列到第5列之间的区域没有填充。虽然作为第5行的相邻行,第一次对第4行的扫描根据靠右原则只确定了(4, 9)一个种子点。但是对第3行处理完后,第4行的左边部分作为第3行下边的相邻行,再次得到扫描的机会。第3行的区间是[3, 9],向左跨过了第6列这个障碍点,第2次扫描第4行的时候就从第3列开始,向右找,可以确定种子点(4, 5)。这样第4行就有了两个种子点,就可以被完整地填充了。
由此可见,对于有障碍点的行,通过相邻边的关系,可以跨越障碍点,通过多次扫描得到完整的填充,算法已经隐含了对这种情况的处理。根据本节总结的四个步骤,扫描线种子填充算法的实现如下:
void SearchLineNewSeed(std::stack<Point>& stk, int xLeft, int xRight,
int y, int new_color, int boundary_color)
{
int xt = xLeft;
bool findNewSeed = false;
while(xt <= xRight)
{
findNewSeed = false;
while(IsPixelValid(xt, y, new_color, boundary_color) && (xt < xRight))
{
findNewSeed = true;
xt++;
}
if(findNewSeed)
{
if(IsPixelValid(xt, y, new_color, boundary_color) && (xt == xRight))
stk.push(Point(xt, y));
else
stk.push(Point(xt - 1, y));
}
/*向右跳过内部的无效点(处理区间右端有障碍点的情况)*/
int xspan = SkipInvalidInLine(xt, y, xRight, new_color, boundary_color);
xt += (xspan == 0) ? 1 : xspan;
/*处理特殊情况,以退出while(x<=xright)循环*/
}
}
FillLineRight()和FillLineLeft()两个函数就是从种子点分别向右和向左填充颜色,直到遇到边界点,同时返回填充的点的个数。这两个函数返回填充点的个数是为了正确调整当前种子点所在的扫描线的区间[xLeft, xRight]。
SearchLineNewSeed()函数完成算法第4步所描述的操作,就是在新扫描线上寻找种子点,并将种子点入栈,新扫描线的区间是xLeft和xRight参数确定的:
void SearchLineNewSeed(std::stack<Point>& stk, int xLeft, int xRight,
int y, int new_color, int boundary_color)
{
int xt = xLeft;
bool findNewSeed = false;
while(xt <= xRight)
{
findNewSeed = false;
while(IsPixelValid(xt, y, new_color, boundary_color) && (xt < xRight))
{
findNewSeed = true;
xt++;
}
if(findNewSeed)
{
if(IsPixelValid(xt, y, new_color, boundary_color) && (xt == xRight))
stk.push(Point(xt, y));
else
stk.push(Point(xt - 1, y));
}
/*向右跳过内部的无效点(处理区间右端有障碍点的情况)*/
int xspan = SkipInvalidInLine(xt, y, xRight, new_color, boundary_color);
xt += (xspan == 0) ? 1 : xspan;
/*处理特殊情况,以退出while(x<=xright)循环*/
}
}
最外层的while循环是为了保证区间[xLeft, xRight]右端被障碍点分隔成多段的情况能够得到正确处理,通过外层while循环,可以确保为每一段都找到一个种子点(对于障碍点在区间左端的情况,请参考图(5)所示实例的解释,是隐含在算法中完成的)。内层的while循环只是为了找到每一段最右端的一个可填充点作为种子点。SkipInvalidInLine()函数的作用就是跳过区间内的障碍点,确定下一个分隔段的开始位置。循环内的最后一行代码有点奇怪,其实只是用了一个小“诡计”,确保在遇到真正的边界点时循环能够正确退出。这不是一个值得称道的做法,实现此类软件控制有更好的方法,本文这样做的目的只是为了使代码简短一些,让读者把注意力集中在算法处理逻辑上,而不是冗杂难懂的循环控制条件上。
算法的实现其实就在ScanLineSeedFill()和SearchLineNewSeed()两个函数中,神秘的扫描线种子填充算法也并不复杂,对吧?至此,种子填充算法的几种常见算法都已经介绍完毕,接下来将介绍两种适合矢量图形区域填充的填充算法,分别是扫描线算法和边标志填充算法,注意适合矢量图形的扫描线填充算法有时又被称为“有序边表法”,和扫描线种子填充算法是有区别的。
来源:https://blog.csdn.net/orbit/article/details/7343236
猜你喜欢
- SimpleDateFormat类:SimpleDateFormat是-一个以与语言环境有关的方式来格式化和解析日期的具体类。进行格式化(日
- 今天看《第一行代码》上面关于拍照和从相册选取图片那一部分,发现始终出不来效果,所以搜索其他资料学习一下相关知识,写一个简单的Demo。&nb
- 我们深知在操作Java流对象后要将流关闭,但往往事情不尽人意,大致有以下几种不能一定将流关闭的写法:1.在try中关流,而没在finally
- 工作以来,代码越写越多,程序也越来越臃肿,效率越来越低,对于我这样一个追求完美的程序员来说,这是绝对不被允许的,于是除了不断优化程序结构外,
- 参考链接:狂神的Swagger笔记号称世界上最流行的API框架Restful Api 文档在线自动生成器 => API 文档 与API
- 基于SSM+Mysql+Maven+HTML实现的员工绩效管理系统。该系统只有后台页面,后台前端框架使用的是layui官网推荐后台界面。角色
- 本文实例为大家分享了Android ViewPager实现页面左右切换的具体代码,供大家参考,具体内容如下主界面viewpager.xml:
- 1、接口:接口与抽象类一样,也是表示某种规则,一旦使用了该规则,就必须实现相关的方法。对于C#语言而言,由于只能继承自一个父类,因此若有多个
- 本文实例为大家分享了Android九宫格图片展示的具体代码,供大家参考,具体内容如下XmlHelperusing System.Xml;us
- 一、Maven生命周期、阶段、目标 &nbs
- 现在很多app的首页都有一个倒计时控件,比如说3秒或者5秒自动跳转界面,或者点击控件直接跳过首先,自定义控件CircleProgressba
- SpringMVC的数据响应SpringMVC的数据响应方式①页面跳转直接返回字符串(如在一个方法中,return了一个"xxx.
- 前言我们大家平时长时间打代码的时候肯定会感到疲惫和乏味,这个时候一边播放自己喜欢的音乐,一边继续打代码,心情自然也愉快很多。音乐带给人的听觉
- 简介CAS的原理其实很简单,为了保证在多线程环境下我们的更新是符合预期的,或者说一个线程在更新某个对象的时候,没有其他的线程对该对象进行修改
- 前言我们在 WPF 中使用绑定时可以使用 ElementName=Foo 这样的写法,并且还能够真的在运行时找到这个名称对应的对象,是因为
- 背景公司线上有个tomcat服务,里面合并部署了大概8个微服务,之所以没有像其他微服务那样单独部署,其目的是为了节约服务器资源,况且这8个服
- 一、简介 线程池类为 java.util.concurrent.ThreadPoolExecutor,常用构造方法为:ThreadPoolE
- Thread dumps(线程转储)能帮助我们判断 CPU 峰值、死锁、内存异常、应用反应迟钝、响应时间变长和其他系统问题。一些在线的分析工
- 背景介绍在开发应用过程中经常会遇到显示一些不同的字体风格的信息犹如默认的LockScreen上面的时间和充电信息。对于类似的情况,可能第一反
- 本文实例为大家分享了C#类的多态性,供大家参考,具体内容如下第一种:编译时的多态性,直接这样说不知道说啥?程序执行过程主要分为三步:编译,链