Merge Polygons With Graph Algorithms - Implementation

18 Feb 2013

From previous post, I described the algorithm for merging a group of polygons in a planar space. Now let’s talk about its implementation.

First thing before running a graph algorithm is to build a graph data structure. Common graph data structures are: adjacency list and adjacency matrix. Say you have chosen adjacency list, and you have no priori-knowledge about the spatial relationship of those polygons you are processing, then you need O(|V|^2) worst-case time to build an adjacency list for those polygons, since for each node you need to scan the node list to find out its neighbors.

However, if the polygons (nodes) are geometry objects in SQLite, then you can use SQLite R*Tree module to help you search for adjacent polygons around a bounding box, which can speed up the process of building adjacency list quite a bit.

Boost Graph Library is also what we need for the task described above. It has adjacency list and numerous algorithm templates ready for use. For our purpose here, we only need the algorithm to find connected components in an undirected graph, and here it is! There is even an example showing how to use such template functions.