OPTIMIZATION METHODS FOR AREA AGGREGATION IN LAND COVER MAPS

J.-H. Haunert

Institute of Cartography and Geoinformatics, Leibniz Universitaet Hannover, Germany

jan.haunert@ikg.uni-hannover.de

 

The aggregation of areas is an important subproblem of the map generalization task. Especially, it is relevant for the generalization of topographic maps which contain areas of different land cover, such as settlement, water or different kinds of vegetation. An existing approach is to apply algorithms that iteratively merge adjacent areas, taking only local measures into consideration. In contrast, global optimization methods are proposed in this paper to derive maps of higher quality.

Given a polygonal subdivision in which each polygon is assigned to a land cover class, we consider the problem of aggregating polygons such that a defined area threshold is satisfied. The aggregation is directed at two objectives: Classes of polygons shall change as little as possible and compact shapes are preferred. In this paper, the problem is formalized and two different approaches are compared, namely mixed integer programming and simulated annealing.

The problem can be formulated as Mixed Integer Program (MIP) in different ways. These options are discussed with respect to the applicability of standard branch and cut techniques that are implemented in commercial software packages. Heuristics are defined to speed up the processing; their effects on the obtained result are shown.

Simulated annealing generally requires the definition of a neighborhood structure that defines possible changes of a feasible solution during one iteration. It turned out that it is not trivial to find a neighborhood structure that ensures the connectivity of the solution space for the discussed problem. Thus, the optimal solution can not be reached from all possible start solutions via a feasible path. The problem is solved by relaxing the hard threshold constraints and penalizing solutions with small areas by definition of an additional term in the objective function. The method starts then with a solution that can be obtained with a simple greedy algorithm. An annealing schedule is defined for the simulation. In order to end up with a feasible solution, a method is proposed to repair solutions with violated threshold constraints.

First tests showed that the solutions of both methods are of high quality and very similar. The MIPs resulted in slightly better solutions, while the simulated annealing method turned out to be faster.

Finally, it is discussed how the presented methods can be integrated in a more comprehensive generalization framework that comprises also polygon decomposition, collapse and line simplification. A complete workflow for the generalization of land cover maps based on these operators is introduced.