| 一种任意简单多边形求差算法 |
| |
| 引用本文： | 姜晓琴,闫浩文,王中辉.一种任意简单多边形求差算法[J].测绘与空间地理信息,2015(9). |
| |
| 作者姓名： | 姜晓琴 闫浩文 王中辉 |
| |
| 作者单位： | 兰州交通大学测绘与地理信息学院，甘肃兰州730070; 甘肃省地理国情监测工程实验室，甘肃兰州730070 |
| |
| 基金项目： | 国家科技支撑计划项目(2013BAB05B01)；甘肃省自然基金项目(148RJZA041)；甘肃省科技支撑计划项目(1304GKCA009)；甘肃省财政厅基本科研业务费(214146) |
| |
| 摘 要： | 提出一种基于线段操作的简单多边形求差算法。该算法的主要过程为:应用基于单调链的扫描线求交算法,求取交点,该过程减少了求交过程中的比较次数,从而提高了求交效率。基于线段操作的结果多边形连接算法,该过程利用基础的计算几何理论,寻找构成结果多边形的边,得到两个多边形的差。实验表明该算法思路简单,数据结构简单,易于编程实现,对于简单多边形求差问题具有普适性。
|
| 关 键 词： | 简单多边形 求差算法 基于线段 单调链 |
An Algorithm for Difference of Two Arbitrary Polygons |
| |
| Abstract: | In this paper, an algorithm are proposed for difference of two polygons.The algorithm includes two steps.Firstly, using the monotone chain scanning method to calculate the intersection point, it has been reduced the computing intersect point time, so as to improve the efficiency of the intersection.Second, the polygon connection algorithm based on the line operation, the process using the basic principle of computational geometry to obtain the difference by searching satisfied edges in polygons.The experiments illustrate that the main idea of this algorithm easy to understand and its date structure is simple, so easy programming, which is great useful and applicable in determining the difference of polygons. |
| |
| Keywords: | simple polygons algorithms for difference based on the line operation monotone chain |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
