Smathermather's Weblog

What is the center line of a complex polygon?

Posted by smathermather on September 16, 2011

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.

1. Andrea Aimesaid

I believe that you can write a filter function and then use geometry transformations to turn the polygon into a line, and then label it as such. However not sure how much geoscript can be plugged into GeoServer today.

2. smathermathersaid

So, while I could set this up as WPS, you’re not sure I could apply this to labeling?

3. Andrea Aimesaid

Yep, I would not know, not much of a script person myself. But the only plugin point you have to do that is “geometry transformations”, you need to be able to create a new filter function with scripting

4. smathermathersaid

I have resigned myself to finally learning Java. Just need to figure out when… . ðŸ™‚

5. What is the center line of a complex polygon? (cont.) « Smathermather's Weblogsaid

[…] we try to extract the centerline of a polygon using Voronoi polygons, like in my previous post, it works pretty well for hydrologic cases, like extracting a stream centerline from stream banks, […]

6. What is the center line of a complex polygon? (cont. again!) « Smathermather's Weblogsaid

[…] previous post […]

7. What is the center line of a complex polygon? New approach. « Smathermather's Weblogsaid

[…] previous post […]

8. Joesaid

Nicely done, I had the same solution for calculating a center path for bird observers traveling up Tomales Bay and it was such a rare task I never thought of it again, I like this. Extracting the line is tricky.