Abstract
Topographic databases normally contain areas of
different land cover classes, commonly defining a
planar partition, that is, gaps and overlaps are not
allowed. When reducing the scale of such a
database, some areas become too small for
representation and need to be aggregated. This
unintentionally but unavoidably results in changes
of classes. In this article we present an
optimisation method for the aggregation problem.
This method aims to minimise changes of classes and
to create compact shapes, subject to hard
constraints ensuring aggregates of sufficient size
for the target scale. To quantify class changes we
apply a semantic distance measure. We give a graph
theoretical problem formulation and prove that the
problem is NP-hard, meaning that we cannot hope to
find an efficient algorithm. Instead, we present a
solution by mixed-integer programming that can be
used to optimally solve small instances with
existing optimisation software. In order to process
large datasets, we introduce specialised heuristics
that allow certain variables to be eliminated in
advance and a problem instance to be decomposed into
independent sub-instances. We tested our method for
a dataset of the official German topographic
database ATKIS with input scale 1:50,000 and output
scale 1:250,000. For small instances, we compare
results of this approach with optimal solutions that
were obtained without heuristics. We compare
results for large instances with those of an
existing iterative algorithm and an alternative
optimisation approach by simulated annealing. These
tests allow us to conclude that, with the defined
heuristics, our optimisation method yields
high-quality results for large datasets in modest
time.
Users
Please
log in to take part in the discussion (add own reviews or comments).