Efficient algorithm for polygon overlay for dense map image data sets

摘要

A map consists of a finite set of mutually disjoint polygons. A data structure and efficient algorithm for polygon overlay of dense map image data sets are discussed. The data structure, referred to as the ending-x structure, is a variant of the y-partition structure developed by Merrill which is still widely acclaimed as an optimum raster data structure. The modest refinement of the ending-x structure further reduces raster data volume. More importantly, it can significantly enhance the process of polygon overlay for multiple map image data sets. Considering the density of many map image data sets, and the significance of the polygon overlay problem to spatial data handling, these are significant advances. The paper describes the ending-x data structure and compares the algorithm for polygon overlay suggested by Merrill with one employing the ending-x structure.