范俊甫，孔维华，马 廷，周成虎，季 民，周玉科

1.山东理工大学建筑工程学院，山东 淄博255049；2.中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室，北京100101；3.山东科技大学测绘科学与工程学院，山东 青岛266590

1 引 言

多边形叠加分析是地理信息系统常用的空间分析工具之一，具有典型的高算法复杂度和计算时间密集性特征［1］，在空间分析算法体系中占有重要地位，是地理数据处理领域所面临的核心且困难的基础问题之一［2－3］。简单多边形的相交测试是线性时间且可以变换为线段求交问题采用Shamos－Hoey算法［4］或 Bentley－Ottmann算法［5］实现快速求解，而对于复杂多边形的叠置分析问题，最坏情况下则需要O（N2）的时间［6］。简单要素模型条件下的任意多边形叠加分析问题通常基于多边形裁剪算法解决，目前公认的既支持任意形状多边形裁剪又能在有限时间内获得正确计算结果的算法包括 Weiler算法［7］、Vatti算法［8］和Greiner－Hormann算法［9－10］。其中后两者所采用的双线性链表数据结构和计算速度均优于前者［11］。尽管 Greiner－Hormann算法被认为比Vatti算法具有更简单的原理和实现过程，也声称拥有更高的执行效率，但在某些情况下其计算效率却低于 Vatti算法［12－13］。文献［14］实现了对Vatti算法的改进，解决了输入多边形中不允许出现水平边的问题，增强了算法稳定性，但其依靠递归实现的交点求解在处理大数据时易出现资源消耗过大的问题［15］。尽管上述多边形裁剪算法具有精度高的优点，但是在数据结构复杂度和计算量等多个方面却表现出了一定的不足。……