What is the center line of a complex polygon?

Sat in on a great presentation yesterday by Tim Schaub and Justin Deoliveira on GeoScript. Definitely check out their tutorials. To practice what I learned, I thought I’d apply it to the problem of how to find the centerline of a polygon.

What do I mean by the centerline of a polygon? Well in the case of a stream that is drawn with both it’s banks, the centerline of a polygon is the effective flowline. Also, if you want to label such polygons, it would be useful to be able to calculate this. This could apply to road polygons as well, or labeling complex parcels, etc. etc. At first (and second) blush, there is no trivial solution. However, there are some excellent approximations.

There are some nice articles online about the derivation of centerlines from polygonized roads, e.g. this one. The basic approach is to densify the lines (if necessary), and run a Thiessen (Voronoi) algorithm, then grab the middle line from those polygons. So, let’s start this process, and take it through at least to deriving the Voronoi result using python/GeoScript:

First our stream line:

>>> from geoscript.geom import *
>>> from geoscript.style import *
>>> from geoscript.render import *
>>> poly = Polygon([(2130394.00006841,633268.4901058), ...
,(2130394.00006841,633268.4901058)])

Then to view it quickly:

>>> draw(poly, format='mapwindow')

Maybe fly with a little style:

>>> style = Stroke('blue', width=1) + Fill('#0000ff', opacity=1)
>>> draw(poly, style, format='mapwindow')

Ok, now that’s a complicated enough polygon. What do we get from calculating a Voronoi diagram against it?:

>>> polyv=voronoi(poly)
>>> draw([polyv, poly], format='mapwindow')

See the centerline running through the stream? It’s not perfect, but apply some densification before we calculate the polygons, then select only that centerline, and Bob’s your uncle, you have a very nice stream centerline for flowline calculations, labeling, what have you. In future steps, I’ll set this up to extract that line as well, and perhaps host it as a WPS service on GeoServer. If I can (I’m not sure the limitations to GeoScript, have to bug the GeoScript guys today…), I’ll also use it to extend the labeling capabilities for my GeoServer instance without having to dig deep into Java development. Ah, I do love a good API.

Advertisement