[GIS] A linestring merger algorithm

cmergepostgispostgresql

I'd like to merge linestrings which touch, but do not cross. The linestrings share the same SRID and come from a PostgreSQL 9.2/PostGIS 1.5 database. Within the table I query are several line strings, not just those I want to merge, but also others.

For example, consider lines from the OpenStreetMap database. I start with a temporary table that has all linestring which are tagged as being part of the power grid, together with the respective voltages. However, not all parts of the grid that belong together are also represented as a single (multi-) linestring, they are within the database the way they were inserted. So, I need to find out which lines touch, do not cross, and share the same voltages, and finally merge them. The result will be another, shorter list containing merged lines and those which did not need to get merged with others.

I've come up with an algorithm in C++ (Qt), which works, but is slow:

for (QHash<qlonglong, MapItem *>::iterator current = gridItems.begin();
        current != gridItems.end(); current++) {
    for (QHash<qlonglong, MapItem *>::iterator other = current;
            other != gridItems.end(); other++) {
        if (other.value() == current.value()) {
            continue;
        }

        const OGRGeometry *firstGeom = current.value()->geometry();
        const OGRGeometry *itGeom = other.value()->geometry();

        if (current.value()->tag("voltages") == other.value()->tag("voltages")
                && firstGeom->Touches(itGeom)
                && !firstGeom->Crosses(itGeom)) {

            // Merge:

            MapItem *mergedItem = new MapItem(firstGeom->Union(itGeom));
            mergedItem->tags(current.value()->tags());

            *current    = mergedItem;
            *other      = mergedItem;
        }
    }
}

Basically, it does the following: Given a list of pointers to geometries, it creates two iterators within two loops. The second iterator always starts as a copy of the first; then both travel until the end of the list. If the geometries the two pointers point to touch, but do not cross (and also share some tags), they are united.

To illustrate what it does, I've drawn a very simple picture featuring five line strings which could be a possible result of my example query outlined above. In this picture, only the three grey ones are merged:

LineMerger: The grey line strings are merged, the blue ones not.

I now want to improve this approach by (a) possibly improving the algorithm and (b) putting the strain on the database server, not the slower client machine.

I've two options here, but I do not know which one is the best or which actually works:

  1. Create a SQL query which does this. However, I do not know how. (Self-join? Aggregates?) If someone could suggest a query that does this, I'd be absolutely happy.
  2. Create a PostgreSQL C extension that implements my algorithm. If so, I'm happy for any suggestions of how to improve the algorithm or improve it by enabling parallel processing.
Related Question