基于线段操作的多边形求交算法研究  

Research on the Polygon Intersection Algorithm Based on Line Operation

作　　者：鲍其胜[1] 王庆[1] 何立恒[2] 

机构地区：[1]南京市测绘勘察研究院有限公司,江苏南京210005 [2]南京林业大学土木工程学院,江苏南京210037

出　　处：《测绘通报》2013年第5期35-37,共3页Bulletin of Surveying and Mapping

摘　　要：根据多边形之间的相交状态求所有目标多边形线段与源多边形边界的交点;利用点与多边形关系判别法则判断出目标多边形与源多边形的公共线段;目标多边形与源多边形对调,再次判定出公共线段;最后将公共数据选择集中的公共线段首尾连接构成闭合多边形即为两个多边形求交结果。求交算法以线段操作为核心求解两多边形的交集,通过遍历公共线段来完成交集多边形边界的构建。该算法结构简单,易于编程实现,计算工作量小,求交效率高,已成功应用在土方计算软件开发中,在地图制图和地理信息空间分析等方面有广阔的应用前景。

关 键 词：多边形 求交算法 线段操作 公共面 

分 类 号：P208[天文地球—地图制图学与地理信息工程]