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

测绘通报 ›› 2013, Vol. 0 ›› Issue (5): 35-37.

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

鲍其胜¹,王庆¹,何立恒²

1. 南京市测绘勘察研究院有限公司；2. 南京林业大学土木工程学院

收稿日期:2012-04-19 修回日期:2012-10-26 出版日期:2013-05-25 发布日期:2013-05-25

Research on the Polygon Intersection Algorithm Based on Line Operation

Received:2012-04-19 Revised:2012-10-26 Online:2013-05-25 Published:2013-05-25

摘要/Abstract

摘要：

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

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

鲍其胜王庆何立恒. 基于线段操作的多边形求交算法研究与应用[J]. 测绘通报, 2013, 0(5): 35-37.

[1]	徐云耘, 周琛, 李满春. CPU+GPU异构环境下数据密集型矢量多边形地理大数据并行框架[J]. 测绘通报, 2022, 0(5): 110-119.
[2]	谢宏全, 梅雪琴, 蔡东健, 王亚娜, 刘付程. 利用车载LiDAR点云数据提取城市道路规则多边形[J]. 测绘通报, 2020, 0(3): 87-90.
[3]	李俐俐, 李成名, 卢小平, 殷勇, 武鹏达. 顾及邻近五点的建筑物多边形化简方法[J]. 测绘通报, 2019, 0(3): 41-45.
[4]	王飞, 李成名. 利用多边形骨架线生成房屋模型算法研究[J]. 测绘通报, 2017, 0(1): 69-73.
[5]	刘洋, 兰泽英, 张荣. 顾及居民地分布特征的建筑物分组合并算法研究[J]. 测绘通报, 2015, 0(12): 50-53.
[6]	康建荣李新刘翘楚. 多边形区域信息最佳注记位置分析[J]. 测绘通报, 2014, 0(6): 34-38.

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

Research on the Polygon Intersection Algorithm Based on Line Operation

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价