基于MBR的多边形内点自动生成算法

第7卷第2期洲绘工程1998年6月ENGINEERINGOFSURVEYINGANDMAPPINGVo1．7，No．2／UN．，1998基于MBR的多边形内点自动生成算法蔡少华秦志远——一(解放军澜绘学院)查鲞一_一(中国矿业大学北京研究生部)县时三纯；M坠，空丑多彳f，《7,胡enn~书三：P208’挚龌／A孬q书瓷料分类号，NewMethodtoAutomaticallyCreatePolygonNodeIJ'singMBRCaishaohua~Qin￡^f册0Z^“TaD留(①ZhengzhouInstituteofSurveyingandMapping，Zhengzhou，450052②BeijingGraduateSchoolofChinaUniversityofMin．＆Tech．，3~ijing，100083)AbstractOnthebaseofanalyzingthetraditionmethodsofmakingpolygonnode，thispaperputforwardanewmethodtOautomaticallycreatenodebymeansofMBR(Mini—mumboundingrectangle)．ThemethodnotonlyadapttOtheconcaveandprotuberantpolygons．butalsocanassurethenodeisrightwhenthepolygonhasislands．KeywordsGeographicInformationSystem；MBR；Spatialrelation地理信息系统(GeographicInformationSystem，GIS)是在计算机硬软件支持下，运用系统工程和信息科学的理论方法，综合地、动态地获取、存储、管理、分析和描述整个或部分地球表面与空间和地理分布有关的数据的空间信息系统。由GIS的定义可以看出，在地理信息系统中集中存储了以下共同内容：1)空间分布位置信息；2)属性信息；3)拓扑空间关系信息。拓扑空间关系信息是空同分析、辅助决策等的基础，也是GI$区别于CAD(计算机辅助设计)等的主要标志。在拓扑空间关系的自动生成过程中，多边形内点的自动生成非常关键，也非常重要，如利用内点进行多边形嵌套关系的判别等。而且，多边形的内点在空间关系生成之后，在属性连接、注记、专题符号配置、空间关系识别、空间分析等方面都必不可少。传统的一些内点生成方法在某种程度上有一定的缺陷，本文基于MBR介绍一种简单、可行的多边形内点自动生成方法1多边形内点生成传统方法分析1．1手工标识法在多边形追踪出来以后，利用鼠标在多边形内取一点，然后通过点在多边形内的判别方法，判断该点是否在多边形之内，如不在，则继续进行。该方法带有大量的人工干涉，工作量太，而且容易出错。尤其当图面要素比较多时，通过人工标识，识别起来比较困难．难免产生遗漏。收蔷日期1§97、维普资讯http://www.cqvip.com·62·测绘工程第7卷1．2质心量测法令(，)为多边形的质心，则X=∑曲／∑Wi，=∑／∑i1|11E一1其中，H-为权重，(五．Y)为多边形边界点坐标。直接以质心作为多边形的内点。对于凸多边形，质心肯定在多边形内。但对凹多边形，质心则不一定在多边形内。如图1所示，该凹多边形的质心就不在多边形之内。为了使凹多边形的内点正确，首先必须进行点在多边形内判别，如不在多边形之内，就必须将质心进行人工或一定的算法移到多边形内。该方法的优点是计算简单，对凸多边形完全能满足条件，凹多边形圈1凹多地形示意圈则必须利用一定的方法进行处理。缺点是需要人工干预，具有试探性，在不利的情况下需要多次试探才能生成一个内点。2内点自动生成原理2．1基于MBR内点自动生成方法最小外切矩形MBR指的是包围空间目标实体投影的最小矩形。对矢量图形，MBR是通过计算目标实体的最小与最大x、y坐标进行求取．并用左下、右上坐标进行表示，即MBR={(咒，Yl_)，(X～．y～))。基于MBR，多边形的内点计算原理如图2所示。首先，对MBR在x方向的长度DX与y方向的宽度DY进行比较，如图2中·DX>DY，则在DX／2处作垂直于x轴的直线，求取该直线与多边形的交点y坐标系列，并对y坐标进行排序，形成排序y坐标系列{y，y．-，y)，其中y最大，y最小，然后，奇偶配对，如y与yz，y。与等，求取间距最大区间，设为y与y，则多边形的内点坐标为((一+x～)／2，(y+YⅢ)12)。该方法不仅简单，而且适用面广，对不包含岛屿的凸、凹多圈2多边形内点自动求取示意圈边形都能保证内点在多边形内。2．2台岛屿”多边形内点自动生成方法在多边形包含“岛屿，特别是包含多个“岛屿时，多边形的内点可能被“岛屿覆盖，