基于简单要素模型的多边形分割算法

编号 zgly0001607876

文献类型 期刊论文

文献题名 基于简单要素模型的多边形分割算法

作者 田光  谢忠  吴亮 

作者单位 中国地质大学信息工程学院  教育部地理信息系统软件及应用工程中心 

母体文献 地理与地理信息科学 

年卷期 2010年01期

年份 2010 

分类号 TP391.41 

关键词 计算交点  多边形分割  多边形运算  简单要素模型  GIS 

文摘内容 多边形是GIS研究和应用中使用最频繁的几何对象,该文描述了基于简单要素模型的任意多边形分割算法。从计算几何出发,结合GIS空间数据的特点,将基于简单要素模型的多边形分割算法设计为:1)对多边形及分割线的边界排序,基于扫描线及外包矩形检测查找可能相交的线段,提高相交线段的搜索效率;2)计算交点生成结点信息(包括交点坐标、线号及交点的出入),并存储在独立的单向链表中;3)根据结点链表和原多边形坐标搜索结果多边形。该算法能够分割任意简单多边形(凹凸、曲线边界和带洞的多边形)以及有共享边的多边形。最后在MapGIS7.0平台上,实现了基于简单要素类的多边形分割功能。