GIS教案第三讲数据结构

1、第三讲 地理数据结构及其文件组织学习目标 理解和掌握地理空间数据的拓扑关系 掌握栅格和矢量数据结构及其编码方法 了解栅格与矢量数据之间的转化方法重点：地理空间数据的拓扑关系、两种空间数据结构的特点及其编码方法。难 点：拓扑结构、栅格数据编码1第一节 地理信息的空间关系地理空间数据的拓扑关系地理空间信息的方向关系地理空间信息的度量关系2一、地理空间数据的拓扑关系拓扑结构 是明确定义空间结构关系的一种数学方法。 在GIS中，它不但用于空间数据的组织，而且在空间分析和应用中都有非常重要的意义。1.地理空间数据的拓扑关系2.地理空间数据拓扑关系应用价值3.地理空间数据拓扑关系的表示3拓扑邻接： 元素之

2、间的拓扑关系。拓扑关联： 元素之间的拓扑关系。拓扑包含： 元素之间的拓扑关系。1、地理空间数据的拓扑关系不 同 类同 类同类不同级4N11256473P1P3P2P4N4N3N5N2拓扑邻接：N1/N2 ,N1/N3 ,N1/N4 ;P1/P3 ;P2/P3拓扑关联：N1/1、3 、6 ；P1/1、5 、6 拓扑包含：P3与P452.地理空间数据拓扑关系应用价值（1）确定地理实体间的相对空间位置，无需坐标和距离（2）利于空间要素查询（3）重建地理实体63.地理空间数据 拓扑关系的表示结点集合结点名指 针第一个离开弧段 第一个到达弧段坐标N1 e3 e1 x1，y1 N2 e1 e5 x2，y2

3、 N3 e2 e4 x3，y31256473P1P3P2P4N4N3N5N2N17顺时针第一弧段 逆时针第一弧段指 针属性 P1 e1 t1 P2 e2 e5 t2多边形名 P3 e3 e4 t31256473P1P3P2P4N4N3N5N23.地理空间数据 拓扑关系的表示多边形集合N18弧段名e1 N2 N1 P1 P0 e6 e2 s1e2 N3 N2 e5 P2 P0 e4 e3 s2e3 N1 N3 e6 e4 P3 P0 s3 e4 N4 N3 e5 e3 P2 P3 e2 e6 s4 始结点 终结点离开始结点的下一条弧段到达终结点的下一条弧段右多边形左多边形右多边形顺时针下一条弧段

4、左多边形逆时针下一条弧段坐标串1256473P1P3P2P4N4N3N5N23.地理空间数据 拓扑关系的表示弧段集合N1P0910ArcGIS中拓扑功能的说明 在ArcGIS8.3以前，拓扑一直是ArcInfo coverage数据模型的一个特性。在ArcInfo coverage数据模型中，广大的GIS用户通过build和clean操作认识到拓扑的好处。从ArcGIS8.3开始为geodatabase增加了全面的拓扑。在ArcGIS9.0以上中常用的有关topology的操作主要有两个地方，一个是在ArcCatalog中，一个是在ArcMap中。通常我们将在ArcCatalog中建立拓扑称为

5、建立拓扑规则，而在ArcMap中建立拓扑成为拓扑处理。11ArcCatalog的Geodatabase中所提供的创建拓扑规则，主要是用于进行拓扑错误的检查，其中部分规则可以在所设容差内对数据进行一些修改调整。建立好拓扑规则后，就可以在ArcMap中打开由拓扑规则所产生的文件，根据错误提示对SHAPE图层进行修改。ArcMap中的topolopy工具条主要功能有对线拓扑，删除重复线、相交线断点（topolopy中的planarize lines），根据线拓扑生成面（topolopy中的construct features），拓扑编辑（如共享边编辑等），拓扑错误显示（用于显示在ArcCatalog

6、中创建的拓扑规则错误，topolopy中的error inspector），拓扑错误重新验证（也即刷新错误记录）。ArcGIS中拓扑功能的说明 12Geodatabase中如何创建拓扑规则 对ArcGIS的Geodatabase而言，能为包含在要素集中的一个或多个要素类定义拓扑。它可以为多点、线和多边形要素类定义拓扑。拓扑作为一系列用于空间关系的完整性规则，有一些重要的属性：一个群组容限（cluster tolerance，容差），要素类等级（rank，对坐标精度而言），错误（error，违规）和你所定义的规则（rules）的任何异常情况。 13Geodatabase中如何创建拓扑规则 在9.

7、0以上版中，ArcCatalog包含了一个拓扑向导来选择参与拓扑的要素类，并定义它们的属性。创建拓扑规则具体步骤如下：创建一个新的geodatabase（个人数据集）在其下创建一个feature dataset(要素集)，并为该要素集定制坐标系统创建feature class(要素类)或将其它数据作为要素类导入到该要素集下进入到该要素集下，在窗口右边空白处单击右键，在弹出的右键菜单中有new-topolopy按所给提示操作，设定合适容差，添加一些所需拓扑规则，若导入的要素类为多个图层，还需为图层划分等级，接着就可完成拓扑规则的检查最后在ArcMap中打开由拓扑规则产生的文件，利用topolop

8、y工具条中给出的错误记录信息进行修改14geodatabase的拓扑规则 具体规则包括： 线topology1.must not have dangle：线，不能有悬挂节点2.must not have pseudo-node：线，不能有伪节点3.must not overlay：线，不能有线重合（不同要素间）4.must not self overlay：线，一个要素不能自覆盖5.must not intersect：线，不能有线交叉（不同要素间）6.must not self intersect：线，不能有线自交叉7.must not intersect or touch interrio

9、r：线，不能有相交和重叠8.must be single part：线，一个线要素只能由一个path组成9.must not covered with：线线，两层线不能重叠10.must be covered by feature class of：线线，两层线完全重叠11.endpoint must be covered by：线点，线层中的终点必须和点层的部分（或全部）点重合12.must be covered by boundary of：线多边形，线被多边形边界重叠13.must be covered by endpoint of：点线，点被线终点完全重合14.point must b

10、e covered by line：点线，点都在线上15geodatabase的拓扑规则 (2) 多边形topology1.must not overlay：单要素类，多边形要素相互不能重叠2.must not have gaps：单要素类，连续连接的多边形区域中间不能有空白区（非数据区）3.contains point：多边形点，多边形要素类的每个要素的边界以内必须包含点层中至少一个点4.boundary must be covered by：多边形线，多边形层的边界与线层重叠（线层可以有非重叠的更多要素）5.must be covered by feature class of：多边形多边

11、形，第一个多边形层必须被第二个完全覆盖（省与全国的关系）6.must be covered by：多边形多边形，第一个多边形层必须把第二个完全覆盖（全国与省的关系）7.must not overlay with：多边形多边形，两个多边形层的多边形不能存在一对相互覆盖的要素8.must cover each other：多边形多边形，两个多边形的要素必须完全重叠9.area boundary must be covered by boundary of：多边形多边形，第一个多边形的各要素必须为第二个的一个或几个多边形完全覆盖10.must be properly inside polygons：

12、点多边形，点层的要素必须全部在多边形内11.must be covered by boundary of：点多边形，点必须在多边形的边界上16拓扑属性 (1)群组容限(cluster tolerance)群组容限与模糊容限（fuzzy tolerance）很相似。它是一个距离范围,在这个范围内结点被认为是重叠的。在验证拓扑的过程中，落入群组容限的结点和端点会被捕捉。(2)等级(rank)坐标精度等级在要素类上定义，在拓扑生效的时候，它将控制哪些要素类向另外哪些要素类进行捕捉。级别越高（1为最高），在验证过程中移动的要素越少。17利用拓扑查错Geodatabase里建立的拓扑用来捕捉要素的几何形

13、体，检查结点是否在群组容限内，以及是否有违规。拓扑首先是捕捉要素的结点，这些结点在考虑等级的要素类的群组容限范围以内。如果要素的结点在这个范围外，则视为违规，都会在验证过程中被发现并标记为错误。完整的错误列表可以在ArcCatalog和ArcMap的拓扑属性中看到。在ArcMap中拓扑中的错误和异常可以在图上显示出来，也可以在错误探测器中列出。然后用户可根据错误提示对图层要素进行修改。18Geodatabase中拓扑的优点 ArcInfo coverage模型明确地定义、存储和操作拓扑信息，并使用一组固定的工具来创建和维护拓扑。结果被软件所规定的工作流程紧紧地控制着，并且拓扑的完整性依然被维持

14、着。这个数据模型不够灵活。因此与很多GIS应用程序的需求相比，用于编辑的应用程序开发需要建立和维护更复杂的数据模型。19Geodatabase中拓扑的优点 在geodatabase中定义拓扑的好处有：更好的数据管理-你可以选择某些要素类参与拓扑。更高的灵活性-多部件的多边形、点和线要素能够参与拓扑。改善的数据完整性你可以为数据指定合适的拓扑规则。更多的数据建模机会大量可能的空间约束可以应用到你的数据上。更多的地图图层非常多的图层能存放在一个单一的数据库中。20二、地理空间信息的方向关系方向关系：地理事物在空间中的相互方位和排列顺序。描述空间实体的方向关系，对于点状空间实体只要计算两点之间的连线

15、与某一基准方向的夹角即可，该夹角称为连线的方位角。基准方向通常有真子午线方向、磁子午线方向和坐标纵线方向三种。同样计算点状和线状空间实体、点状和面状空间实体时，只需将线状和面状空间实体视为由它们的中心所形成的点状实体，然后按点状实体来求解方向关系即可。21三、地理空间信息的度量关系度量空间关系主要是指空间对象之间的距离关系。这种距离关系可以定量地描述为特定空间中的某种距离，如A实体距离B实体100m。也可以应用与距离概念相关的术语，如远近等进行定性的描述。22第二节 地理信息空间数据结构 空间数据结构矢量数据结构栅格数据结构栅格结构与矢量结构的比较23常用的空间数据结构XYijx1 y1x2

16、y2xi yixn yn矢量数据栅格数据24 矢量数据结构 矢量结构是通过记录坐标的方式来表示点、线、面等地理实体。 特点：定位明显，属性隐含。 获取方法： (1) 手工数字化法； (2) 手扶跟踪数字化法； (3) 数据结构转换法。25栅格数据结构 栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表示地理要素的非几何属性特征。 特点：属性明显，定位隐含。 获取方法： (1) 手工网格法； (2) 扫描数字化法； (3) 分类影像输入法； (4) 数据结构转换法。88888888888888888888888888888888888888888888811111111

17、1111112222222222232226栅格数据的取值方法 * 中心点法 * 面积占优法 * 长度占优法 * 重要性法 编码: A 1 B 2 C 3ABC2 ; 1; 1 ; 3 ; 1; ; 327A.OBC中心点法重要性法长度占优法面积占优法栅格结构数据中混合像元的处理方案一方案二：缩小栅格单元的面积28比较内容矢 量 结 构栅 格 结 构数据结构复杂简单数据量小大图形精度高低图形运算、搜索复杂、高效简单、低效软件与硬件技术不一致一致或接近遥感影像格式要求比较高不高图形输出显示质量好、精度高， 但 成本比较高输出方法快速，质量低，成本比较低廉数据共享不易实现容易实现拓扑和网络分析容易

18、实现不易实现矢量结构与栅格结构的比较29第三节 地理数据的编码方法编码的概念和意义栅格结构编码方法矢量结构编码方法属性数据编码方法30云南盈江地震北京3月10日电据中国地震台网中心网站消息，云南省德宏傣族景颇族自治州盈江县，北京时间10日12时58分，发生里氏5.8级地震，震中位于北纬24.7、东经97.9，震源深度10公里。随后，在同一位置，13时03分及04分，又相继发生里氏4.7级地震和里氏4.5级地震。31第三节 地理数据的编码方法 地理数据编码，是根据GIS的目的和任务，把地图、图像等资料按一定数据结构转换为适于计算机存贮和处理的数据过程。地理内容的编码要反映出地理实体的几何特征，以

19、及地理实体的属性特征，空间数据的编码是地理信息系统设计中最重要的技术步骤，它表现由现实世界到数据世界之间的界面，是联结从现实世界到数据世界的纽带。一、编码的概念和意义32链码(chain Encoding)直接栅格编码游程长编码(Run_length Encoding)块 码四叉树编码(quarter_tree Encoding)栅格结构编码方法331、直接栅格编码 直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行从左到右逐像元记录，也可奇数行从左到右而偶数行由右向左记录，为了特定的目的还可采用其他特殊的顺序。 0 2 2 5 5 5 5 52 2 2 2 2 5

20、5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 30，2，2，5，5，5，5，5；2，2，2，2，2，5，5，5；2，2，2，2，3，3，5，5；0，0，2，3，3，3，5，5；0，0，3，3，3，3，5，3；0，0，0，3，3，3，3，3；0，0，0，0，3，3，3，3；0，0，0，0，0，3，3，3。34由起点位置和一系列在基本方向的单位矢量给出每个后续点相对其前继点的可能的8个基本方向之一表示。8个基本方向自0开始按逆时针方向代码分别为0，1，2，3，4

21、，5，6，7。单位矢量的长度默认为一个栅格单元。2、链码1234507600107670110035链码编码： 2，2 ，6 ，7，6，0，6，5123450760 5 0 0 0 0 0 00 0 5 0 0 0 0 00 0 0 0 0 0 0 00 5 0 0 0 0 0 00 0 5 5 0 0 0 00 0 0 5 0 0 0 00 0 5 0 0 0 0 00 0 0 0 0 0 0 0链码编码示例363、游程长度编码(1)只在各行（或列）数据的代码发生变化时依次记录 该代码以及相同代码重复的个数；0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3

22、3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3沿行方向进行编码：( 0，1），（2，2），（5，5）；（2，5），（5，3）；（2，4），（3，2），（5，2）；（0，2），（2，1），（3，3），（5，2）；（0，2），（3，4），（5，1），（3，1）；（0，3），（3，5）；（0，4），（3，4）；（0，5），（3，3）。373、游程长度编码逐个记录各行（或列）代码发生变化的位置和相应代码。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 3

23、2 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3沿列方向进行编码：( 1，0），（2，2），（4，0）；（1，2），（4，0）；（1，2），（5，3），（6，0）；（1，5），（2，2），（4，3），（7，0）；（1，5），（2，2），（3，3），（8，0）；（1，5），（3，3）；（1，5），（6，3）；（1，5），（5，3）。38 4、块码 采用方形区域作为记录单元，数据编码由初始位置行列号加上半径，再加上记录单元的代码组成。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50

24、0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3（1，1，1，0），（1，2，2，2），（1，4，1，5），（1，5，1，5），（1，6，2，5），（1，8，1，5）；（2，1，1，2），（2，4，1，2），（2，5，1，2），（2，8，1，5）；（3，3，1，2），（3，4，1，2），（3，5，2，3），（3，7，2，5）；（4，1，2，0），（4，3，1，2），（4，4，1，3）；（5，3，1，3），（5，4，2，3），（5，6，1，3），（5，7，1，5），（5

25、，8，1，3）；（6，1，3，0），（6，6，3，3）；（7，4，1，0），（7，5，1，3）；（8，4，1，0），（8，5，1，0）。39 5、四叉树编码 是根据栅格数据二维空间分布的特点，将空间区域按照4个象限进行递归分割（2n2 n，且n1），直到子象限的数值单调为止，最后得到一棵四分叉的倒向树。四叉树分解，各子象限大小不完全一样，但都是同代码栅格单元组成的子块，其中最上面的一个结点叫做根结点，它对应于整个图形。不能再分的结点称为叶子结点，可能落在不同的层上，该结点代表子象限单一的代码，所有叶子结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶子结点编号，最下面的一排数字表示各子

26、区的代码。 为了保证四叉树分解能不断的进行下去，要求图形必须为2n2 n的栅格阵列。n 为极限分割次数，n1是四叉树最大层数或最大高度400 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3 1112131415161718192021222324252627282930313233363738393435400 0 00 3 3 3 0 3 3 33 3 5 3 0 0 2 22 3 2 2 2 2 0 2

27、2 2 2 5 2 5 5 53 33 5 5西南东南西北东北 0 0 0 0 0 0 0 1 1 0 1 0 0 1 122位6位4位41体元形式的三维数据线性八叉树编码 编码 42直接栅格编码：简单直观，是压缩编码方法的逻辑原型（栅格文件）；链码：压缩效率较高，以接近矢量结构，对边界的运算比较方便，但不具有区域性质，区域运算较难；游程长度编码：在很大程度上压缩数据，又最大限度的保留了原始栅格结构，编码解码十分容易，十分适合于微机地理信息系统采用；块码和四叉树编码：具有区域性质，又具有可变的分辨率，有较高的压缩效率，四叉树编码可以直接进行大量图形图象运算，效率较高，是很有前途的编码方法。43

28、矢量结构编码方法1、点实体矢量编码方法2、线实体矢量编码方法3、多边形矢量编码方法44点实体编码比例朝向线指针线交汇编比例朝向字体文句x,y 坐标其它非几何属性建立和显示数据库联系的属性简单点符号文本点字符结 点符号统一标识类别或系列号点类型简单点文本点结 点45线实体编码唯一标示码线标示码起始点终止点坐标对序列显示信息非几何属性46多边形矢量编码多边形环路法树状索引编码法拓扑结构编码法由多边形边界的x,y坐标队集合及说明信息组成对所有边界点数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系形成完整的拓扑结构47多边形环路法1234567891011121314

29、15P1P2P3P1 x1，y1；x2，y2； x3，y3；x4，y4； x5，y5；x6，y6；P2 x7，y7；x8，y8； x9，y9；x10，y10； x11，y11；x5，y5；x6，y6P3 x12，y12；x13，y13；x14，y14；x15，y1548树状索引法123456789101112131415P1P2P3 P1P3P2 1 2 3 4 5 65 65 6 7 8 9 1012 13 14 15 49123456789101112131415P1P2P3点文件 点号 坐标 1 x1，y1 2 x2，y2 15 x15，y15树状索引法50123456789101112

30、131415P1P2P31 2 3 4 5 65 65 6 7 8 9 1012 13 14 15 线号 起点 终点 点号 6 5 6,1,2,3,4,5 5 6 5,6 6 5 6,7,8,9,10,11,5 12 13 12,15,14,13树状索引法51123456789101112131415P1P2P3多边形文件多边形号 边界线号 1 ， 2 ， 3 P1P3P2 树状索引法52 根据图层的图形特征数字化画点画线画面文字面、线节点编辑工具点、线、面、文字符号化工具53 根据图层的属性定义录入属性值图形选择工具图形窗缩放、平移工具属性查询、属性值录入工具图层控制工具量距热连接54拓扑结

31、构编码法唯一标示多边形标示外包多边形指针邻接多边形指针边界链接范围较好的解决了空间关系查询等问题，但增加了算法的复杂度55 四、属性数据编码方法1.编码内容 （1）登录部分 （2）分类部分 （3）控制部分2.编码原则 （1）管理效率高 （2）适用性好 （3）接口方便56第四节 矢量结构与栅格结构的相互转换矢量数据结构向栅格数据结构的转换栅格数据结构向矢量数据结构的转换57栅格数据格式 矢量数据格式 （一）两种数据格式变换的基础1、矢量数据格式 ：空间位置是用它们在某一参照坐标系中的坐标来表达。 点：单个的坐标 线：一组坐标值 面：封闭的边界线2、栅格数据格式：表达空间位置数据的基本单位是栅格单

32、元（像素）583、将一个网格系统覆盖在笛卡儿坐标系统上，可生成一个网格坐标系统。向量地图上线和面的边界可以用网格线近似表达。精度取决于网格密度。4、栅格坐标系统左上角为坐标原点，矢量坐标系统左下角为坐标原点。两坐标系之间存在着相互转换的关系。59518437529508268439643964360（二）由栅格数据转换成矢量数据 设给定网格数据是一个NN矩阵间隔：矩阵中同一行内相互邻接 ，且具有 相同专题属性值的元素构成一个间 隔段。区域：分布在不同行，但相互邻接的间隔组 成一个区域。61一、矢量数据结构向栅格数据结构的转换矢量数据转换成栅格数据后，图形的几何精度必然要降低，所以选择栅格尺寸的

33、大小要尽量满足精度要求，使之不过多地损失地理信息。为了提高精度，栅格需要细化，但栅格细化，数据量将以平方指数递增，因此，精度和数据量是确定栅格大小的最重要的影响因素。栅格尺寸确定 计算若干个小图斑的面积S（i1，2，n）； 求小图斑面积平均值； 求栅格尺寸L（）1/2。62一、矢量数据结构向栅格数据结构的转换点的栅格化63一、矢量数据结构向栅格数据结构的转换直线栅格化 直线插补法 扫描线法64一、矢量数据结构向栅格数据结构的转换面域的栅格化 直线插补法 扫描线法65二、栅格数据结构向矢量数据结构的转换多边形边界提取边界线追踪拓扑关系生成去除多余点及曲线圆滑66二、栅格数据结构向矢量数据结构的转

34、换多边形边界提取 二值化 细化 67二、栅格数据结构向矢量数据结构的转换多边形边界提取 二值化 细化 68二、栅格数据结构向矢量数据结构的转换边界线追踪：边界线跟踪的目的就是将写入数据文件的细化处理后的栅格数据，整理为从结点出发的线段或闭合的线条，并以矢量形式存储于特征栅格点中心的坐标拓扑关系生成：对于矢量表示的边界弧段，判断其与原图上各多边形空间关系，形成完整的拓扑结构，并建立与属性数据的联系。去除多余点及曲线圆滑：由于搜索是逐个栅格进行的，必须去除由此造成的多余点记录，以减少冗余。69（1）对网格型数据所描述的区域赋给一个标志值 A.对第一行的每一个间隔段按先后顺序给定一个标志值 B.从第

35、二行开始到最后一行，如果某一间隔的第一个元素的专题属性值等于上一行相邻的间隔段的专题属性值，则该间隔的标志值采用上一行与其相邻间隔的标志值，否则赋给一个新的标志值。如果在一间隔内第一个元素以外的其它元素与上一行相邻接的元素有着相同的专题属性值，而这两个元素所在的间隔段的标志值又不相同，则这两个间隔段要建立一个关系 。具体分析算法：70C.在所有的间隔都赋给了一个间隔值后，则获得一个包含相邻间隔之间的关系表和关系子图。每个子图把属于同一区域的间隔段连结在一起。每个区域取值为间隔段的最小标志值。这样同一区域的所有间隔段都被赋给了一个相同的唯一标志值。为去掉断号现象，按从小到大的次序重新对区域标志编

36、号。 4 66 97 108 1011 1212 1313 1514 1616 1919 2018 2224 2528 304 6 97 8 1011 12 13 1514 16 19 2018 2224 2528 301113242533477333333254444711117141111111111141717171718181114142114181814142323212114242424262626262627271414142829282827272729291471D.专题属性值转变成标志值后，形成二者的关系表，进行空间处理分析时应用。提取每个区域间隔段时，每个间隔段用R-L 码进行编码（行列编码），编码值与区域标志值储存在一起 。72（2）区域和邻域关系表每个区域的邻域用开“窗口”方法获得（22）。如果两个或三个元素的区域标志值在“窗口”中不同，则表明这些标志值所代表的区域具有邻域关系。 XXX114781073（3）提取边界线，并用链码编码 为提取边界线及结点，开设22的窗口进行游动搜索。窗口内结点及边界结果如图 a c b c a b c a a b a c a b c c a a b c a b b a a c b