A dynamic approach to area mapping in a geographic information system

Abstract

This report introduces a dynamic approach to area mapping by investigating how a geographic information system can be utilized to create and manage areas. The main purpose of the report is to investigate how to create areas from user generated content and how to store and query the areas efficiently and correctly. The implemented system starts the processing of the input by applying the Autoclust algorithm in order to remove deviating data points. The actual area boundaries are generated using the Alpha shape algorithm. Both algorithms are dependent on the Delaunay graph, which is generated by a Delaunay triangulation algorithm. To dynamically create an area, an alpha value based on the standard deviation of the edge lengths of the Delaunay graph created from the Autoclust step is used. The areas are stored in an R-tree data structure using a MySQL database with spatial extension, allowing for efficient storage and fast queries. Alternative algorithms and data structures are discussed and compared in detail. Denna rapport introducerar ett dynamiskt tillvägagångssätt för areamappning genom att undersöka hur ett geografiskt informationssystem kan användas till att skapa och hantera areor. Rapportens huvudsakliga syfte är att undersöka hur areor kan skapas från användargenererad indata och hur dessa areor kan lagras och sökas igenom på ett korrekt sätt. Det implementerade systemet börjar med att processera indatan genom att applicera Autoclust-algoritmen för att avlägsna avvikande datapunkter. Den faktiska areagränsen genereras genom att använda Alpha shape-algoritmen. Båda algoritmerna är beroende av Delaunaygrafen som genereras genom en Delaunaytrianguleringsalgoritm. För att dynamiskt skapa en area används ett alfavärde baserat på kanternas standardavvikelse i Delaunaygrafen som skapats i Autocluststeget. Areorna lagras i en MySQL-databas med ett spatiellt tillägg, som utnyttjar en datastruktur baserad på R-träd. Detta tillåter effektiv lagring och snabba sökningar. Alternativa algoritmer och datastrukturer diskuteras och jämförs också i detalj.