提出了一个鲁棒高效的内存矢量地图叠加分析算法,采用改进的平面扫描算法计算交点,解决了重叠边、交点位于端点等所有特殊情形。利用交点及其携带的信息来构造结果环,并且将没有产生交点的输入环忽略,或者增加到结果的外环(或内环)集合中去。所有结果环都带有标识码,增加该标识码信息可以简化后续的两个过程-内外环的匹配以及属性的继承。与一一循环方法相比,本文方法对任何叠加操作可以一次计算得到所有的交点。此外还实现了叠加分析操作,并且用一组真实地理数据的不同操作与ESRI的ArcGIS的叠加分析操作进行了比较,计算结果的要素数完全一致;计算时间耗费约为ArcGIS时间耗费的50%-60%。

Robust and efficient internal memory algorithm for vector map overlay is proposed. The algorithm employs the plane sweep idea improved from the traditional plane sweep algorithm to calculate the intersection points, by which all the special cases are handled properly. Then rings of the results are constructed by the intersection points and the information, and original rings with no intersection point are ignored or added to the result as outer rings (contour) or holes. All the generated rings have ID information, which simplifies the following two processes-finding the matching outer ring for each hole and attributes propagation. With this algorithm, we can determine all the intersection points for any overlay operation immediately, not by a one to one loop. We implemented the algorithm, and the comparisons with the one-by-one method (using spatial access method) demonstrated its effi ciency. Besides, we implemented the whole function (including the algorithm and the necessary processes of reading data from and writing data to the disk), and compared it with ESRI's ArcGIS, by which correctness and efficiency of our approach are demonstrated.