Strk's Blog

I’ve been spending the last few days profiling and optimizing the new simple-to-topological converter you will find in PostGIS 2.0.0 thanks to a community effort.

The most expensive operation was found to be the ST_AddEdgeModFace function, which adds an edge and checks if such edge creates a new face.

Face-splitting detection was implemented using a brute force approach consisting in invoking the GEOS polygonizer and then checking if any polygon created contained the newly added edge in its boundary. It can get pretty wild when you add an edge in the universe face, and thus end up feeding the polygonizer with thousands of edges.

So I started thinking about two fields we make great effort to maintain and were (so far) unused: next_left_edge and next_right_edge. Each edge has these two pointers which may be used to walk clockwise along its left or right face.

By walking on the edge side you can know a lot about the edge you add !

First of all if you get to the other side of the edge you know for sure you didn’t split any face (no ring was created). Second, you can easily get the identifiers of all the edges you’ll need to update for setting their new left_face and right_face attributes. Finally by computing ring winding you can know whether each side of the edge is forming a fill or an hole.

I was afraid that such approach could have been slower than the brute force one, mainly due to more database querying and IO. But the dataset I was using for a testcase (Italian municipalities by ISTAT: 8094 multipolygons with an average of 560 vertices each) showed a speedup of up to 10x !

The testsuite was an invaluable tool for correctness checking. I actually spent a fair amount of time enhancing it further with new corner cases (new algorithm, new corners!).

I’m still checking correctness of  the resulting topology for the ISTAT case,  making sure that the improvements didn’t introduce any regression. Hopefully next week the code will be committed upstream for broader delectation. Stay tuned, prepare your input for conversion and start playing and timing the current routines !

PostGIS implementation of the ISO SQL/MM Topology-Geometry model is finally complete.

The SQL/MM model is just a portion of the whole topology support, but an important one, including schema definition and functions to create and populate the schema with primitive components (nodes, edges, faces).

In addition to the base model, PostGIS adds a TopoGeometry data type for use wherever you would normally use a Geometry type, except the former will be defined by references to primitive, shared, topological components.

The work on SQL/MM topology for PostGIS 2.0 was mainly funded by the Land Management department of the Tuscany Region as part of a larger project aimed at enhancing effectiveness of free software tools already in use within the institution for the management of the topographic database (chapeau!).

But more work is needed to make it easier to convert your layers to topological layers, your Geometries to TopoGeometries. Because I know you want to generalize your vectors in a topologically consistent way, don’t you ? And you want to edit the boundaries just once. And do you want to waste all that space for your triangles ?

Feature freeze for 2.0 will be by the end of November. Drop a note ASAP if you’d like to help with getting the enhanced TopoGeometry constructor shipped with it.