GIS环境中一种高效的多边形剪裁方法

AN EFFICIENT ALGORITHM FOR CLIPPING POLYGON IN GIS

在Weiler算法的基础上提出一种在GIS环境中计算非凸多边形之间的剪裁区域的新算法。该算法前提是多边形已根据梯形分解法被分解成若干个梯形,首先计算两个多边形之间的交叉点,并在计算的过程中按Weiler算法中的出点和入点来标示它们,然后逆序遍历所有的交叉点来确定剪裁区域。该算法通过减少交叉点的计算时间和遍历时间来提高Weiler算法的效率。在GIS这种具有频繁拓扑关系运算的环境中可以很好地提高运算效率,最后通过实验验证,即使在接近最坏的情况下,该算法也优于传统的Weiler算法。

This paper introduces a new algorithm to calculate clipping area between two non-convex polygons in GIS environment by improving Weiler algorithm. The polygon having been decomposed into a set of trapezoids before clipping according to the decomposition method of trapezoid is the precondition of the algorithm. First the cross points between two polygons are calculate, and are flagged when calculating them to show if they are the entry point or exit point as described in Weiler algorithm. Then the clipping areas are determined by traversing entire cross points in reverse order. It ameliorates the efficiency of Weiler algorithm through minimising the times consumed on calculating and traversing cross points, which is also an ideal way to improve operation efficiency in the environment of GIS which has frequent topological relation operations. Finally the experiment validated that this algorithm outperforms traditional Weiler algorithm even in the condition approximating the worst situation.