基于点序的任意多边形分割(X)桂工)地理空间信息版本

【文章编号】【中图分类号】【文献标识码】基于点序的多边形分割方法探讨肖飞1唐媛2（1桂林理工大学高等职业技术学院，南宁，5300011,2南宁市房产信息管理服务中心，广西，南宁，530022）摘要:多边形分割是多边形剪切的特殊情况之一,目前多边形分割的算法较为复杂且适用范围有很大的局限性。本文根据多边形的图形定义给出两个约束条件,然后根据约束条件结合多边形点序特征,提出一种基于点序的多边形分割算法。此外本文还依据多边形剪切和多边形分割的关系,扩展基于点序的多边形分割算法在多边形剪切中的实现，经试验分析达到了理想效果。关键词：多边形分割；多边形剪切；点序；折线分割1引言折线分割多边形是多边形剪切的特例，是利用折线与待剪切多边形分割后的部分来剪切多边形。多边形剪切的算法很多，其中Sutherland-Hodgeman算法、梁-Barsky算法、Foley算法及Maillot算法要求裁剪多边形是矩形或凸多边形；Weiler-Athernton算法(内裁剪)的裁剪多边形可以是凸多边形或凹多边形。但是这些算法实现难度都比较大，本文拟从多边形的定义出发，提出一种全新的基于点序的多边形裁剪算法。2算法基本思想2.1两个约束一．多边形是首尾相接的闭合折线，其中首节点和尾节点重合。多边形是首尾相接的闭合折线，其中首节点和尾节点重合。也就是说，假如一个多边形有N个顶点，那么它应有N+1个节点，其中首节点和尾节点重合但是节点序列一个最大一个最小，如下图1所示节点1和节点6。节点1和节点5重合，节点6和节点10重合，其目的是保证节点序列的一致性，比如涉及到节点1和节点6时，也可以认为其节点序列为节点5和节点10。二．多边形特征点顺序为外边界逆时针，内边界顺时针。节点的顺序外多边形以逆时针为准，如图1外多边形顺序1-2-3-4-5，内多边形顺序为6-7-8-9-10，其目的是保证节点序列的一致性，其好处是便于分析交点，交点所在弧段，弧段端点之间的关系。2.2基本思路多边形分割，一般以分割线分割最为常见。如图2所示。多边形分割以后形成多边形1-2-b-a和a-b-3-4。那么如何生成分割后的多边形呢？分析多边形1-2-b-a和a-b-3-4发现，因为边a-b被两个多边形所共有，所以在构建分割后的多边形时边a-b被使用两次，即交点a到交点b和交点b到交点a。根据以上两个约束，为保证数据的特征点顺序，分割后的多边形的特征点顺序必须是1-2-b-a和3-4-a-b。由此可以得到分割多边形的基本思路：判定交点所在的弧段（两相邻节点的连线），求出两交点所载弧段的端点序列，然后根据逆时针原则，分别以边a-b和边b-a构造多边形b-a-1-2和a-b-3-4，即得到多边形分割结果。2.3特殊情形折线分割的难点在于如何构造分割后多边形，如图3所示分割以后的多边形为多边形2-3-b-a和多边形a-b-4-1，那么就会出现节点顺序发生跳转，由节点4跳到节点1，造成多边形节点的顺序突变，如何避免以上情形？如图2，根据多边形的定义，多边形就是闭合折线，首尾重合。那么根据多边形的定义可知，多边形a-b-4-1实际上也就是多边形a-b-4-5，由此通过以上两个约定避免了节点顺序的突变。2.4复杂多边形分割以上仅仅讨论一次相交的情形，那么对于多次相交复杂情形，就必须分析其不同之处。如图4，此时分割线与待分割多边形相交次数为2，那么如何实现基于点序的多边形分割呢？根据两个约束，分割以后的结果多边形点序必须为逆时针且连续，那么可以采取以下措施。首先对交点进行排序，原则如下：以第一个交点为始，两个为一对，进行排序。如图4所示xy一对，mn一对。之后，根据上文的原理，依次求得分割后的多边形x-y-7-8和多边形m-n-3-4；然后对待分割多边形剩余节点和交点进行分析排序，这里应注意剪切部分的相应节点被剪掉，以相应的交点为替，排序结果如下：多边形1-2-n-m-5-6-y-x,多边形x-y-7-8和多边形m-n-3-4，此三多边形即为分割以后的结果。2.5包含空洞多边形分割对于包含空洞多边形分割，如图5：空洞多边形可以分解为两个简单多边形即多边形1-2-3-4-5和多边形6-7-8-9-10。根据约束条件2，外多边形的节点顺序为逆时针，内多边形的节点顺序为顺时针，所以根据点序分割的原理，分割以后的左多边形节点顺序为1-2-d-c-9-10-b-a-5，同理右边多边形为3-4-a-b-7-8-c-d，这样就完成了包含空洞的多边形的分割。3多边形分割的扩展多边形的分割是多边形剪切的特殊情况，以上思路也可以扩展到多边形的剪切。基于点序的多边形剪切，其原理也是利用被剪切多边形与剪切多边形交点所在弧段的关系构造被剪切以后多边形。如图6，用右上角多边形剪切此多边形后，剪切的结果是两多边形的交点及被包含的节点4所构成的多边形a-c-b-4。基于上文点序分割的思想，无论用多么复杂的多边形来剪切目标多边形时，都可以利用其交点和部分相关的节点来构造剪切后的结果多边形，实例如下。假定所有多边形的节点顺序为逆时针，如上图，多边形剪切以后得到结果左边为多边形7-8-x-y和多边形3-4-m-n，右边为多边形1-2-n-m-5-6-y-x，那么如何裁剪多边形和判定剪切后的结果呢？根据上文的两个约束，多边形其实质为闭合的折线，所以可以把剪切多边形a-b-c-d看作一条特殊的折线，对待剪切多边形进行剪切。差异就是分割以后需要判定剪切后的多边形与剪切多边形a-b-c-d的空间关系，即与剪切多边形a-b-c-d空间重叠的多边形即为剪切后的结果。4实例分析传统的CAD中面即为闭合的线，对于面的分割，经常采用先打散原有闭合线数据，再重新拓扑闭合形成新的闭合线。此过程非常费时。以100个面为例，采用传统的方法拓扑构面，费时超过10分钟，若采用此方法，系统仅仅处理被分割的面，效率得到很大提升，一般可以达到时时分割。在南宁市征地内分测量业务中，各地块的调整非常频繁，采用传统模式对所有地块进行处理，效率不高，而采用此方法，基本上可以实现时时修改，大大提升作业效率。以Microstaionv8为平台，实现折线分割功能的流程图如下：5结论基于点序的多边形分割算法原理简单，不仅能实现简单多边形分割，也能完成复杂图形的分割。鉴于多边形的定义、多边形剪切与多边形分割的关系，此算法还可用于多边形剪切功能的扩充，特别适用于CAD平台，经试验验证其原理简单实现方便，可供相关开发人员参阅。参考文献[1]魏金占，熊旭平，施真娥。MapInfo中折线分割功能的扩展[J]信息技术与信息化2005,(1)[2]郭功举。面向对象的复杂多边形裁剪实现[J]现代测绘2003，(8)[3]邬伦,刘瑜,张晶,等.地理信息系统———原理、方法和应用[M].北京:科技出版社,2001.[4]郭仁忠.空间分析(第二版)[M].武汉:武汉测绘科技大学出版社,2001.[5]张新长,曾广鸿,张青年.城市地理信息系统[M].北京:科技出版社,2001.[6]孙家广,杨长贵.计算机图形学[M].北京:清华大学出版社,1995.[7]姚志军,李满春,陈刚,等.地籍管理信息系统中宗地数据的时空组织与查询研究[J].南京大学学报(自然科学版),2002,38(6):7862193.[8]赵新元,潘瑜春,向南平,等.利用GIS校正自动计产数据中的收割面积误差[J].地理与地理信息科学,2005,21(5):41244.[9]石国荣,赵长胜,纪奕君.GIS数据误差分类与来源[J].辽宁工程技术大学学报(自然科学版),2001,21(2):1542156.第一作者简介肖飞（1965-），男（汉族），湖北黄冈人，讲师，桂林理工大学南宁分校土木工程系教师，桂林理工大学大地测量学与测量工程专业工学硕士，主要研究方向：地理信息系统应用，GPS控制测量及空间数据处理等。E-mail：[e-mail],[e-mail]手机：[phone]通讯地址：广西南宁市安吉大道15号桂林理工大学南宁分校邮编：530011StudyofPolygonSplittingBasedOntheIndexofNodesXiaoFei1,TangYuan2（1.VocationalCollegeofhigheducation,GuiLinUniversityofscienceandTechnology;Nanning,530011;2.Nanningcityrealestateinformationmanagementservicecenter,Nanning,530022）Abstract:polygonsplittingisaspecialtyofpolygoncutting,nowadaysthemethodsofpolygonsplittingisverycomplexandhasalotoflimitation.Thepapergivestwolimitationsaccordingtothedefinitionofpolygonandthentogetherwiththesetwolimitationsputsforwardstoanewmethodtofulfillpolygonsplittingbasedontheindexofnodes.Besidesthepaperexpandsthemethodtorealizepolygoncuttingwithrespecttothepolygoncutting,whichisprovedtobeefficientbyanexperiment.Keywords:polygonsplitting;polygoncutting;indexofnodes;polylinesplitting