vegagis中矢量空间分析的关键算法研究

《vegagis中矢量空间分析的关键算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学院计算技术研究所博士学位论文VegaGIS中矢量空间分析的关键算法研究姓名：程振林申请学位级别：博士专业：计算机系统结构指导教师：唐志敏20061001摘要空间分析是GIs的核心和灵魂，是GIs区别于一般的信息系统、CAD或者电子地图系统的主要标志之一，也是GIS的主要技术门槛。二维矢量数据的空间分析能提供各类要素信息提取和辅助决策。因此，空间分析在GIs基础平台研发中的重要性不言而喻。叠加分析和缓冲区分析是矢量数据的空间分析中最为重要的两种类型。也是本文的主要研究内容。本文在分析当前GIs业界和学术界研发现状基础上，总结了矢量空间分析的基本功能特征，将叠加分析分解为点与

2、线的关系、线与线的交点、面与面的叠加等基本问题并结合计算几何、空间数据索引等领域的最新研究成果，对平面中线段求交点的BO算法着重阐明了该算法的核心流程改进的关键是维护B0中的不变式，并对于求“点和线段的方向”函数给出了鲁棒实现，这些内容为后续研究奠定基础。要素叠加分析是GIs矢量空间分析中最核心的计算之一。面面叠加，由于其在Gls的空间分析和查询中非常基础和关键，并且实现难度大，受到了较多的关注。基于H孤算法，本文提出了改进算法H柚．E并给出了面面叠加分析的实现。相比于H姐算法，H硒．E算法在不改变算法的时间复杂度的前提下，充分考虑了GIS数据集中会导致Han算法失效的特殊情形并

3、且提出了改进方法。H强-E算法可以在一次扫描过程中输出交，并、差、对称差、几何并的结果，并求得每个结果多边形的父多边形。对于多边形的洞，以较低的时间和空间复杂度求得其归属多边形。基于经过裁剪的H蚰．E算法并结合空间数据索引实现了点面叠加分析和线面叠加分析。算法时间复杂度是点面为n109n(n为坐标点数)，线面为伍+k)】09n(n为点数，k为交点数)。而计算几何中的经典算法和可获得的开源软件中的算法的复杂度皆为O(n2)。本文提出了基于改进的平面扫描算法的缓冲区分析方法，相对于传统的矢量算法，总体效率高，并且减少了需要处理的特殊情况。本文中给出的算法支持线的端点平头、圆头的缓冲边

4、界。在不增加空间复杂度的前提下，本文中的算法相对于文献中给出的算法运行时间上能减少5％。本文提出了一种基于空间数据索引和平面扫描算法的分条带叠加分析的方法，该方法可用来处理大数据量的叠加分析。实际测试表明该方法性能优于ArcGIs9。对于GIs需要支持的矢量空间分析算法(以A们Is为参考系统)，本文系统地给出了实现方法并通过实际数据集验证了其正确性和效率。依据本文的算法，可以实现当前ArcGls9矢量空间分析的所有功能。而且，算法流程清晰、一致，可以有效减少未来代码维护的工作量。同时，算法的时间复杂度低，算法设计对于较大规模的数据量具有很好的扩展性。本文的工作已经在VcgaGIs

5、中得到了应用。经过测试，运行稳定、高效，取得了良好的效果。关键词：地理信息系统，Bo算法，ⅦgaGIs，矢量空间分析，叠加分析，缓冲区分析，Hall算法，腧-E算法，平面扫描ⅡR髓∞腿h柚dImpIementaHon伽V酏torSpatiaIAnalysisalengzhenlin(computcrArchitectllrc)DircctcdByTangzhimjnSpatial柚alysis，whichdailIlsthcboundarybeM啪GIs缸dcommonm粗agementill：fo咖ationsyst锄，CAD卸delcctmnicmap，isthekcmelo

6、fGIs．1W0dimensi蛐alvc枷orspatial锄lysis，∞mbincdwilhtheattributcofspatialda氇c柚pfovidevcr翰tilefIlndi∞aliti鹳ofinfo衄ati∞cxtraction．Sotheimpon锄ccofVcclorspatial柚alysis伽notbeemph鸫izcd锄ou曲forthcdcVelopmentofGlsplat硒rIn．Mapoverlay卸dbu自ccr卸alysisa∞腑otypicalfIInctio璐ofVecIorspatial彻alySis．Thisthesis缸u∞s衄t

7、hekcyalgofitllmsfofmap0veday柚dbu岱盯analysis．Aft盯thcsurvey0fre∞arch柚ddevel叩memeffons￡romGIsindust哆thisthesis鲫mm撕esthef11ncti彻listofw蜘rspatial柚alysis．ThesefIlnctionsc蛆brcal【downintothcb勰icbuildingblocks：tlIerelationbct、Ⅳ嘲(1)pointwimunc，(2)linewi