| 一种有效的复杂多边形裁剪算法 |
| |
| 引用本文： | 王结臣,沈定涛,陈焱明,李利番.一种有效的复杂多边形裁剪算法[J].武汉大学学报(信息科学版),2010(3). |
| |
| 作者姓名： | 王结臣 沈定涛 陈焱明 李利番 |
| |
| 作者单位： | 南京大学地理信息科学系; |
| |
| 基金项目： | 国家基础科学人才培养基金资助项目(J0630535) |
| |
| 摘 要： | 提出了一种基于扫描线思想和梯形分割技术的多边形裁剪算法,其主要步骤包括:计算主多边形(集)与窗口多边形(集)的交点,提取所有交点和多边形边界结点的纵坐标(y)并进行排序;以排序后的y作水平扫描线,分别对主多边形和窗口多边形进行梯形分割,获得两组梯形集合;对这两组梯形集合逐行执行梯形单元"交"运算,最后对结果交集进行边界追踪建立裁剪多边形。实验结果表明,该算法具有较好的计算效率,是一种比较实用的多边形裁剪算法。
|
| 关 键 词： | 多边形裁剪 算法 地理信息系统 |
An Efficient Algorithm for Complex Polygon Clipping |
| |
| WANG Jiechen SHEN Dingtao CHEN Yanming LI Lifan.An Efficient Algorithm for Complex Polygon Clipping[J].Geomatics and Information Science of Wuhan University,2010(3). |
| |
| Authors: | WANG Jiechen SHEN Dingtao CHEN Yanming LI Lifan |
| |
| Institution: | WANG Jiechen1 SHEN Dingtao1 CHEN Yanming1 LI Lifan1(1 Department of Geographic Information Science,Nanjing University,22 Hankou Road,Nanjing 210093,China) |
| |
| Abstract: | We popose an efficient algorithm for complex polygon clipping by adopting the trapezium segmentation technique and scan-line idea.Firstly,we find and compute the intersection points between main polygons and window polygons,then we record and sort the Y values of these points and the points in all polygons.Secondly,we cut all the polygons into some trapezium units by drawing the scan lines on the basis of these Y values and intersecting the edges of all polygons with the scan lines.Thirdly,we complete the t... |
| |
| Keywords: | polygon clipping algorithm GIS |
| 本文献已被 CNKI 等数据库收录！ |
|
