GIS算法基础lecture3-topology

Lecture3拓扑,什么是拓扑什么是拓扑关系拓扑关系的重要性GIS中常用的拓扑关系GIS空间拓扑关系形式化描述的发展阶段,为什么九条路不可能不相交在世界各地,广泛地流传着一道数学名题,尽管说法有不同,但实质上是同一个问题:某地有三个村庄和三所学校,从每个村庄到三所学校各修一条路,能不能使这九条路互不相交呢?您可能以为,只要不怕费事绕绕弯子,这事是不难办到。可事实并非如此,上述想法是不能实现的,这里有着奥妙的数学原理。19世纪,瑞士大数学家欧拉,在研究多面体的顶点数、棱数和面数的关系时,发现了一个规律,如立方体有8个顶点、12条棱、6个面、具有关系8-12+6=2。基它多面体也是这样,即一个多面体若有n个顶点、m条棱、p个平面,则一定有n-m+p=2,这就是著名的欧拉公式。有了欧拉公式,前面的问题就可迎刃而解了。把问题看成是立体图形,每个村庄或学校就相当一个顶点,一条路就相当一条棱,用路围起来的部分就相当于一个面。因为有九条棱、六个顶点,那么有6-9+p=2,即p=5,就是说应该有5个面;而从另一个角度考虑,从一个村庄出发,走一条路就到达一所学校,再走一条路就到达另一个村庄,再走一段路就到达另一所学校,再走一段路才能回到原地。所以围成一个至少要四段路即四条边,现有9条棱,若数面的边当然是18条面,至少四条边围一个面,当然围不成5个面。也就是说九条路的设想是不能实现的。读者们不妨想一下,若只修八条路能否实现?对这类问题的研究,已经形成了数学领域的一个分支拓扑学。它对工程设计,机器元件的设计,集成电路设计,电子计算机的程控、各种信息网络系统的建立,都有广泛的应用。,世界近代三大数学难题之一(另外两个是费马定理和哥德巴赫猜想)四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯格思里(FrancisGuthrie)来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以只用四种颜色着色，使得有共同边界的国家着上不同的颜色。”,用数学语言表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”这个结论能不能从数学上加以严格证明呢？他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠，可是研究工作没有进展。这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明。不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。,四色猜想,什么是拓扑,拓扑是研究几何对象在弯曲或拉伸等变换下仍保持不变的性质。拓扑学经常被描述成“橡皮泥的几何”，就是说它研究物体在连续变形下不变的性质。比如，所有多边形和圆周在拓扑意义下是一样的，因为多边形可以通过连续变形变成圆周，下边这个图，一个茶杯可以连续地变为一个实心环，在拓扑学家眼里，它们是同一个对象。,拓扑关系,拓扑常被解释为通过图论这一数学分支,用图表或图形来研究几何对象排列及其相互关系.对矢量数据模型重要的是有向图,包括点和有向线(弧段),最基本的拓扑关系是拓扑关联和邻接。拓扑关联是不同拓扑元素之间的关系。如结点与链，链与多边形等。拓扑邻接是相同拓扑元素之间的关系。如结点和结点，链和链，面和面拓扑包含是面与其他拓扑元素之间的关系。如果点、线、面在该面内，则称被该面包含。如某省包含的湖泊、河流等。连通关系：拓扑元素之间的通达关系。如点连通度，面连通度的各种性质及相互关系层次关系：相同拓扑元素的等级关系。如国家有省，省由县组成等。,邻接矩阵和关联矩阵,拓扑对于数据编辑，如GIS数据制作者会发现在查找错误、确保线的正确会合和多边形的正确闭合方面，使用拓扑是绝对必要的,近年来，计算机技术发展非常迅速，虽然GIS的输入、存储和输出功能进展较快，但是空间分析功能的发展就显得比较落后。而空间分析是建立在空间对象位置和属性表达以及对象间复杂空间关系表达的基础上，若要提高空间分析能力，必须解决空间关系描述与表达，因此空间对象的拓扑关系也就成了研究的重点。空间分析在某种程度上是处理空间实体间的相互关系,例如叠置分析处理多个空间目标之间的相交、覆盖等拓扑关系;网络分析处理空间目标的拓扑邻接与关联;一致性分析检验同一目标在多重表达中是否产生拓扑矛盾。在这些应用分析中,拓扑信息通常被视为最基本的一类空间信息。空间数据库包括表达空间目标分布的空间数据(位置数据和拓扑关系数据)和非空间数据(属性数据)。传统关系数据库的查询语言如SQL只是提供了对简单数据类型(如整数或字符)的相等或排序等操作,而不能有效地支持包含空间数据的空间查询以及处理。为了解决空间数据库在空间查询、分析与处理中的应用问题,则需要空间查询语言的支持。为此,许多学者提出了空间查询语言设计的构架,但大部分研究都是对传统关系数据库SQL进行扩展。为了构造空间查询,ARC/INFO中通过Macro语言方式将9交模型描述的结果(分离、相接、相交、包含/包含于、覆盖/覆盖于、相等)加入到查询命令中,Oracle中是把9交模型与SQL相结合,为用户和GIS软件提供一个灵活的接口,使查询功能扩展到空间域。Egenhofer等人称这种具有空间查询功能的SQL为空间SQL。,拓扑关系在空间分析中的重要性,GIS软件中常用的三种基本拓扑关系,Esri规定用于ARC/INFO的标准拓扑矢量数据格式为coverage,并以点、线、面对图层归类。图层支持的三种基本拓扑关系为：Connectivity(连接性)弧段和节点:Arcsconnecttoeachotheratnodes.Areadefinition(面定义)多边形和弧段:andareaisdefinedbyaseriesofconnectedarcs.Contiguity(邻接性)多边形和多边形:arcshavedirectionsandleftandrightpolygons,拓扑关系的表示,Geodatabase中基于规则的拓扑关系的建立,拓扑规则参考Geodatabase中基于规则的拓扑关系管理机制.doc;Topology_rules_poster.pdf拓扑编辑的两个重要方面是：共享点（结点连接编辑）共享边（多边形连接的编辑）参考黄杏元地理信息系统概论P39Geodatabase建立拓扑的基础1)Geodatabase实现拓扑的基础是“几何重合”，Geodatabase中的地理对象都是实体存储，主要是根据节点坐标是否重合来判断地理要素之间是否存在某种拓扑关系2)拓扑只能在要素集(featuredataset)中创建，参加创建拓扑的所有要素类(featureclass)必须具有相同的空间参考3)参与拓扑创建必须是简单要素类，注记类，尺寸和几何网络要素类不能参与拓扑的创建4)单个要素集可以创建多个拓扑,TopologicaleditinginARCGIS,ToolsfortopologicaleditingareplacedindifferentapplicationsandondifferenttoolbarsinArcGIS,therearethreegroups:CoveragetoolsMaptopologytoolsToolsfortopologyrules,EditingUsingMapTopology,Amaptopologyisatemporarysetoftopologicalrelationshipsbetweenthepartsoffeaturesthataresupposedtobecoincident.Forexample,amaptopologycanbebuiltbetweenaland-uselayerandasoillayersothattheiroutlinesarecoincident.Amaptopologycanalsobebuiltbetweenastreamlayerandacountylayersothat,whenastreamservesasthecountyboundary,theyarecoincident.Layersparticipatinginamaptopologycanbeshapefilesorgeodatabasefeatureclasses,butnotcoverages.(shapefilesarenontopologicalbutcanparticipateinatemporarymaptopologythatappliesonlytocoincidentfeatures).Coincidentfeaturesinamaptopologyaredefinedbyaspecifiedclustertolerance.Theclustertolerancecansnapverticesandlinesiftheyfallwithinthespecifiedtolerance.Functionally,theclustertoleranceissimilartothefuzzytoleranceforeditingcoverages.And,likethefuzzytolerance,aclustertoleranceshouldnotbesettoolarge.Alargeclustertolerancecanunintentionallyaltertheshapeoflinesandpolygons.Agoodstrategyistouseasmallclustertoleranceandtochangeitonlytodealwithmoreseverebutlocalizederrors.Toeditwithamaptopology,wecreateamaptopology,specifytheparticipatingfeatureclasses,anddefineaclustertolerance.ThenweusetheeditingtoolsinArcGIStoforcethegeometriesoftheparticipatingfeatureclassestobecoincident.,Editingusingtopologyrules,Thegeodatabasedatamodelhasatotalof25topologyrulesforpoint,line,andareafeatures.editingwithatopologyruleinvolvesthreebasicsteps.Thefirststepcreatesanewtopologybydefiningtheparticipatingfeatureclasses,theranksforeachfeatureclass,thetopologyrules,andaclustertolerance.Therankdeterminestherelativeimportanceofafeatureclassintopologicalediting.supposesatopologyincludestwofeatureclassesofsoilandvegetationcover.Ifthesoilfeatureclassisdeemedtobemoreaccurateofthetwo,itisassignedahigherrank,thusensuringthatitspolygonboundarieswillnotbemovedasmuchastheotherfeatureclass.Thesecondstepisvalidationoftopology.Thisstepevaluatesthetopologyruleandcreateserrorsindicatingthosefeaturesthathaveviolatedthetopologyrule.Atthesametime,theedgesandverticesoffeaturesintheparticipatingfeatureclassesaresnappedtogetheriftheyfallwithinthespecifiedclustertolerance.Thesnappingusestherankingofthefeatureclasses:featuresofalower-rankfeatureclassaremovedmorethanfeaturesofahigher-rankfeatureclass.validationoftopologyissimilartocleaningacoverageandtheclustertolerancepaystheroleofthefuzzytolerance.Validationresultsaresavedintoatopologylayer,whichisusedinthethirdstepforfixingerrorsandforacceptingerrorsasexceptions.Thegeodatabasedatamodelprovidesasetoftoolsforfixingtopologicalerrors.F