区域边界规划算法

区域边界规划算法（共2篇）

区域边界规划算法 篇1

大气环境是综合自然环境(SNE)的重要组成部分,大气环境模型是武器装备仿真模型体系的有机组成部分.在SNE概念参考模型基础上,探讨了大气环境建模的概念和方法,比较了几种大气环境内部模型,提出了利用大气数值模式进行大气环境建模的具体实现方法.利用大气数值模式RAMS 4.3(Regional Atmospheric Modeling System)对我国东南沿海地区大气边界层风场进行了建模研究.

作 者：李鲲 徐幼平许丽人 LI Kun XU You-ping XU Li-ren 作者单位：李鲲,许丽人,LI Kun,XU Li-ren(北京市应用气象研究所,北京,100029)

徐幼平,XU You-ping(北京市应用气象研究所,北京,100029;中国科学院大气物理研究所大气科学和地球流体动力学数值模拟国家重点实验室,北京,100029)

区域边界规划算法 篇2

区域填充即给定一个区域边界，要求对边界范围内的所有像素点赋予指定的颜色。常见区域填充的算法有种子填充算法、线填充算法和边标志填充算法等。种子填充算法[1][2]基于栈结构或队列结构的搜索算法，填充速度慢，并且对大块区域填充会因堆栈溢出而导致填充程序崩溃。扫描线算法则是用水平扫描线按顺序从上往下扫描，计算出每根扫描线与区域边界产生的一系列交点，将这些交点按照x坐标排序，将排序后的交点依次成对取出作为左右边界点，以指定颜色对这些左右边界点画水平线段，区域被扫描完毕后，填充即完成。扫描线算法填充速度快，但需已知区域边界，并要计算出每根扫描线与区域边界的交点坐标，应用起来繁琐。对由曲线围成的未知边界坐标值的不规则区域的填充，难度可想而知。边标志算法[3]需勾画轮廓线, 在每条扫描线上找出各区段的边界像素对，然后对这些边界像素对之间的所有像素进行填充。文中提出一种新的算法，只需已知一个区域内的点或一个区域边界点，即能对未知边界坐标值的不规则单连通区域进行快速填充，并适应于任意复杂区域的填充。该算法应用边界扫描的方式找出正确匹配的区域左右边界点对，边界扫描完，所有成对的左右边界点即找出。然后，以指定颜色对这些成对的左右边界点画水平线段，即能完成填充，称之为“边界扫描”填充算法。

2 边界扫描填充算法

2.1 定义

定义1若给定点A和点B，至少存在一条坐标路径使得AA到达BB所经过的所有点的颜色皆与A且B的颜色相同，即称点A和点B相连通。

定义2若给定一个初始点为一块区域中的点，则周围与该初始点相连通的所有点皆为区域内点。

定义3令区域内点P的坐标为 (x, y) ，若该点往上下左右任意方向移一步，即x坐标加减1，或y坐标加减1，所得4个新点中至少有一点不是区域内点，则称点P为区域边界点。

定义4令区域内点P的坐标为 (x, y) ，若坐标为 (x-1, y) 的点不是区域内点，则称点P为区域左边界点;若坐标为 (x+，y) 的点不是区域内点，则称点P为区域右边界点;两者同时满足，则称点P既为区域左右边界点又为区域右边界点。

定义5假设在一条水平直线上存在n个区域左边界点和n个区域右边界点，对于其中的一个区域左边界点lPi (i∈{1, 2, 3，…，n}，有m个区域右边界点在lPi的右边 (m≤n) 。令这m个区域右边界点为rPj, j={k1, k2, k3…，km}。其中kt∈{1, 2, 3, …, n}, t={1, 2, 3…m}。

令|lPi-rPj|为lPi与rPj的距离，其中j={k1, k2, k3…，km}，k∈{k1, k2, k3…，km}，满足|lPi-rPj|=min{|lPi-rPj|}，j={k1, k2, k3…，km}，则称区域左边界点lPi和区域右边界点rPk为正确匹配的区域左右边界点对。

2.2 边界扫描填充原理

边界扫描填充需建立两个数据结构。第一，建立一个栈表Stack_boundPt，用来保存区域边界点的坐标及该坐标的状态信息(是区域右边界点还是左边界点);第二，建立一个线性表Store_line，用来保存正确匹配的区域左右边界点对。如图1所示。

边界扫描填充需给定一个初始区域右边界点(或区域左边界点)，或一个区域内点，若给定的是区域内点，则由这点水平扫描找到一个初始区域边界点。边界扫描填充采用从第一个初始区域边界点开始按逆时针或顺时针扫描，直到回到初始区域边界点为止。它利用栈[4]结构先进后出的特点，在扫描过程中找出处于同一水平直线上对应的区域左右边界点对。把找出的对应区域左右边界点对保存到线性表当中，并在扫描过程中不断修改此线性表中的区域左右边界点对，确保最后保存下来的区域左右边界点对是正确匹配的。然后，以这些正确匹配的左右边界点作为端点依次画水平线段来完成区域的填充。

算法详细原理及步骤如下所述：

(1)判断新区域边界点(即新找到的区域边界点)，若回到初始区域边界点，则执行第6步;否则，执行第2步。

(2)判断新区域边界点的状态(是区域左边边界点还是区域右边界点)，若它为区域右边界点(或区域左边界点)，查看栈Stack_boundPt的栈顶单元里保存的边界点是否是区域左边界点(或区域右边界点)，且是否和它在同一水平线上(即它们的y坐标是否相等)，且是否在它的左边(或右边)。若同时满足以上三个条件，则取出栈Stack_boundPt的栈顶区域左边界点(或区域右边界点)，把它们组成一对区域左右边界点对保存到线性表Store_line中，并往下执行第5步;若不满足则执行第3步。

(3)依次查看线性表保存的区域左右边界点对，判断此新区域边界点是否处于某对区域左右边界点对的水平之间。若存在一对区域左右边界点符合此条件，则根据第2步对新区域边界点的状态判断情况，若它为区域右边界点(或区域左边界点)，把线性表中符合条件的区域左右边界点对的区域右边界点(或区域左边界点)修改成新区域右边界点(或新区域左边界点)，并将原区域左右边界点对中的区域右边界点(或区域左边界点)入栈Stack_boundPt，且设置状态boundPtState为1(或0)，接下来执行第5步;若不存在符合条件的区域左右边界点对，则执行第4步。

(4)将新区域边界点入栈Stack_boundPt，并根据第2步对新区域边界点的状态判断情况，若它为区域右边界点(或区域左边界点)，设置状态boundPtState为1(或0)。往下执行第5步。

(5)按逆时针扫描，找出下一个新区域右边界点或新区域左边界点，并往上执行第1步。

(6)取出线性表Store_line中所有正确匹配区域左右边界点对作为端点，以指定颜色依次画水平线段完成区域的填充。根据上述算法原理及步骤，结合图分9个阶段，如图3所示，简要地讲解图2所示(图中每个方格代表一个像素点)的一个被放大的不规则区域的填充过程。假如给定初始区域右边界点P0 (x0, y0) ，按逆时针方向扫描。

第1阶段，P0, P1, P2, P3, P4, P5会依次入栈，如图(a)所示。

第2阶段，P5, P4, P3, P2, P1, P0会依次出栈分别与P6, P7, P8, P9, P10, P11组成区域左右边界点对存入线性表Store_line中，如图(b)所示。

第3阶段，P12, P13, P14会依次入栈Stack_boundPt，如图(c)所示。

第4阶段，P14, P13, P12会依次出栈分别与P15, P16, P17组合成区域左右边界点对存入线性表Store_line中，如图(d)所示。

第5阶段，线性表Store_line中的P0, P1点会依次被修改成P18, P19，且P0, P1依次入栈Stack_boundPt，如图(e)所示。

第6阶段，P1, P0会依次出栈分别与P20, P21组成区域左右边界点对存入线性表Store_line中，如图(f)所示。

第7阶段，P22, P23依次入栈Stack_boundPt，如图(g)所示。

第8阶段，P23, P22会依次出栈分别与P24, P25组成区域左右边界点对存入线性表Store_line中，如图(h)所示。到此边界扫描完毕。

第9阶段，取出线性表Store_line中所有正确匹配区域左右边界点对作为左右端点，以指定颜色依次画水平线段完成区域的填充。

2.3 算法分析

与扫描线填充算法相比较，边界扫描算法不需知道区域边界，即可完成未知边界坐标值的任意复杂区域的填充，这有效的解决了扫描线填充算法应用受限制的缺陷。边界扫描填充关键在于找出所有正确匹配区域左右边界点对，下面分析找出所有正确匹配区域左右边界点对的时间复杂度。

经分析，该时间复杂度主要为边界扫描的时间复杂度与扫描过程中查看线性表的时间复杂度之和。因区域边界点坐标相邻，变化幅度不大，即边界扫描时间复杂度约为O (n) 。

扫描过程中查看线性表的时间复杂度与给定的初始区域边界点有关。设扫描过程中查看线性表的执行时间为T (k) 。如图4，若给定的初始边界点为P0 (P0为区域最低端的区域右边界点), 则按逆时针扫描到最顶端的区域右边界点时，需查看线性表n次(区域高为n个像素点)，但因此阶段中线性表一直为空，使得每查看一次线性表执行的语句频度为0，即T (k) =n*0=0。继续从最顶端区域左边界点扫描到最低端区域左边界点时，根据算法特点不需查看线性表，因此，整个扫描过程中因查看线性表执行的语句频度总和为0。由此可以得出从P0点开始扫描，找出所有正确匹配区域左右边界点对的时间复杂度即为边界扫描时间复杂度，约为O (n) 。若给定区域右边界点P1为初始边界点，按逆时针扫描，从P1到最顶端区域右边界点与前面情况相同，即执行的语句频度为m*0=0。继续从最顶端区域左边界点扫描到区域左边界点P2时不需查看线性表，但从P2扫描到最低端区域左边界点时，需查看线性表次，因线性表此时保存了m个区域左右边界点对，即这个过程语句执行频度T (k) =m*t=t* (n-t) =nt-t2。由此得出从P1开始扫描，与第一种情况比较，增加了时间复杂度。

查看线性表时间复杂度还与区域的形状有关，如图4所示区域，时间复杂度可以小到约为O (n) 。而对于图5所示的区域，假定初始区域边界点如图所示，则在扫描过程中需查看线性表约2*m*n次，假设每查看一次线性表T (k) =k，则查看线性表的语句频度总和约为2*m*n*k，即时间复杂度为O (n3)。因扫描边界的时间复杂度为O (n)，故总的时间复杂度为O (n3)+O (n) ，即约为O (n3)。

综上，应用边界扫描填充，找出所有正确匹配区域左右边界点对的时间复杂度由初始区域边界点的选择和区域的形状决定，最好情况为O (n) ，最坏情况为O (n3)。

2.4 VC++程序实现结果

图6所示为不规则区域填充前与填充后的对照图。实践表明边界扫描算法能实现对任意复杂单连通区域的填充，且填充效率较高。

3 结语

经过实践证明，文中提出的边界扫描区域填充算法易于实现，便于理解。它能实现对未知边界坐标的不规则区域进行快速填充，并能对诸如曲线这种线状图形以及任意复杂单连通区域进行填充，弥补了扫描线填充算法应用受限制的缺陷。该算法是针对单连通区域的填充提出来的一种新算法，但它对实现多连通区域的填充给予启发，通过对算法的改进即可在此基础上找到一种实现多连通区域快速填充算法。

参考文献

[1]潘荣江, 孟祥旭.一种基于快速行进法的区域填充算法[J].工程图学学报, 2005, 02.

[2]刘小园.VB实现不规则区域填充[J].计算机与信息技术, 2006, 6.

[3]吴章文, 杨代论, 勾成俊, 等.区域填充极点判别方法[J].计算机辅助设计与图形学学报, 2003, 18 (8) .