边界填充算法

⑴ web填充怎么设置

web填充设置：单击上面工具栏中的“设计”按钮。下一步点击“页面颜色”按钮。单击颜色下拉菜单中的填充效果按钮。点击填充效果屏幕上的“图片”按钮。点击屏幕上的”选择图像”按钮。

<Meta http-equiv="Page-Enter" Content="blendTrans(Duration=0.5)">，<Meta http-equiv="Page-Exit" Content="blendTrans(Duration=0.5)">。

blendTrans其实就是一种动态滤镜效果，当然还有其他的方法也可以产生这种动态滤镜效果，<Meta http-equiv="Page-Enter" Content="revealTrans(ration=x, transition=y)">。

边标志填充算法步骤：

1、用边界色画出多边形轮廓线,也就是将多边形边界所经过的象素打上边标志。

2、为了缩小范围,加快填充速度,须找出多边形的最小包围盒：xmin、ymin、xmax、ymax。

3、逐条扫描线进行处理,初始时标志为假,对每条扫描线依从左往右的顺序,逐个访问该扫描线上的象素。每遇到边界象素,标志取反。然后,按照标志是否为真决定象素是否为填充色。

⑵ 地理信息系统知识点

什么是地理信息系统篇一：地理信息系统的基本概念

（一）数据与信息

数据是一种未经加工的原始资料，是通过数字化或记录下来可以被鉴别的符号。数字、文字、符号、图像都是数据。

信息（Information）是用文字、数字、符号、语言、图像等介质来表示事件、事物、现象等的内容、数量或特征，从而向人们（或系统）提供关于现实世界新的事实和知识，作为生产、建设、经营、管理、分析和决策的依据。信息具有客观性、适用性、可传输性和共享性等特征。信息来源于数据（Data）。

数据是客观对象的表示，而信息则是数据内涵的意义，是数据的内容和解释。例如，从实地或社会调查数据中可获取到各种专门信息；从测量数据中可以抽取出地面目标或物体的形状、大小和位置等信息；从遥感图像数据中可以提取出各种地物的图形大小和专题信息。

（二）地理信息

地理信息是指表征地理圈或地理环境固有要素或物质的数量、质量、分布特征、联系和规律的数字、文字、图象和图形的总和。地理信息是有关地理实体的性质、特征和运动状态的表征和一切有用的知识，它是对表达地理特征与地理现象之间关系的地理数据的解释。而地理数据则是各种地理特征和现象间关系的符号化表示，包括空间位置、属性特征（简称属性）及时域特征三部分。空间位置数据描述地物所在位置。这种位置既可以根据大地参照系定义，如大地经纬度坐标，也可以定义为地物间的相对位置关系，如空间上的相邻、包含等；属性数据有时又称非空间数据，是属于一定地物、描述其特征的定性或定量指标。时域特征是指地理数据采集或地理现象发生的时刻/时段。时间数据对环境模拟分析非常重要，正受到地理信息系统学界越来越多的重视。空间位置、属性及时间是地理空间分析的三大基本要素。

地理信息除了具有信息的一般特性，还具有以下独特特性：

（1）空间分布性。地理信息具有空间定位的特点，先定位后定性，并在区域上表现出分布式特点，其属性表现为多层次，因此地理数据库的分布或更新也应是分布式。

（2）数据量大。地理信息既有空间特征，又有属性特征，另外地理信息还随着时间的变化而变化，具有时间特征，因此其数据量很大。尤其是随着全球对地观测计划不断发展，我们每天都可以获得上万亿兆的关于地球资源、环境特征的数据。这必然对数据处理与分析带来很大压力。

（3）信息载体的多样性。地理信息的第一载体是地理实体的物质和能量本身，除此之外，还有描述地理实体的文字、数字、地图和影像等符号信息载体以及纸质、磁带、光盘等物理介质载体。对于地图来说，它不仅是信息的载体，也是信息的传播媒介。

（三）地理信息系统

地理信息系统（GeographicInformationSystem或Geo－Informationsystem，GIS）有时又称为“地学信息系统”或“资源与环境信息系统”。它是一种特定的十分重要的空间信息系统。它是在计算机硬、软件系统支持下，对整个或部分地球表层（包括大气层）空间中的有关地理分布数据进行采集、储存、管理、运算、分析、显示和描述的技术系统。地理信息系统处理、管理的对象是多种地理空间实体数据及其关系，包括空间定位数据、图形数据、遥感图像数据、属性数据等，用于分析和处理在一定地理区域内分布的各种现象和过程，解决复杂的规划、决策和管理问题。

通过上述的分析和定义可提出GIS的如下基本概念：

1、GIS的物理外壳是计算机化的技术系统，它又由若干个相互关联的子系统构成，如数据采集子系统、数据管理子系统、数据处理和分析子系统、图像处理子系统、数据产品输出子系统等，这些子系统的优劣、结构直接影响着GIS的硬件平台、功能、效率、数据处

理的方式和产品输出的类型。

2、GIS的操作对象是空间数据，即点、线、面、体这类有三维要素的地理实体。空间数据的最根本特点是每一个数据都按统一的地理坐标进行编码，实现对其定位、定性和定量的描述、这是GIS区别于其它类型信息系统的根本标志，也是其技术难点之所在。

3、GIS的技术优势在于它的数据综合、模拟与分析评价能力，可以得到常规方法或普通信息系统难以得到的重要信息，实现地理空间过程演化的模拟和预测。

4、GIS与测绘学和地理学有着密切的关系。大地测量、工程测量、矿山测量、地籍测量、航空摄影测量和遥感技术为GIS中的空间实体提供各种不同比例尺和精度的定位数；电子速测仪、GPS全球定位技术、解析或数字摄影测量工作站、遥感图像处理系统等现代测绘技术的使用，可直接、快速和自动地获取空间目标的数字信息产品，为GIS提供丰富和更为实时的信息源，并促使GIS向更高层次发展。地理学是GIS的理论依托。有的学者断言，“地理信息系统和信息地理学是地理科学第二次革命的主要工具和手段。如果说GIS的兴起和发展是地理科学信息革命的一把钥匙，那么，信息地理学的兴起和发展将是打开地理科学信息革命的一扇大门，必将为地理科学的发展和提高开辟一个崭新的天地”。GIS被誉为地学的第三代语言——用数字形式来描述空间实体。

GIS按研究的范围大小可分为全球性的、区域性的和局部性的；按研究内容的不同可分为综合性的与专题性的。同级的各种专业应用系统集中起来，可以构成相应地域同级的区域综合系统。在规划、建立应用系统时应统一规划这两种系统的发展，以减小重复很费，提高数据共享程度和实用性。

什么是地理信息系统篇二：地理信息系统名词解释大全(整理版本)

地理信息系统作为信息技术的一种，是在计算机硬、软件的支持下，以地理空间数据库（GeospatialDatabase）为基础，以具有空间内涵的地理数据为处理对象，运用系统工程和信息科学的理论，采集、存储、显示、处理、分析、输出地理信息的计算机系统，为规划、管理和决策提供信息来源和技术支持。简单地说，GIS就是研究如何利用计算机技术来管理和应用地球表面的空间信息，它是由计算机硬件、软件、地理数据和人员组成的有机体，采用地理模型分析方法，适时提供多种空间的和动态的地理信息，为地理研究和地理决策服务的计算机技术系统。地理信息系统属于空间型信息系统。

地理信息是指表征地理圈或地理环境固有要素或物质的数量、质量、分布特征、联系和规律等的数字、文字、图像和图形等的总称；它属于空间信息，具有空间定位特征、多维结构特征和动态变化特征。

地理信息科学与地理信息系统相比，它更加侧重于将地理信息视作为一门科学，而不仅仅是一个技术实现，主要研究在应用计算机技术对地理信息进行处理、存储、提取以及管理和分析过程中提出的一系列基本问题。地理信息科学在对于地理信息技术研究的同时，还指出了支撑地理信息技术发展的基础理论研究的重要性。

地理数据是以地球表面空间位置为参照，描述自然、社会和人文景观的数据，主要包括数字、文字、图形、图像和表格等。

地理信息流即地理信息从现实世界到概念世界，再到数字世界（GIS），最后到应用领域。

数据是通过数字化或记录下来可以被鉴别的符号，是客观对象的表示，是信息的表达，只有当数据对实体行为产生影响时才成为信息。

信息系统是具有数据采集、管理、分析和表达数据能力的系统，它能够为单一的或有组织的决策过程提供有用的信息。包括计算机硬件、软件、数据和用户四大要素。

四叉树数据结构是将空间区域按照四个象限进行递归分割（2n×2n，且n≥1），直到子象限的数值单调为止。凡数值（特征码或类型值）呈单调的单元，不论单元大小，均作为最后的存储单元。这样，对同一种空间要素，其区域网格的大小，随该要素分布特征而不同。

不规则三角网模型简称TIN，它根据区域有限个点集将区域划分为相连的三角面网络，区域中任意点落在三角面的顶点、边上或三角形内。如果点不在顶点上，该点的高程值通常通过线性插值的方法得到（在边上用边的两个顶点的高程，在三角形内则用三个顶点的高程）。

拓扑关系拓扑关系是指网结构元素结点、弧段、面域之间的空间关系，主要表现为拓扑邻接、拓扑关联、拓扑包含。根据拓扑关系，不需要利用坐标或距离，可以确定一种地理实体相对于另一种地理实体的位置关系，拓扑数据也有利于空间要素的查询。

拓扑结构为在点、线和多边形之间建立关联，以及彻底解决邻域和岛状信息处理问题而必须建立的数据结构。这种结构应包括以下内容：唯一标识，多边形标识，外包多边形指针，邻接多边形指针，边界链接，范围（最大和最小x、y坐标值）。

游程编码是逐行将相邻同值的网格合并，并记录合并后网格的值及合并网格的长度，其目的是压缩栅格数据量，消除数据间的冗余。

空间数据结构是指适合于计算机系统存储、管理和处理的地学图形的逻辑结构，是地理实体的空间排列方式和相互关系的抽象描述。

矢量数据结构是利用欧几里得几何学中的点、线、面及其组合体来表示地理实体空间分布的一种数据组织方式。这种数据组织方式能最好地逼近地理实体的空间分布特征，数据精度高，数据存储的冗余度低，便于进行地理实体的网络分析，但对于多层空间数据的叠合分析比较困难。

栅格数据结构基于栅格模型的数据结构简称为栅格数据结构，指将空间分割成有规则的网格，在各个网格上给出相应的属性值来表示地理实体的一种数据组织形式。

空间索引是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息。作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。

空间数据编码是指将数据分类的结果，用一种易于被计算机和人识别的符号系统表示出来的过程。编码的目的是用来提供空间数据的地理分类和特征描述，同时为了便于地理要素的输入、存储、管理，以及系统之间数据交换和共享的需要。

Delaunay三角网即由狄洛尼三角形组成的三角网，它是在地形拟合方面表现最出色的三角网，因此常被用于TIN的生成。狄洛尼三角形有三个最邻近的点连接而成，这三个相邻点对应的Voronoi多边形有一个公共的顶点，此顶点同时也是狄洛尼三角形外接圆的圆心。

Voronoi多边形即泰森多边形，它采用了一种极端的边界内插方法，只用最近的单个点进行区域插值。泰森多边形按数据点位置将区域分割成子区域，每个子区域包含一个数据点，各子区域到其内数据点的距离小于任何到其它数据点的距离，并用其内数据点进行赋值。

栅格数据压缩编码有键码、游程长度编码、块码和四叉树编码等。其目的，就是用尽可能少的数据量记录尽可能多的信息，其类型又有信息无损编码和信息有损编码之分。

边界代数算法边界代数多边形填充算法是一种基于积分思想的矢量格式向栅格格式转换算法，它适合于记录拓扑关系的多边形矢量数据转换为栅格结构。它不是逐点判断与边界的关系完成转换，而是根据边界的拓扑信息，通过简单的加减代数运算将边界位置信息动态地赋给各栅格点，实现了矢量格式到栅格格式的高速转换，而不需要考虑边界与搜索轨迹之间的关系，因此算法简单、可靠性好，各边界弧段只被搜索一次，避免了重复计算。

DIME文件美国人口普查局在1980年的人口普查中提出了双重独立地图编码文件。它含有调查获得的地理统计数据代码及大城市地区的界线的坐标值，提供了关于城市街道，住址范围以及与人口普查局的列表统计数据相关的地理统计代码的纲要图。在1990年的人口普查中，TIGER取代了DIME文件。

空间数据内插即通过已知点或分区的数据，推求任意点或分区数据的方法。空间数据压缩即从所取得的数据集合S中抽出一个子集A，这个自己作为一个新的信息源，在规定的精度范围内最好地逼近原集合，而又取得尽可能大的压缩比。

坐标变换实质是建立两个平面点之间的一一对应关系，包括几何纠正和投影转换，他们是空间数据处理的基本内容之一。

仿射变换是GIS数据处理中使用最多的一种几何纠正方法。它的主要特性为：同时考虑到因地突变形而引起的实际比例尺在x和y方向上的变形，因此纠正后的坐标数据在不同方向上的长度比将发生变化。

数据精度是考察数据质量的一个方面，即对现象描述的详细程度。精度低的数据并不一定准确度也低。

空间数据引擎是一种空间数据库管理系统的实现方法，即在常规数据库管理系统之上添加一层空间数据库引擎，以获得常规数据库管理系统功能之外的空间数据存储和管理的能力。代表性的是ESRI的SDE。

空间数据引擎在用户和异种空间数据库的数据之间提供了一个开放的接口，它是一种处于应用程序和数据库管理系统之间的中间件技术。使用不同厂商GIS的客户可以通过空间数据引擎将自身的数据提交给大型关系型DBMS，由DBMS统一管理；同样，客户也可以通过空间数据引擎从关系型DBMS中获取其他类型GIS的数据，并转化成客户可以使用的方式。

数据库管理系统是操作和管理数据库的软件系统，提供可被多个应用程序和用户调用的软件系统，支持可被多个应用程序和用户调用的数据库的建立、更新、查询和维护功能。

空间数据库是地理信息系统在计算机物理存储介质上存储的`与应用相关的地理空间数据的总和，一般是以一系列特定结构的文件的形式组织在存储介质之上的。

空间数据模型是关于现实世界中空间实体及其相互间联系的概念，为描述空间数据组织和设计空间数据库模式提供了基本的方法。一般而言，GIS空间数据模型由概念数据模型、逻辑数据模型和物理数据模型三个有机联系的层次所组成。

分布式数据库是一组数据的集合，这些数据在物理上分布于计算机网络的不同结点上，而逻辑上属于同一个系统。它具有分布性，同时在逻辑上互相关联。

对象－关系管理模式/型是指在关系型数据库中扩展，通过定义一系列操作空间对象（如点、线、面）的API函数，来直接存储和管理非结构化的空间数据的空间数据库管理模式。

缓冲区分析是根据分析对象的点、线、面实体，自动建立他们周围一定距离的带状区，用以识别这些实体或主体对邻近对象的辐射范围或影响度，以便为某项分析或决策提供依据。

叠合分析是指在统一空间参照系统条件下，每次将同一地区两个地理对象的图层进行叠合，以产生空间区域的多重属性特征，或建立地理对象之间的空间对应关系。

空间分析是基于空间数据的分析技术，它以地学原理为依托，通过分析算法，从空间数据中获取有关地理对象的空间位置、空间分布、空间形态、空间形成、空间演变等信息。

网络分析是运筹学模型中的一个基本模型，即对地理网络和城市基础设施网络进行地理分析和模型化。它的根本目的是研究、筹划一项网络工程如何安排，并使其运行效果最好。

透视图从数字高程模型绘制透视立体图是DEM的一个极其重要的应用。透视立体图能更好地反映地形的立体形态，非常直观。与采用等高线表示地形形态

相比有其自身独特的优点，更接近人们的直观视觉。调整视点、视角等各个参数值，就可从不同方位、不同距离绘制形态各不相同的透视图制作动画。

网络是一个由点、线的二元关系构成的系统，通常用来描述某种资源或物质在空间上的运动。

变量筛选分析是通过寻找一组相互独立的变量，使相互关联的复杂的多变量数据得到简化的空间统计分析方法。常用的有主成分分析法、主因子分析法、关键变量分析法等。

变量聚类分析是将一组数据点或变量，按照其在性质上亲疏远近的程度进行分类的空间统计分析方法。两个数据点在m为空间的相似性可以用这些点在变量空间的距离来度量。

数字地面模型简称DTM，是定义于二维区域上的一个有限项的向量序列，它以离散分布的平面点来模拟连续分布的地形。

数字高程模型当数字地面模型的地面属性为海拔高程时，则该模型即为数字高程模型。简称DEM。

GIS应用模型是根据具体的应用目标和问题，借助于GIS自身的技术优势，使观念世界中形成的概念模型，具体化为信息世界中可操作的机理和过程。

OGC即OpenGIS协会(OpenGISConsortium)其目的是使用户可以开放地操纵异质的地理数据，促进采用新的技术和商业方式来提高地理信息处理的互操作性(Interoperablity)，OGC会员主要包括GIS相关的计算机硬件和软件制造商，数据生产商以及一些高等院校，政府部门等，其技术委员会负责具体标准的制定工作。

开放式地理信息系统（OpenGIS）OpenGIS(,OGIS-开放的地理数据互操作规范)由美国OGC（开放地理信息系统协会）提出。其目标是，制定一个规范，使得应用系统开发者可以在单一的环境和单一的工作流中，使用分布于网上的任何地理数据和地理处理。它致力于消除地理信息应用之间以及地理应用与其它信息技术应用之间的藩篱，建立一个无“边界”的、分布的、基于构件的地理数据互操作环境，与传统的地理信息处理技术相比，基于该规范的GIS软件将具有很好的可扩展性、可升级性、可移植性、开放性、互操作性和易用性。

数据结构是地理实体的数据组织形式及其相互关系的抽象描述。

空间数据质量是对空间数据在表达空间位置、空间关系、专题特征以及时间等要素时，所能达到的准确性、一致性、完整性以及它们之间统一性的度量，一般描述为空间数据的可靠性和精度，用误差来表示。

数字地球是把浩瀚复杂的地球数据加以数字化、网络化，变成一个地球信息模型计划。是一种可以嵌入海量地理数据、多种分辨率、三维的地球表达，是对真实地球及其相关现象的统一性的数字化重现和认识。其核心思想有两点：一是用数字化手段统一处理地球问题；二是最大限度地利用信息资源。

虚拟现实也称虚拟环境或人工现实，是一种由计算机生成的高级人机交互系统，即构成一个以视觉感受为主，也包括听觉、触觉、嗅觉的可感知环境，演练者通过专门的设备可在这个环境中实现观察、触摸、操作、检测等试验，有身临其境之感。

地图投影是建立平面上的点（用平面直角坐标或极坐标表示）和地球表面上的点（用纬度和精度表示）之间的函数关系。

投影转换是从一种地图投影变换为另一种地图投影。其实质是建立两平面场之间及邻域双向连续点的一一对应的关系。

虚拟地理环境简称VGE，是基于地学分析模型、地学工程等的虚拟现实，它是地学工作者根据观测实验、理论假设等建立起来的表达和描述地理系统的空间分布以及过程现象的虚拟信息地理世界，一个关于地理系统的虚拟实验室，它允许地学工作者按照个人的知识、假设和意愿去设计修改地学空间关系模型、地学分析模型、地学工程模型等，并直接观测交互后的结果，通过多次的循环反馈，最后获取地学规律。

高斯-克吕格投影Gauss-KruegerProjection①是一种横轴等角切椭圆柱投影。它是将一椭圆柱横切于地球椭球体上，该椭圆柱面与椭球体表面的切线为一经线，投影中将其称为中央经线，然后根据一定的约束条件即投影条件，将中央经线两侧规定范围内的点投影到椭圆柱面上从而得到点的高斯投影。

②一种等角横切椭圆柱投影。其投影带中央子午线投影成直线且长度不变，赤道投影也为直线，并与中央子午线正交。

UTM投影全球横轴墨卡托投影的简称。是美国编制世界各地军用地图和地球资源卫星象片所采用的横轴墨卡托投影的一种变型投影。它规定中央经线长度比为0.9996。

电子地图当纸地图经过计算机图形图像系统光——电转换量化为点阵数字图像，经图像处理和曲线矢量化，或者直接进行手扶跟踪数字化后，生成可以为地理信息系统显示、修改、标注、漫游、计算、管理和打印的矢量地图数据文件，这种与纸地图相对应的计算机数据文件称为矢量化电子地图。

元数据[空间]是指描述空间数据的数据，它描述空间数据集的内容、质量、表示方式、空间参考、管理方式以及数据集的其他特征，是空间数据交换的基础，也是空间数据标准化与规范化的保证，在一定程度上为空间数据的质量提供了保障。

Web地理信息系统（WebGIS）是Web技术和GIS技术相结合，即利用Web技术来扩展和完善地理信息系统的一项新技术。从WWW的任一个节点，Internet用户可以浏览WebGIS站点中的空间数据、制作专题图、进行各种空间检索和空间分析。

GIS互操作互操作是指在异构环境下的两个或多个实体，尽管它们实现的语言、执行的环境和基于的模型不同，但仍然可以相互通信和协作，以完成某一特定任务。这些实体包括应用程序、对象、系统运行环境等。空间数据的互操作针对异构的数据库和平台，实现数据处理的互操作，与数据转换相比，它是“动态”的数据共享，独立于平台，具有高度的抽象性，是空间数据共享的发展方向。

组件式GIS是采用了面向对象技术和组件式软件的GIS系统（包括基础平台和应用系统）。其基本思想是把GIS的各大功能模块划分为几个组件，每个组件完成不同的功能。各个GIS组件之间，以及GIS组件与其它非GIS组件之间，都可以方便地通过可视化的软件开发工具集成起来，形成最终的GIS基础平台以及应用系统。

客户机/服务器结构即C/S结构，是一种分布式系统结构，在该体系中，客户端通常是同最终用户交互的应用软件系统，而服务器由一组协作的过程构成，为客户端提供服务。客户机和服务器通常运行相同的微内核，一个客户机/服务器机制可以有多个客户端，或者多个服务器，或者兼而有之。客户机/服务器模式基于简单的请求/应答协议，即客户端向服务器提出信息处理的请求，服务器端接收到请求并将请求解译后，根据请求的内容执行相应操作，并将操作结果传

⑶ 区域填充的主要思想和方法

扫描线种子填充算法思想
首先填充种子所在的尚未填充的一区段,然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段,如果存在,则依次把每个新区段最右端的象素作为种子放入堆栈。反复这个过程,直到堆栈为空。
扫描线种子填充算法步骤 1、初始化堆栈。 2、种子压入堆栈。 3、While（堆栈非空）从堆栈弹出种子象素。
(1)如果种子象素尚未填充,则： ① 求出种子区段：xleft、xright。
② 填充整个区段。 (2)检查相邻的上扫描线的xleft≤x≤xright区间内,是否存在需要填充的新区段,如果存在,则把每个新区段在xleft≤x≤xright范围内的最右边的象素,作为新的种子象素依次压入堆栈。 (3)检查相邻的下扫描线的xleft≤x≤xright区间内,是否存在需要填充的新区段,如果存在,则把每个新区段在xleft≤x≤xright范围内的最右边的象素,作为新的种子象素依次压入堆栈。 }
有关堆栈操作的辅助代码
1、定义栈结构： # define MAX 100 /*定义最大栈空间*/
struct stack
{
int top; /*指向栈顶的计数器*/
int xy[MAX][2]; /*种子点（二维）*/
}s; 2、初始化堆栈 s.top=－1; 3、进栈操作 pushxy(int x,int y)
{
if(s.top= =MAX－1)
{
printf(“Overflow!”);
exit(1);
}
else
{
s.top=s.top+1;
s.xy[s.top][0]=x;
s.xy[s.top][1]=y;
}
} 4、出栈操作 popxy(int *x,int *y)
{
if(s.top<0)
{
printf(“underflow!”);
exit(1);
}
else
{
*x=s.xy[s.top][0];
*y=s.xy[s.top][1];
s.top=s.top－1;
}
} 5、堆栈非空 s.top!=－1 或者 s.top>=0 扫描线种子填充算法伪代码 scanline_seed_fill(int x,int y,int boundarycolor,int newcolor)
{
int savex,xleft,xright,pflag,xenter;
//初始化堆栈；
pushxy(x,y); /*种子压入堆栈*/
while(堆栈非空)
{
popxy(&x,&y); /*栈顶象素出栈*/
savex=x; /*保存种子坐标x分量的值*/
while(getpixel(x,y)!=boundarycolor) /*获取该点的颜色值*/
{
putpixel(x,y, newcolor ); /*填充种子右侧的象素*/
x++;
}
xright=x－1; /*得到种子区段的右端点*/
x=savex－1; /*准备向种子左侧填充*/
while(getpixel(x,y)!=boundarycolor) /*获取该点的颜色值*/
{
putpixel(x,y, newcolor ); /*填充种子左侧的象素*/
x--;
}
xleft=x+1; /*得到种子区段的左端点*/
x=xleft;
y=y+1; /*考虑种子相邻的上扫描线*/
while(x<=xright)
{
pflag=0; /*找到新种子的标志：0为假；1为真*/
while(getpixel(x,y)!=boundarycolor && getpixel(x,y)!=newcolor&& x<xright)
{
if(pflag= =0)
pflag=1;
x++;
}
if(pflag= =1)
{
if((x= =xright)&&(getpixel(x,y)!=boundarycolor)&&(getpixel(x,y)!=newcolor))
pushxy(x,y); /*新区间超过xright,将代表该区段的象素进栈*/
else
pushxy(x－1,y); /*新区段右端点作为种子进栈*/
pflag=0;
}
xenter=x;
while((getpixel(x,y)==boundarycolor||getpixel(x,y)==newcolor)&&x<xright)
{
x++;/*向右跳过分隔带*/
}
if(xenter==x) x++;/*处理特殊情况,以退出while(x<=xright)循环*/
}
x=xleft; /*为下扫描线的处理作准备*/
y=y－2;
/*检查相邻的下扫描线,找新区段,并将每个新区段右端的象素作为种子
入栈,其方法与上扫描线的处理一样,这里省略。要求同学补充完整。*/
}
} 边相关多边形扫描线填充思想
边相关扫描线填充算法的实现需要建立两个表：边表（ET）和活动边表（AET）。
ET用来对除水平边外的所有边进行登记,即建立边的记录。
AET则是在ET建立的基础上进行扫描转换。对不同的扫描线,与之相交的边线也是不同的,当对某一条扫描线进行扫描转换时,我们只需要考虑与它相交的那些边线,为此AET建立了只与当前扫描线相交的边记录链表,以提供对当前扫描线上的区段进行填充。
边相关多边形扫描线填充算法步骤
1、根据给出的顶点坐标建ET表；并求出顶点坐标中最大y值ymax和最小y值ymin。
2、定义AET指针,并使它为空。
3、使用扫描线的yj值作为循环变量,使其初值为ymin。
4、对于循环变量yj的每一整数值,重复作以下事情,直到yj大于ymax,或ET与AET表都为空为止：
① 如果ET中yj桶非空,则将yj桶中的全部记录合并到AET中。
② 对AET链中的记录按x的大小从小到大排序。
③ 依次取出AET各记录中的xi坐标值,两两配对,对每对xi之间的象素填上所要求的颜色。
④ 如果AET中某记录的ymax=yj,则删除该记录。
⑤ 对于仍留在AET中的每个记录,用xi+1/m代替xi,这就是该记录边线与下一条扫描线yj+1的交点。
⑥ 使yj加1,以便进入下一轮循环。
边相关多边形扫描线填充为伪代码 #include <stdlib.h>
#include <graphics.h>
#include <stdio.h>
#define round(x) ((x>0)?(int)(x+0.5):(int)(x-0.5)) /*求舍入的宏*/
struct edge{ /*边记录结构*/
int ymax;
float xi;
float m;
struct edge *next;
};
void poly_fill(int,int *,int);
void main()
{
int polypoints[]={ /*多边形顶点坐标: x0,y0,x1,y1,... */
100,300, 200,200, 300,200, 300,350,
400,250, 450,300, 300,50, 100,150};
int gdriver=DETECT,gmode;
initgraph(&gdriver,&gmode,);
poly_fill(8,polypoints,4); /*用红色填充*/
getch();
closegraph();
}
/*将一条边记录插入边记录构成的链表的表头*/
void insert_et(struct edge *anedge,struct edge **p_edges)
{
struct edge *p;
p=*p_edges;
*p_edges=anedge;
anedge->next=p;
}
/*复制一条边记录插入有效边表,维持有效边表的有序性*/
short insert_aet(struct edge *p,struct edge **p_aet)
{
struct edge *q,*k,*l;
if(!(q=(struct edge *)malloc(sizeof(struct edge))))
{
printf( OUT MEMORY IN INSERTING EDGE RECORD TO AET );
return(0);
}
q->ymax=p->ymax; q->xi=p->xi;
q->m=p->m; q->next=NULL;
if(!(*p_aet)||((*p_aet)->xi>q->xi)||(((*p_aet)->xi==q->xi)&&((*p_aet)->m>q->m)))
{
l=*p_aet; *p_aet=q; q->next=l;
}
else
{
l=*p_aet;
k=l->next;
while(k&&(k->xi<q->xi))
{
l=k;
k=k->next;
}
if(k&&(k->xi==q->xi)&&(k->m<q->m))
{
l=k;
k=k->next;
}
l->next=q;
q->next=k;
}
return(1);
}
/*从（x1,y）到（x2,y）用color色绘水平直线*/
void draw_line(int x1,int x2,int y,int color)
{
int i;
y=getmaxy()-y; /*进行坐标变换*/
for(i=x1;i<=x2;i++)putpixel(i,y,color);
}
/*多边形扫描线填充:
numpoint是多边形顶点个数；
points存放多边形顶点坐标（x0,y0,x1,y1,...);
color是填充色*/
void poly_fill(int numpoint,int *points,int color)
{
struct edge **et=NULL,*aet,*anedge,*p,*q;
int i,j,maxy,miny,x1,y1,x2,y2,yi,znum;
maxy=miny=points[1];
znum=2*numpoint;
for(i=3;i<znum;i++)
{
if(maxy<points[i]) maxy=points[i];
else if(miny>points[i])miny=points[i];
i++;
}
if(!(et=(struct edge **)malloc((maxy-miny+1)*sizeof(struct edge *))))
{ /*建立边表ET */
printf( OUT MEMORY IN CONSTRUCTING ET );
return;
}
for(i=0;i<maxy-miny+1;i++) et[i]=NULL;
x1=points[znum-2]; y1=points[znum-1];
for(i=0;i<znum;i+=2)
{ /*处理多边形所有边,为每条非水平边建立一个边记录,并将其插到ET表中的合适位置 */
x2=points[i]; y2=points[i+1];
if(y1!=y2) /*只考虑非水平边*/
{
if(!(anedge=(struct edge *)malloc(sizeof(struct edge))))
{
printf( OUT MEMORY IN CONSTRUCTING EDGE RECORD. );
goto quit;
}
anedge->m=(float)(x2-x1)/(y2-y1);
anedge->next=NULL;
if(y2>y1) /*处理奇异点*/
{
j=i+1;
do{ /*向后划过所有水平边*/
if((j+=2)>=znum)j-=znum;
}while(points[j]==y2);
if(points[j]>y2) anedge->ymax=y2-1;
/*若(x2,y2)不是局部极值点,边记录的ymax域为y2-1,这样处理
扫描线y=y2时此边记录将不在AET中,从而不会产生交点 */
else anedge->ymax=y2; /*若(x2,y2)是局部极值点,边记录的ymax域为y2,
这样处理扫描线y=y2时此边记录将在AET中,从而会产生一个交点 */
anedge->xi=x1;
insert_et(anedge,&et[y1-miny]);
}
else
{
j=i+1; /*向前划过所有水平边*/
do{
if((j-=2)<0)j+=znum;
}while(points[j]==y1);
if(points[j]>y1) anedge->ymax=y1-1;
/*若(x1,y1)不是局部极值点,边记录的ymax域为y1-1,这样处理
扫描线y=y1时此边记录将不在AET中,从而不会产生交点 */
else anedge->ymax=y1; /*若(x1,y1)是局部极值点,边记录的ymax
域为y1,这样处理扫描线y=y1时此边记
录将在AET中,从而会产生一个交点 */
anedge->xi=x2;
insert_et(anedge,&et[y2-miny]);
}
}
x1=x2;
y1=y2;
}
aet=NULL; /*初始化有效边表AET*/
for(yi=miny;yi<=maxy;yi++) /*从低到高逐条处理扫描线*/
{ /*将ET表中与yi对应的边记录链表中的全部边记录
p=et[yi-miny]; 都按序并入AET中*/
while(p)
{
if(!insert_aet(p,&aet)) goto quit;
p=p->next;
}
p=aet;
while(p) /*依次取出AET各记录中的xi坐标值,两两配对,*/
{/*对每对xi之间的象素填上所要求的颜色*/
draw_line(round(p->xi),round(p->next->xi),yi,color);
p=p->next->next;
}
p=aet;
while(p&&(p->ymax==yi)) /*对AET中的每个记录,若它的ymax==yi, */
{/*则删除该记录,否则用xi+1/m代替xi,这就是该记录所对应的*/
aet=p->next; /*边线与下一条扫描线y=yi+1的交点 */
free(p);
p=aet;
}
while(p)
{
if(p->ymax==yi)
{
q->next=p->next;
free(p);
p=q->next;
}
else
{
p->xi+=p->m;
q=p;
p=p->next;
}
}
}
quit:
if(et) /*释放动态申请的内存*/
{
for(yi=miny;yi<=maxy;yi++)
{
q=p=et[yi-miny];
while(p)
{
q=p->next;
free(p);
p=q;
}
}
free(et);
}
} 边标志填充算法思想
扫描线具有连贯性,这种连贯性只有在扫描线与多边形相交处才会发生变化,而每次的变化结果：无非是在前景色和背景色之间相互“切换”。
边标志填充算法正是基于这一发现,先在屏幕上生成多边形轮廓线,然后逐条扫描线处理。处理中：逐点读取象素值,若为边界色,则对该象素值进行颜色切换。
边标志填充算法步骤 1、用边界色画出多边形轮廓线,也就是将多边形边界所经过的象素打上边标志。
2、为了缩小范围,加快填充速度,须找出多边形的最小包围盒：xmin、ymin、xmax、ymax。
3、逐条扫描线进行处理,初始时标志为假,对每条扫描线依从左往右的顺序,逐个访问该扫描线上的象素。每遇到边界象素,标志取反。然后,按照标志是否为真决定象素是否为填充色。
边标志填充算法伪代码 EdgeMarkFill(int p[][2],int n,int boundarycolor,int newcolor)
{
int i,x,y,flag,xmin,xmax,ymin,ymax;
setcolor(boundarycolor); /*设置画笔色*/
for(i=0 ;i<n;i++)/*画出多边形的n条边*/
line(p[i][0], p[i][1], p[(i+1)%n][0], p[(i+1)%n][1]);
/*用求极值的算法,从多边形顶点数组p中,求出xmin,xmax,ymin,ymax*/
for(y=ymin;y<=ymax;y++)
{
flag=－1;
for(x=xmin;x<=xmax;x++)
{
if(getpixel(x,y)= = boundarycolor) flag=－flag;
if(flag= =1)putpixel(x,y, newcolor);
}
}
}