An algorithm for polygon clipping, and for determining polygon intersections and unions
An algorithm for polygon clipping, and for determining polygon intersections and unions
复制标题
多边形裁剪以及确定多边形交集和并集的算法
DOI：
10.1016/j.cageo.2006.08.008
复制
发表时间：
2007-05-01
影响因子：
4.4
通讯作者：
Zalik, Borut
中科院分区：
文献类型：
--
作者：
Liu, Yong Kui;Wang, Xiao Qiang;Zalik, Borut
本文介绍了一种通用的多边形裁剪算法，多边形裁剪是GIS中的常用操作。在所提出的解决方案中，剪裁多边形可以是凹形的并且可以包括孔。该算法基于所谓的入口/出口交点属性，该属性仅必须在第一个计算的交点处明确确定。它使用基于单链表的简单但高效的数据结构。布尔并集和输入多边形之间的差异也可以在小的修改后确定。该算法可以很容易地适应由多边形集合组成的区域之间的布尔运算。 (c) 2006 Elsevier Ltd. 保留所有权利。
This paper introduces a universal algorithm for polygon clipping, which is a frequent operation in GIS. In the proposed solution, the clipping polygons can be concave and may include holes. This algorithm is based on so-called entry/exit intersection point property, which has to be explicitly determined only at the first calculated intersection point. It uses a simple but efficient data structure based on a single-linked list. Boolean union and the difference between input polygons can also be determined after small modifications. This algorithm can easily be adapted to Boolean operations between regions composed of polygon sets. (c) 2006 Elsevier Ltd. All rights reserved.