Merge Polygons With Graph Algorithms

05 Feb 2013

There is a group of polygons in a planar space, some of them are adjacent while others are disjoint. The problem is to merge such group of polygons as much as possible (merge those adjacent and overlapping ones, and leave those disjoint ones as they were).

How do you tackle this problem?

One naïve approach is for each polygon in the group, try to merge it with all the rest (pair-wise) and see if merging is successful for the current pairwise merging. If successful, we preserve the merged polygon and use it to merge with the rest of polygons; if not, continue the merging process with the rest of polygons.

How would you keep track of the merged polygons and those that are not merged yet? A stack or a queue? Without a proper data structure, this task might become complicated and daunting.

Another way to see this problem is to see each polygon as a node in a graph; if two polygons are adjacent or overlapping, there is an edge connecting them. This is a graph problem! Now you have this (undirected) graph, but how can you find polygons that can be merged together?

What we actually want is to find connected components within the graph. Each component contains all the polygons that can be merged together at once. To find connected components, a simple DFS (Depth-First Search) running for each node in the graph will do just what we want (finding connected components). However, during the DFS process, you can use an array or a list to record connected components. For example, you might need some array of this form: ccnum[v], where v is representing the index of a node (vertex) and ccnum[v] returns the component number to which vertex v belongs to.

In conclusion, to tackle this problem, you first build a graph of polygons, each polygon represents a vertex in the graph and each edge represents two vertices (polygons) that are adjacent or overlapping to each other. Then you run the algorithm to find connected components within the graph. Once you find the connected components, you then use some polygon merging operation to merge every component, then done.

In the following posts, I will explain the implementation details of this algorithm.