２０２０年５月第２期
168声讯台城㊀市㊀勘㊀测
ＵｒｂａｎＧｅｏｔｅｃｈｎｉｃａｌＩｎｖｅｓｔｉｇａｔｉｏｎ＆Ｓｕｒｖｅｙｉｎｇ
Ｍａｙ.２０２０Ｎｏ.２
引文格式：孙春生.基于扫描线法的数字线划图中多边形相交检测算法[Ｊ].城市勘测ꎬ２０２０(２):１２６－１２８.文章编号:１６７２－８２６２(２０２０)０２－１２６－０３ 中图分类号:Ｐ２０９
文献标识码:Ａ
基于扫描线法的数字线划图中多边形相交检测算法
孙春生∗
ibm蓝之路爱的流刑地∗㊀收稿日期:２０１９ １１ １６
作者简介：孙春生(１９７３ )ꎬ男ꎬ博士ꎬ高级工程师ꎬ主要从事城市规划与３Ｓ研究应用工作ꎮ基金项目：上海市科委重点科研计划资助(１７ＤＺ１２０４９０２)
(南京捷鹰数码测绘有限公司ꎬ江苏南京㊀２１００１９)
摘㊀要：针对数字线划图中多边形相交检测问题ꎬ提出了一种基于扫描线法的检测算法ꎮ该算法将多边形按节点拆分成多个线段ꎬ根据多边形节点绘制扫描线ꎬ获得扫描线与线段的交点ꎬ通过分析交点顺序及从属多边形ꎬ检测出相交多边形ꎮ算法效率高㊁数据处理能力强㊁利于编程实现ꎬ算法复杂度跟多边形节点数量正相关ꎬ适合处理数字线划图中大批量简单多边形的相交检测ꎮ
关键词：扫描线法ꎻ数字线划图ꎻ多边形ꎻ相交检测
１㊀引㊀言
数字线划图(ＤＬＧꎬＤｉｇｉｔａｌＬｉｎｅＧｒａｐｈｉｃ)是测绘地
理信息数据的重要载体及表现形式[１]ꎬ随着测绘地理信息行业的发展以及数字城市的不断建设开展ꎬ数字线划图作为数字城市的支撑数据ꎬ在工程㊁设计㊁城市规划管理等多个行业㊁领域得到广泛的应
秦皇岛开发区胡英杰用ꎬ对数据质量的要求也越来越高[２]ꎮ数字线划图中存在大量的以闭合多边形来表示的面状地物(例如房屋㊁池塘㊁草地等)ꎬ多边形相交存在情形多㊁人工判断困难㊁算法判断复杂程度高等问题ꎮ为保障数字线划图数据质量ꎬ亟须快速㊁高效地检测出多边形相交问题ꎮ
目前ꎬ多边形相交问题常用算法主要为：多边形相互关系判别法(通过求多边形间的交点个数结合顶点与多边形关系判别)㊁三角化法[３]㊁包围盒法[４]㊁扫描线法[５]等ꎬ其中Ｂｅｎｔｌｅｙ等提出的扫描线算法最常用ꎮ基于扫描线法ꎬ研究者们也提出了一些优化算法ꎬ例如杨崇俊等提出基于单调链的Ｒｅｄ/Ｂｌｕｅ平面扫描线法[６]㊁陈正鸣等提出多边形链求交的改进算法[７]等ꎮ虽然上述算法可以应用到数字线划图中多边形相交检测问题中ꎬ但数字线划图存在多边形数量大㊁形状相对简单㊁只需出相交多边形不需要求取交点坐标等特点ꎬ上述算法或者无法解决全部相交情形ꎬ或者针对的是求解复杂多边形交点坐标问题ꎬ并不能快速㊁高效地检测出数字线划图中多边形相交情况ꎮ目前针对数字线划图中多边形相交检测算法并不多ꎬ本文充分考虑了数字线划图中多边形相交检测问题的特点ꎬ在扫描线法的基础上ꎬ提出了一种基于扫描线法的数字线划图中多边形相交检测算法ꎮ
垂直与平行教学设计２㊀基于扫描线法的数字线划图中多边形相交
daas检测算法
２ １㊀算法简介
对于数字线划图中的全部多边形ꎬ绘制一条平行
于Ｙ轴的足够长的扫描线ＬꎬＬ满足不经过多边形节点ꎬ且左边最近的节点距其垂线距离为一个极小值(例如０ ０００１ꎬ目的是为了确保扫描线Ｌ与每个多边形的交点都是偶数ꎬ且确保判断准确度ꎬ具体数据可根据实际调整)ꎬ自左向右扫描全部多边形ꎮ如图１所示ꎬ扫描线Ｌ与多边形存在偶数个交点ꎬ对每次扫描产生的交点按Ｙ坐标大小进行排序后ꎬ获得带标识的交点的集合ＬｉｓｔＣＰ<Ｒｉꎬｊ>＝{ＣＰ１ꎬＣＰ２ꎬ ꎬＣＰｍ}(其中每个都带有属性标识<Ｒｉꎬｊ>ꎬ标识该交点是扫描线Ｌ与多边形Ｒｉ的第ｊ个交点)ꎬ通过分析扫描线Ｌ与多边形的交点ꎬ可以得出：若扫描线Ｌ与多边形Ｒｉ的一对交点ＣＰｊ<Ｒｉꎬｊ>与ＣＰｋ<Ｒｉꎬｊ＋１>(ｊ为奇数)之间存在其他交点ＣＰｌ<Ｒｉ ꎬｊ >ꎬ则多边形Ｒｉ与Ｒｉ 必定相交ꎬ以此类推ꎬ直至扫描结束ꎬ可获取全部的相交多边形
ꎮ
图１㊀算法示意图
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议