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
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
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.