piwik-script

English Intern
    Lehrstuhl für Informatik I - Algorithmen, Komplexität und wissensbasierte Systeme

    Aggregation von Flächen unterschiedlicher Landnutzung

    Der beschriebene Generalisierungsansatz durch Optimierung konnte erfolgreich für Landnutzungsdaten umgesetzt werden. Diese sind in Geographischen Informationssystemen in der Regel durch Polygone gegeben, die gemeinsam ein Gebiet überschneidungsfrei abdecken. Jedem Polygon ist eine Landnutzungsklasse zugeordnet. Bei der Generalisierung solcher Daten sind Polygone zusammenzufassen, so dass neue Polygone entstehen, die eine vorgegebene Mindestgröße erreichen — für das deutsche Informationssystem ATKIS sind solche Mindestgrößen beispielsweise in Abhängigkeit des Maßstabs und der Landnutzungsklasse festgelegt. Wir haben erstmals die Generalisierung von Landnutzungsdaten als kombinatorisches Optimierungsproblem formalisiert und dafür wichtige Qualitätskriterien identifiziert, nämlich die semantische Ähnlichkeit zwischen Landnutzungsklassen der ursprünglichen und der neuen Polygone sowie die geometrische Kompaktheit der neuen Polygone. Wir konnten zeigen, dass es NP-schwer ist, eine Lösung zu finden, die hinsichtlich dieser Qualitätskriterien optimal ist. Bei der Entwicklung von Algorithmen zur Lösung des Problems haben wir uns daher auf Verfahren der mathematischen Programmierung sowie auf effiziente Heuristiken konzentriert, mit denen wir große Instanzen lösen konnten.

    Literatur

    Area aggregation in map generalisation by mixed-integer programming.
    International Journal of Geographical Information Science, 24(12):1871-1897, 2010.
    J.-H. Haunert und A. Wolff.
    [doi] [PDF] http://www.bibsonomy.org/bibtex/2345c20fc0b2909b4b1f7cd2e61914a57/haunert?format=bibtex[BibTeX]