Deutsch Intern
    Chair of Computer Science I - Algorithms, Complexity, and Knowledge-Based Systems

    Aggregation of Polygons in Land Cover Maps

    The described optimization-based generalization approach was successfully implemented for land cover data. In geographic information systems, such data are commonly given as sets of polygons that commonly cover a certain area without overlapping each other. Each polygon is assigned to a land cover class. During generalization, some polygons have to become merged, such that all polygons in the output dataset have a size that is not smaller than a given threshold — for the official German topographic database ATKIS, for example, experts have defined such thresholds as a function of scale and land cover classes. For the first time, we have formalized the aggregation of areas in land cover maps as a combinatorial optimization problem. We have identified important quality criteria, namely the semantic similarity between the land cover classes of the input and output polygons and the geometric compactness of the output polygons. We proved that aggregating the polygons optimally with respect to these criteria is NP-hard and, therefore, focused on approaches by mathematical programming and heuristics, which allowed us to solve large problem instances.

    Publications

    Area aggregation in map generalisation by mixed-integer programming.
    International Journal of Geographical Information Science, 24(12):1871-1897, 2010.
    J.-H. Haunert and A. Wolff.
    [doi] [PDF] [BibTeX] 


    Map Generalization by Optimization
    Aggregation of Polygons in Land Cover Maps
    Simplification of Building Footprints
    Variable-Scale Maps
    Map Matching and Map Conflation
     
    Contact

    Lehrstuhl für Informatik I (Effiziente Algorithmen und wissensbasierte Systeme)
    Am Hubland
    97074 Würzburg

    Phone: +49 931 31-85054
    Email

    Find Contact

    Hubland Süd, Geb. Z8 Hubland Süd, Geb. M2