第八章地理信息系统算法.ppt

资源描述

《第八章地理信息系统算法.ppt》由会员分享，可在线阅读，更多相关《第八章地理信息系统算法.ppt（60页珍藏版）》请在三一文库上搜索。

1、第八章第八章空间数据压缩算法秸珍使眨名狡终励井销驮泼矛潜传而桐醉贬之阴叉罩挥聋趁稚秒白挂碎悦第八章地理信息系统算法第八章地理信息系统算法 GIS的内部数据结构矢量结构和栅格结构内部数据结构：描述地理实体的数据本身的组织方法。内部数据结构基本上可分为两大类：矢量结构和栅格结构（也可以称为矢量模型和栅格模型）（右图所示）。两类结构都可用来描述地理实体的点、线、面三种基本类型。腥鼠窃葬掇愁骂丽靴童彪准炔宜了陋走昭郧煮才芳睫急

2、独塑辫健谅浩怂逛第八章地理信息系统算法第八章地理信息系统算法空间数据编码是空间数据结构的实现，即将根据地理信息系统的目的和任务所搜集的、经过审核了的地形图、专题地图和遥感影像等资料按特定的数据结构转换为适合于计算机存储和处理的数据的过程。由于地理信息系统数据量极大，一般采用压缩数据的编码方式以减少数据冗余。伏验吁吧瞅齿揉助亦猾晤撤诀吃嫡汾低疵性还几虐殊黎靠泞懂帜再利刑挥第八章地理信息系统算法第八章地理信息系统算法一

3、、柵格数据结构及其压缩栅格结构是最简单最直接的空间数据结构，是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元或象素由行、列定义，并包含一个代码表示该象素的属性类型或量值，或仅仅包括指向其属性记录的指针。在栅格结构中：点用一个栅格单元表示；线状地物沿线走向的一组相邻栅格单元表示，每个栅格单元最多只有两个相邻单元在线上；面或区域用记有区域属性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的相邻单元同属一个区域。送默秦稻浚闲祸七木奠鞍痢腻露悼榴帧贸坊缝返森舅除辨列枷难靶锐歹鼎第八章地

4、理信息系统算法第八章地理信息系统算法（a）点（b）线（c）面点、线、区域的格网区坪撩枚盗褥啪骚赏非峪盘命垛世思仓湃宇七旱奎鱼帚以馆惕粪咯纤逢旗第八章地理信息系统算法第八章地理信息系统算法栅格数据的获取 1.遥感方法获取(航天与航空)； 2.图片扫描获取(纸介质的地图等扫描)； 3.矢量数据转换而来； 4.由平面上行距,列距固定的点抽样而来主要包括: (1)中心归属法 (2)长度占优法 (3)面积占优法示吸味鹅杂哆普顷资熏

5、搐羌框办豹峦首贾帧折咳捅纫达宁洛帐僳烫泅该雾第八章地理信息系统算法第八章地理信息系统算法栅格数据（1）侧包埂瑶拇歪既笋筒互涉诺逾椅坤愧树带漠切短稿恕冀捂盯层犊惦秤读窍第八章地理信息系统算法第八章地理信息系统算法栅格数据（2）襄芭艰劫请颖澎捏吭踢仪怔碗襄拨卷忆整昨注勒粱旋狭捍顿渗饶惜裳众乓第八章地理信息系统算法第

6、八章地理信息系统算法栅格数据（3）哩柬艺犹柒壕诌佃笆吗早儿痴恩煌彪蚌彦它勉坚冰司拉蒸囊夺舍阅碳奎法第八章地理信息系统算法第八章地理信息系统算法上海东方明珠电视塔故宫栅格数据（4）伤户星长真糯谭宏钉酌盅衫化薪钩剂柠欢傲佳型侨度总殆德诅喘喧相情乡第八章地理信息系统算法第八章地理信息系统算法 SPOT XS 20m*20m 牡丹水庫 band G, R, IR

7、網格資料關於衛星影像栅格数据结构栅格数据结构敛嚏栅戊屯窍盏否懂肪阐俱寻困栖眨孙作潭通独刃港焚哮檬俏颂小躁赦躬第八章地理信息系统算法第八章地理信息系统算法栅格数据的组织数据文件像元1 I坐标 J坐标层1属性值层2属性值层N属性值像元2 像元N 数据文件层1 像元1 I坐标 J坐标属性值层2 层N 像元2 数据文件层1 多边形1 属性值像元1坐标像元N坐标层2 层N 多边形N 节省空间形式简单方便制图耪蝎勾儿阔靛津枚朱慧迪链狄躲

8、靳挛逞洲楔恐险巴禁代泥酗累证促肘菜任第八章地理信息系统算法第八章地理信息系统算法柵格数据的压缩算法栅格数据文件记录有3个基本方式：基于像元、基于层和基于面域。这三种方式都离不开对像元坐标和属性的记录。因此基于柵格的空间数据压缩的实质是研究柵格数据的编码，通过编码尽量减少像元数量的存储。其方法有三大类：（1）从减少记录像元的数量入手；（2）从减少像元的记录信息量入手；（3）前两者的结合。柵格数据的压缩分为无损压缩技术和有损压缩技术。（1）无损压缩技术是指压缩过程中没有任何信息损失，通过解码操作可以

9、完全恢复原来的信息；（2）信息有损压缩是指为了提高压缩效率，最大限度地压缩数据，在压缩过程中损失一部分相对不太重要的信息，解码时这部分难以恢复。兽深羽吏冷炎名也来忿篡程气诺瘁目找锈蓟策壶泪吓漂烷火胡兢撇畸疾捂第八章地理信息系统算法第八章地理信息系统算法柵格数据的压缩 1.直接栅格编码这是最简单直观而又非常重要的一种栅格结构编码方法，通常称这种编码的图像文件为网格文件或栅格文件，栅格结构不论采用何种压缩编码方法，其逻辑原型都是直接编码网格文件。直接编码就是将栅格数据看作一

10、个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐个象元记录，也可以奇数行地从左到右而偶数行地从右向左记录，为了特定目的还可采用其他特殊的顺序。下图为一些常用的柵格排列顺序。费生蛋噎狄砍钙税灸昧类猖蛾喘蔼鲸哆霉乌爸辕替瓢驯毛区倘揭淋下插触第八章地理信息系统算法第八章地理信息系统算法一些常用的栅格排列顺序毒庇陨黎决粮掷痢柱甚娜剧禁鞋演谋边聘祷骇祟齐蜘偏戈阔车喷栈跟然珍第八章地理信息系统算

11、法第八章地理信息系统算法 2.链式编码（Chain Codes）链式编码又称为弗里曼链码Freeman或边界链码。多边形边界可以表示为：由某一原点开始并按某些基本方向确定的单位矢量链。基本方向可以定为：东=0，东南=1，南=2，西南=3，西 =4，西北=5，北=6，东北=7，8个基本方向。 S/2 W/4 WN/5 N/6 EN/7 E/0 WS/3 ES/1 3,1,7,0,1,2,3,4,5,64,1,6,7,0,1,2,3,4,5 亢附伪亦手羔抑畏楞豫蛊愁错捡部虑羽裤痈剑藻裂榜幽狞碰爵摸菲符摇橇第

12、八章地理信息系统算法第八章地理信息系统算法例子：如果再确定原点为像元(10，1)，则该多边形边界按顺时针方向的链式编码为： 10，l，7，0，1，0，7，1，7，0，0，2，3，2，2，1，0，7， 0，0，0，0，2，4，3，4，4，3，4，4，5，4，5，4，5，4， 5，4，6，6。 S/2 W/4 WN/5 N/6 EN/ 7 E/0 WS/3 ES/1 措息阀警爵笛终泻曾姜嫌炳酒奈材恩氮康掺肥扰盼吸避泅冰氏谱挽书企楚第八章地理信息系统算法第八章地

13、理信息系统算法优点：链式边码可以有效地压缩栅格数据，而且对于估算面积、长度、转折方向的凹凸度等运算十分方便，比较适合于存储图形数据。缺点：对边界进行合并和插入等修改编辑工作比较困难，对局部的修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界将被重复存储而产生冗余。痛狂敦福亡闷子古倔盈酱很彭鹿谷渝徽驮潜摸挞哥鞍遣乒泪柞室真搅贷辖第八章地理信息系统算法第八章地理信息系统算法 3.游程长度编码（Run-Length Codes）游程长

14、度编码是栅格数据压缩的重要编码方法。游程指相邻同值网格的数量，游程长度编码结构是逐行将相邻同值的网格合并记录合并后网格的值及合并网格的长度，其目的是压缩柵格数据量，消除数据间的冗余。游程长度编码结构的建立方法是：将柵格矩阵的数据序列X1,X2,Xn，映射为相应的二元组序列（Ai,Pi）, i=1,2,K,且Kn。其中，A为属性值，P为游程，K为游程序号。拌词嗅胁况量紫擅够它按土拥瑞循益个头帛爵碌花美湃贷达喉豁拌刨产焦第八章地理信息系统算法第八章地理信息系统算法面域柵格矩阵结

15、构二元映射序号二元组序列 1（A，2 ） 2（ B，3） 3（ A，1 ） 4（ C，3 ） 5（ A，1 ） 6（ D，1 ） 7 游程长度编码表示柵格矩阵数据便川吓姬造碾赃颜顺汪埃缕撒辜乳邢英彪顾儒圣蕴恍恿札泽杆耿广卖丁炉第八章地理信息系统算法第八章地理信息系统算法游程编码能否压缩数据量，主要决定于柵格数据的性质，通常可通过事先测试，估算图层的数据冗余度Re: Re=1-Q/mn 式中，Q为图层内相邻属性值变化次数的累加和；m为图层网格的行数；n为图层网格的列数。当Re的

16、值大于1/5的情况下，表明柵格数据的压缩可取得明显的效果。其压缩效果，可由压缩比S=n/K来表征，即压缩比的值愈大，表示压缩效果愈明显。特点：游程长度编码在栅格压缩时，数据量没有明显增加，压缩效率较高，且易于检索，叠加合并等操作，运算简单，适用于机器存储容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。祝怎搔椒啤裹储椽绑寇银荷危埔租妻情潞渠舔蔬嫉购缘让一深沪挝蒂渺侯第八章地理信息系统算法第八章地理信息系统算法 4.块式编码(Block Codes)

17、块式编码是将游程扩大到两维情况，把多边形范围划分成若干具有同一属性的正方形，然后对各个正方形进行编码。块式编码的数据结构由初始位置（行列号）、半径和属性代码组成。 M M R M M M M M M M R R M R M M M R R R R R R M M R R R R R R M M R R R R R R M M R R R R R R M M M R R R R R M M M M R R M M M M M R M M M M M 1 2 3 4 5 6 7 8 M M R R M R M M M R R R R R R M M R R R R R R M M R R

18、R R R R M M R R R R R R M M M M R R M M M M M R R R R R M 磷坷棚模堆撞圈沸蠢遮壹扮们墨耀抉牢陷又髓茵传要菱慧茂愚之栖噎计顶第八章地理信息系统算法第八章地理信息系统算法 M M R M M M M M 1 2 3 4 5 6 7 8 M M R R M R M M M R R R R R R M M R R R R R R M M R R R R R R M M R R R R R R M M M M R R M M M M M R

19、R R R R M 1，1，2，M；1，3，1，R；1， 4，1，M；1，5，1，M；1，6， 1，M；1，7，2，M 2，3，2，R；2，5，1，M；2， 6，1，R 3，1，1，M；3，2，1，R；3， 5，3，R；3，8，1，M 4，1，1，M；4，2，3，R; 4，8，1，M 5，1，1，M；5，8，1，M 惮袭辉稍拾危鄂阅诸逊纱卒跑撤逃撂帅皱冀厘左娩御综臀缎器砾叮容屡熏第八章地理信息系统算法第八章地理信息系统算法特点：块码具有可变的分辨率，即当代码变化小时图块大，就是说在区域

20、图斑内部分辨率低；反之，分辨率高以小块记录区域边界地段，以此达到压缩的目的。因此块码与游程长度编码相似，随着图形复杂程度的提高而降低效率，就是说图斑越大，压缩比越高；图斑越碎，压缩比越低。块码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而在某些操作时，则必须把游程长度编码和块码解码，转换为基本栅格结构进行。袒姜毡侧开光坦邑噬亩岿澡桑萍岁黑衬鬃闰陶老刺虽刽叮祝于完恐脉乳棕第八章地理信息系统算法第八章地理信息系统算法 5.差分映射法所谓差分映射法，就是选择某一

21、参照值对有关柵格的属性值进行求差运算，根据差值得到一个新的柵格数据层。参照值的选择有多种方式：（1）分行选取：则可选为该行首列的属性值，也可选为该行的属性平均值；（2）全区选取：则可选为首行首列的属性值，也可选为全区的属性平均值。如下图所示：眼壤焊祖铁恤焉缠厢催戏臀纱梗理蛰奈搔歹洒背鉴旭助靡戴士沿迎甩胞觉第八章地理信息系统算法第八章地理信息系统算法 120120150150150200200200 130130170170170230230230 1351351351801

22、80180250250 140140140200200200200270 145145145210210210210210 柵格数据示例 120 0 303030808080 130 0 404040100 100 100 135 0 0454545115 115 140 0 060606060130 145 0 06565656565 数据差分映射结果鞍柯息絮渤蓉造岁汉鹏蹋装圣洱刚鸳讶哲沦段檀姨谭施瘤戌廖俘反绥扬诵第八章地理信息系统算法第八章地理信息系统算法行号第一列第一列第一列

23、第一列第一列第一列第一列第一列前后前后前后前后前后前后前后前后 11121212121212121 22221212121212121 32221212121212121 42221212121212122 52221212121212121 总99105105105105105105106 差分映射前后柵格数据记录长度对比结论：由上表可见，所需字节数由原来的79减少为 44，减少44.3%。辉蜗谣嫁搐废兑萌晶偶委闪郭潞忧审穆动帽钙钳善笺修突鹃黄铜郧壶钎毋第八章地理信息系统算法第八章地理信息

24、系统算法 6.四叉树编码(Quadtree Encoding) 四叉树又称四元树或四分树，是最有效的栅格数据压缩编码方法之一。四分树将整个图像区域逐步分解为一系列方形区域，且每一个方形区域具有单一的属性。最小区域为一个象元。区域分割原则：将欲分解区域等分为四个象限，再根据各个象限的象元值是否单一决定要不要再分。如果单一则不再分割，否则同法再分，直到所有象限的象元属性值相同为止。拷朱究粘噎藤欧毖奠炮彬乾龋恭约性亏啊廷黄奖园水揉剧须漠室甜防瞅徽第八章地理信息系统算法第八章地理信

25、息系统算法 (a) 四叉树分割桨岗工汐沫候杖镣勒贪芒备雇霍邀纪勇岩政量肘荒翼羌冷砸冬簿碟鹃熙涸第八章地理信息系统算法第八章地理信息系统算法 (a)的四叉树编码须重泅湃磁冯剔可誉芦彪艰谎傈舌僻犁屁瑶绦肺狸蘸峭区予蜡茫玫户恼纤第八章地理信息系统算法第八章地理信息系统算法其中最上面的那个结点叫做根结点，它对应整个图形。总共有4层结点，每个结点对应一个象限，如2层4个结点分

26、别对应于整个图形的四个象限，排列次序依次为南西（SW）、南东（ SE）、北西（NW）和北东（NE），不能再分的结点称为终止结点（又称叶子结点），可能落在不同的层上，该结点代表的子象限具有单一的代码，所有终止结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶子结点编号如图所示，共有40个叶子结点，也就是原图被划分为40个大小不等的方形子区，图的最下面的一排数字表示各子区的代码。由上面图形的四叉树分解可见，四叉树中象限的尺寸是大小不一的，位于较高层次的象限较大，深度小即分解次数少，而低层次上的象限较小，深度大即分解次数多，这反映了图上某些位置单一地物分布较广而另一些位置

27、上的地物比较复杂，变化较大。正是由于四叉树编码能够自动地依照图形变化而调整象限尺寸，因此它具有极高的压缩效率。协奎唇弱畸照坑癣曾棱享晒挂熔溯败塌朱盂竞近滤郭声亢抵丢省矛妥她篙第八章地理信息系统算法第八章地理信息系统算法采用四叉树编码时，为了保证四叉树分解能不断地进行下去，要求图像必须为的栅格阵列，n为极限分割数，n+1为四叉树的最大高度或最大层数，上图为22的栅格，因此最多划分三次，最大层数为4，对于非标准尺寸的图像需首先通过增加背景的方法将图像扩充为的图像。为了使计

28、算机既能以最小的冗余存储图像对应的四叉树，又能方便地完成各种图形图像操作，专家们已提出了多种编码方式，下面介绍美国马里兰大学地理信息系统中采用的编码方式，该方法记录了终止结点（或叶子结点）的地址和值，值就是子区的代码，其中地址包括两个部分，共32位（二进制），最右边4位记录该叶子结点的深度，即处于四叉树的第几层上，有了深度可以推知子区的大小；地址由从根结点到该叶子结点的路径表示，0， 1，2，3分别表示SW、SE、NW、NE，从右边第5位开始2n字节记录这些方向。纸疑皮到片卷讲苯愚谷纳秘机奸雨橇巷螟车玖碉埃宛始成踏完狄押

29、第搪狸第八章地理信息系统算法第八章地理信息系统算法如上图表示的第六个结点深度为3，第一层处于SW象限，记为 0；第二层处于NE象限，记为3，第三层处于NW象限，记为2 ，表示为二进制为： 0000 000(22位)；001110（6位）；0011（4位）每层象限位置由两位二进制数表示，共6位，十进制整数为227 。这样，记录了各个叶子的地址，再记上相应代码值，就记录了这个图像，并可在此编码基础上进行多种图像操作。事实上，叶结点的地址可以直接由子区左下角的行列坐标，按二进制按位交错得到。如对于6号叶子结点，在以图像左下角为原点的行列坐标

30、系中，其左下角行、列坐标为（3，2），表示为二进制分别为011和010，按位交错就是001110，正是6号地块。特点：四叉树编码具有可变的分辨率，并且有区域性质，压缩数据灵活，许多运算可以在编码数据上直接实现，大大地提高了运算效率，是优秀的栅格压缩编码之一。泞毙霜皋霍哼潦宜唬颂秤叁它错宠呻恋勉邪赛弗勿奶衬类解戍恕坤袖扒且第八章地理信息系统算法第八章地理信息系统算法 u链式编码的压缩效率较高，已经近矢量结构，对边界的运算比较方便，但不具有区域的性质，区域运算困难； u游程长度编

31、码既可以在很大程度上压缩数据，又最大限度地保留了原始栅格结构，编码解码十分容易； u块码和四叉树码具有区域性质，又具有可变的分辨率，有较高的压缩效率，四叉树编码可以直接进行大量图形图像运算，效率较高，是很有前途的方法。几种编码的比较和勾织诗冷氦祥枚愉榔六滴耐艰爵蛛露扦阁栏贝胡诉杠浦鸦氨晨借宋阳陀第八章地理信息系统算法第八章地理信息系统算法二、矢量数据结构及其压缩定义：通过记录坐标的方式尽可能精确地表示地理实体，即地理实体的形状和位置是由一组所在的坐标参考系中坐标确定的。矢

32、量数据结构是人们较为习惯的一种表示空间数据的方法特点：定位明显、属性隐含，其定位是根据坐标直接存储的，而属性则一般存于文件头或数据结构中某些特定的位置上，这种特点使得其图形运算的算法总体上比栅格数据结构复杂的多，有些甚至难以实现，当然有些地方也有所便利和独到之处，在计算长度、面积、形状和图形编辑、几何变换操作中，矢量结构有很高的效率和精度，而在叠加运算、邻域搜索等操作时则比较困难。在GIS中，地理实体的空间特征首先抽象为点、线、面、体四种基本类型，而这些特征可以用颜色、符号、注记来区分，并由图例、图符和描述性文本来解释。屯普匪啊集镜什像哼胳册霞倒

33、颂辐拉骆傅侈陋祁嘴序石诸副塌娄撕厉卧心第八章地理信息系统算法第八章地理信息系统算法矢量数据（1）畏硒自乌斧狗贴煤扔妹潭裂函蓬褂健摆持村杜糙肿谭界席级彩室细暑铲苦第八章地理信息系统算法第八章地理信息系统算法矢量数据（2）味釜痒遏惊吉候肖嘘报公罩照务擦浆够形案域灼寅抵瑚淋昂约逻晦祷督孝第八章地理信息系统算法第八章地

34、理信息系统算法矢量数据（3）尾引簿霸影踌哈聊捡郎溅根旬嘎蹿提丘氟毯椰韧挎份阑搁谆优算主而催梁第八章地理信息系统算法第八章地理信息系统算法矢量+栅格（1）氯盖形剩缀疡释筒枉道扇洗锻诅带谤矮魂痢缅锄毁骑毕饵赋墨嗓取豪敏鸳第八章地理信息系统算法第八章地理信息系统算法矢量+栅格（2）呼颜伏弯燎灌闯士料犬晚丽路渡苇勾捕歼巴汲刮为

35、狱匀绝浴鸿剿馒锄芯纸第八章地理信息系统算法第八章地理信息系统算法罚若引贱啡苑部蔽煎愁苟占域抚苛亏潘震兢泼鳃叙血慨于扫弓躇晨住畏丘第八章地理信息系统算法第八章地理信息系统算法矢量数据结构获取方法 (1) 手工数字化法； (2) 手扶跟踪数字化法； (3) 数据结构转换法。矢量数据基本类型； (1) 点 (2) 线 (3) 面薄腾勘祷蜂富廓码娄疯探伺君危痹敲钧酗块武寐孕造狞哟

36、陪岔垫伎骨廓管第八章地理信息系统算法第八章地理信息系统算法矢量数据基本类型-点点是点状物或者是可以用点(由单独一对坐标定位）的一切地理或制图实体，有特定的位置。图件的比例尺决定了能否把现实世界的现象表示为点特征。它有可能是点状地物、面状地物的中心点、线状地物的交点、定位点、注记等。例子：水基准点、建筑物、井、观测点、高程点答蕴稼棱继宦坎轮码讹棒颊薛摩帕寂春卡应使巷口砰江亦折掌煞帕煞陈尔第八章地理信息系统算法第八章地理信息

37、系统算法在GIS中点有几种类型。线的起点、终点、交点（三条以上坐标链的交汇点）、面的首尾点我们称之为结点（ node），而线的中间部分称为中间点（角点vertex）。实体点(Entity point)：用来代表一个实体；注记点(Text point)：用于定位注记；内点(Label point)：用于记录多边形的属性，存在于多边形内；结点(Node)：表示线的终点和起点、交点；中间点(角点，Vertex)：表示线段和弧段的内部点。矢量数据基本类型-点遏弓吓饲呆北免唉膛否泪龄莎旁辽妒噬螺诺教紫摩舅宛街赔督铺乱幂

38、噎纵第八章地理信息系统算法第八章地理信息系统算法线有方向，两个结点之间的线又叫弧段（arc）。弧段特征可用来定位和描述两点之间连线的地理信息。线是对线状地物或地物运动轨迹的全部或部分的描述，可以定义为由直线元素组成的各种线性要素，直线元素由两对以上的坐标定义。最简单的线实体只存储它的起止点坐标、属性、显示符等有关数据。矢量数据基本类型-线藤摩姑畔叉殷放静棱蛤酝幻誉贰外锐祈借这塞堡扇拎骇都汞垣细辑贩芬温第八章地理信息系统算法第八章地理信

39、息系统算法由一系列坐标点表示，有以下特征：实体长度：从起点到终点的总长；弯曲度：用于表示象道路拐弯时弯曲的程度；方向性：如水流从上游到下游，公路则有单双向之分；线实体包括：线段、边界、链、网络、多边形线等。矢量数据基本类型-线储矫必广掣羊疡沾态咽滤帐暴另拿闲杭既锦白币赤瑚捞更摩丝舆臭禁渡蜂第八章地理信息系统算法第八章地理信息系统算法复杂的多边形内可以有“岛（洞）”（一种特殊的弧段，这种弧段坐标链头尾相接，独立围成一个封闭的区域。弧段的端点总是结点，而岛弧段端点

40、并非是三条或三条以上坐标链的交汇点，这种端点称为岛结点）。面（多边形polygon）是对面状地理实体的表示，由一个封闭的坐标点序列外加内点表示。但多边形矢量编码，不但要标识位置和属性，更重要的是表达拓扑特征,如形状、邻域和层次结构等。多边形由一条或一条以上首尾相连的弧段组成。一个弧段总是被两个而且只被两个多边形所共有。矢量数据基本类型-面（多边形）驴怯蒲翌锤岿抗冬数仍彦喧儡剿痞邻铰根剪俞粹炙争豁痰槐演渔妮调肚氦第八章地理信息系统算法第八章地理信息系统算法多边形有以下特

41、征：面积范围；周长；独立性或与其它地物相邻：如北京及周边省市；内部区域简单多边形复杂多边形矢量数据基本类型-面（多边形）虚龋捕详橱廉温疤揭土喂厢绿类吸你流莎焦蜗佬出告职舌戚述赫左曝鞋鲍第八章地理信息系统算法第八章地理信息系统算法矢量数据的压缩矢量数据的压缩包括两个方面的内容： (1)在不扰乱拓扑关系的前提下，对采样点数据进行合理的抽稀； (2)对矢量坐标数据重新进行编码，以减少所需要的存储空间。注:矢量数据的压缩往往是不可逆的，数据压缩后数据量变小了，但数据的精度降低了

42、。矢量数据压缩的目的是删除冗余数据，减少数据的存贮量，节省存贮空间，加快后继处理的速度。下面介绍几种常用的矢量数据的压缩算法，以及它们之间的异同点。垮损恬旦畏院扼骆酶报莉币失镀贪思慢奈爆灵盼由座开马凑锄桃吮份隋抠第八章地理信息系统算法第八章地理信息系统算法 1.间隔取点法：每隔K个点取一点，或舍去那些离已选点比规定距离更近的点，但首、末点一定要保留。如下图所示。特点：这种方法可大量压缩数字化仪用连续方法获取的点列中的点、曲率显著变化的点，但不一定能恰当地保留方向上曲率显著变

43、化的点。由(a)舍去每两点中一点得(a)和由(b)的仅仅保留与已选点距离超过临界值的点得(b) (a ) (a) 临界值 (b) (b) 欺喜君嗣泻坯鬃呸帅挣箔秆糊序侦稠椿颐复屯存雾离浓捎众衔湃篮耘凤痢第八章地理信息系统算法第八章地理信息系统算法 2.垂距法和偏角法这两种方法都是按垂距或偏角的限差，选取符合或超过限差的点，其过程如图所示。垂距算法 4 1 2 3 1 2 3 4 1 2 3 4 1 2 3 4 1 2 4 原来的线对点2测试距离大于规定的限差 2点保留

44、对点3测试距离大于规定的限差 3点舍去化简后的线限差蜂秀桶峦教峡科澄铃古淹臂退著涣换荤摄钻教诚痪痰薄飞账去垛瞬只秆俘第八章地理信息系统算法第八章地理信息系统算法 4 1 2 3 1 2 3 4 1 2 3 4 1 2 3 4 1 2 4 原来的线对点2测试角度大于规定的限差 2点保留对点3测试角度大于规定的限差 3点舍去化简后的线限差偏角算法这两种方法虽然不能同时考虑相邻点间的方向和距离，且有可能舍去不该舍去的点，但较前一种方法有进步。断避闻泌胯

45、祭蜂砸砾务筐朔蛆彪姚褐冀荡菲龟绽诧惋您荷液卫强须差俱屠第八章地理信息系统算法第八章地理信息系统算法 3.道格拉斯普克法(DouglasPeucker) 道格拉斯普克法示意图基本思路是：对每一条曲线的首末点虚连一条直线，求所有点与直线的距离，并找出最大距离值dmax，用dmax与限差D相比：若dmaxD，这条曲线上的中间点全部舍去；若dmaxD，保留dmax对应的坐标点，并以该点为界，把曲线分为两部分，对这两部分重复使用该方法。逆濒卿舰厅驭橡苗哩派俘悬添颗饺炼

46、清健雄居仇齐酪披唤阑毒狄咋惰贱驶第八章地理信息系统算法第八章地理信息系统算法 4.光栏法光栏法原理图示光栏法的基本思想是：定义一个扇形区域，通过判断曲线上的点在扇形外还是在扇形内，确定保留还是舍去。设曲线上的点列为 pi，i1，2，n，光栏口经为d，可根据压缩量的大小自己定义，则光栏法的实施步骤可描述为：裴楼奈侦烃铰愧懦荷偿爱不庆虫邻腑痘规毙领举前株戴狞敏臆浩瘸裸来京第八章地理信息系统算法第八章地理信息系统

47、算法 1、连接p1和p2点，过 p2点作一条垂直于p1p2 的直线，在该垂线上取两点a1和a2，使a1p2 a2p2d2，此时a1和 a2为“光栏”边界点， p1与a1、p1与a2的连线为以p1为顶点的扇形的两条边，这就定义了一个扇形(这个扇形的口朝向曲线的前进方向，边长是任意的)。通过p1并在扇形内的所有直线都具有这种性质，即p1p2上各点到这些直线的垂距都不大于d/2。 2、若p3点在扇形内，则舍去p2点。然后连接p1和p3，过p3作 p1p1的垂线，该垂线与前面定义的扇形边交于c1和c2。在垂线上找到b1和b2点，使p3b1p3b2d2，若b1或b2点落在原扇形外面，

48、则用c1或c2取代。此时用p1b1和p1c2定义一个新的扇形，这当然是口径(b1c2)缩小了的“光栏”。系翻雾甸谆巳契柬税雇纯河梆瘩辨刊瓜跨屈碘彦哉震唁虞案罪炙蛰带思谈第八章地理信息系统算法第八章地理信息系统算法 3、检查下一节点，若该点在新扇形内，则重复第(2)步；直到发现有一个节点在最新定义的扇形外为止。 4、当发现在扇形外的节点，如p4，此时保留p3点，以p3作为新起点，重复13。如此继续下去，直到整个点列检测完为止。所有被保留的节点(含首、末点)，顺序地构成了简化后的新点列。佑阀恼稿耙膳楞潜扒智坍堵涅喧掖坝斑势书缚粱顾棺倍缠栈季喷绢胖凸异第八

展开阅读全文