one additional example:
Posted by smathermather on August 10, 2012
one additional example:
Posted by smathermather on August 9, 2012
Continuing my posts on the centerline of a complex polygon (you can work your way backward from here), here’s it’s application to a riverine system (legend: light blue river, black centerline derived from routing through the skeleton of voronoi polygons from a densified stream bank set + the skipped skeleton bits in pink– read through the series if you if you don’t grok that explaination):
Posted by smathermather on August 2, 2012
I’ve had a series of posts (including this one) on finding the center line of a complex polygon– especially with an interest in finding the center line of streams and river bodies. We have to give credit to my colleague Tom Kraft for solving the polygon centerline problem. Tom struck upon the very elegant solution– derive the medial axis, and then use a few end points to route between to extract just the important features. It’s not fully automated, but the amount of user input is so nominal as to be as close to automatic as I care about. So far, we have this implemented in a mix of ArcGIS and PostGIS, but I can easily picture a pretty simple web interface with a PostGIS back end for extracting the centerlines of polygons in a nominally interactive way. As a teaser, a non-stream example:
Posted by smathermather on January 17, 2012
Today, I just show pictures of my process for filtering the medial axis of extraneous elements. I’ll let the pics tell the story for now:
Posted by smathermather on January 14, 2012
I didn’t remember that I had 4 previous post on this topic, but I’ve gotten a little obsessed with this problem– how to (with relatively little computational cost) kind the centerline of complex polygons, so we can extract flow lines from streams, label long complex polygons, easily generate the centerline parcel boundary line for river bound parcels, etc.. FYI, here are my 4 previous posts on this topic:
I’ll confess, I became somewhat enamored of the scale axis transform as a method for tackling this problem. In short, the scale axis transform identifies the medial axis of the polygon using Amenta and Kolluri’s finite union of balls to identify the initial centerline of the polygon, and then tries to fix the deficiencies in the robustness of the medial axis.
The problem, of course, is the degree to which bumps in the shape result in extra little lines hanging off our medial axis. This does not represent an intuitive medial axis. This is not what we would (in this case) call the centerline of the stream.
The scale axis transform suggests expanding these balls by a multiplicative factor, and deriving the new axis from that scaled version:
This step can easily be done in PostGIS once you have the medial axis:
CREATE TABLE rr_expand_r3_12 AS SELECT ST_Buffer(b.the_geom, ST_Distance(b.the_geom, ST_Union(a.the_geom)) * 1.2 ) FROM medial_axis b, polyline a GROUP BY <a href="http://a.id/" target="_blank">a.id</a>, b.the_geom ;
I will play a bit more with this, but the initial results I got around areas with islands (torus like topology) were disappointing. Also, at least as I have this implemented in PostGIS, this is a computationally intensive process. I think though that I have a good (enough) alternative, which will be the topic of my next post.
Posted by smathermather on October 18, 2011
Just a quick post on this one, this time. I haven’t implemented an approximation of Bálint Miklós‘ Scale Axis Transform in PostGIS yet, and I don’t think I’ll dare try in GeoTools for GeoServer just yet, but I thought I’d give a preview of the sensitivity of the medial axis calculations in “bumpy” streams with the following image:
As you can see, the problem isn’t restricted to giraffes… 🙂 .
Posted by smathermather on October 8, 2011
I glossed over the difficulties of finding the centerline of a complex polygon in the last couple of posts, and didn’t realize the disservice until we got to the nitty-gritty of finding the centerline of “bumpy” streams, for which our solution, which is arguably a discretized version of the traditional medial axis, is quite sensitive to noise and “bumpiness”.
With a little more googling, my collegue T. Kraft found Bálint Miklós site describing The Scale Axis Transform, an alternate technique that is not sensitive to noise, but looks at the importance factor of a feature to control whether we show an axis for it, e.g.:
Notice how many “extra” lines we have in the initial medial axis? The scale axis transform really helps in trimming these out. There are some really well done videos describing this process conceptually for both the 2D case and the 3D case.
We’ll see if we can implement an approximation of this technique in PostGIS.
Posted by smathermather on September 26, 2011
If 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, e.g.:
We’ll use this to extract flow lines, in order to build out a better hydrologic network, but also use it to update property boundaries based on deed descriptions which may alternately follow distances and bearings, or banks and centerlines of streams and rivers.
But, I was still curious to see how well it does on smaller polygons, e.g. does it help with labeling of parcel polygons:
Not perfect, but not bad. Looks like developing a special case for equilateral triangle, circular, and square shaped polygons (etc) might be in order, as these are probably best labeled in a more simple fashion (see northeast corner of this map, parcel 48517140)… .
Posted by smathermather on February 4, 2011
I promised pics from our labeled parcels:
Posted by smathermather on February 1, 2011
We have a guest blogger today– Ramon, a bright and hard-working intern I’ve had the pleasure of working with for over a year. If you’re looking for someone versed in Postgre/PostGIS/GeoServer/OpenLayers, Ramon’s been my rock as we’ve been building our internal system, doing everything from basic grunt work to esoteric trouble-shooting. I’m trying hard not to fall on my face now that he’s moved on.
We wanted to take advantage of the advance labeling of Maplex for parcels in GeoServer. GeoServer SLDs don’t yet (I think) have automatic rotation for best fit for polygons, but Maplex (an ESRI label extension that’s rolled in with the ArcINFO license in ArcGIS desktop) does. Here’s how we took advantage of that:
The general procedure to generate the attribute table is as follows: (Note: It is best to do this in sections because in the limitations of labels that could be generated per annotation feature)
1) Generate the labels using Maplex as the label engine in Arcmap.
2) Convert the labels into annotation (in a database)
3) Join the annotation table back to the original polygon that needs labeled.
4) Export the dataset to create a new shapefile with the combined attribute table of the original shapefile and “annotation feature”
5) Import the shapefile to PostgreSQL
Notes: I added the following fields to the shapefie before importing it to PostgreSQL
a) acreage – area of the parcel in acres
b) res_prop – “Y” if parcel is within 1500 ft of our area of interest, otherwise “N”
c) ang – small integer conversion of the “Angle” value generated by Maplex (this may be scrapped from the workflow in the future)
d) Rot_Ang – the rotation angle in terms of Geoserver convention.
– calculated as “zero” minus “ang” (see the UPDATE SQL below)
e.g. UPDATE base.parcel_annotations_med SET rot_ang = 0 – ang;
This final step step converts annotation rotation values, which are rotated from horizontal up to 90 degrees either in a positive or negative to GeoServer label rotation convention, which run the full arc of a circle.
We’ll have a post that follows with the final SLD, and screen shot of the great labeling effect. Stay posted.