Monday, November 22, 2010

Removing Complexities

My co-worker Alyssa Wright just asked me an interesting question: Vancouver Island is a pretty crinkley island, how would we simplify it to remove the crinkley bits?

Original Island

Notice the big fjords and other fine work by Slartibartfast. ST_Simplify will not do what we need, since it removes redundant vertices within a tolerance. So the fjords will have fewer vertices, but they'll still be there.

However, it turns out there is a solution, and I didn't even need a long walk in the snow to figure it out. If we buffer by a large amount, then reverse the buffer by the same amount, we'll get something that has a similar shape to the original, but without the crinkly bits.

Buffered by 4km

Buffer out, and the crinkley bits get melted away. But now the island is too big. So buffer inwards.

Negative Buffer by 4km

And now we have something we can use. We could now even run ST_Simplify on this result to drop some unneeded vertices and make it smaller yet.

Simple Island

Looking closer, you can see how we have melted away all the crinkley bits while still following the original (mostly). Note that the new shape is still a strict superset of the original.

Saanich Peninsula


Bernie said...

I really like the simplicity of this solution and it uses tools that are readily available in most GIS software.

mpg said...

FYI, this is known as erosion and dilation -- pretty standard morphology operations in image processing to reduce noise (well, technically not noise - rather, to make the image look like something more canonical, e.g. for OCR work).


Warren J. Medernach, GISP said...

So simple, yet so effective!
Thanks Paul.


Marko Tiikkaja said...

Awesome trick! Thanks for sharing! :-)

ells bells said...

Goodbye Saanich Peninsula! Nice knowing you.

I used Mapshaper for generalizing the BC coast a few days ago:

alvherre said...

I thought Slartibartfast only did Norway. Am I mistaken?


Benjamin Supnik said...


Could you comment on the time complexity differences between a pair of buffer operations vs. a "topology preserving" simplification? Both are relatively expensive operations for polygons with large numbers of segments...


Hugh said...

Apparently I'm the second commenter that specifically needed to simplify Vancouver Island. Thanks for the tip, and for your choice of examples.

Paul Ramsey said...

@Benjamin. "TopologyPreservingSimplification" and this approach are apples and oranges. The former will weed vertices and avoid cases that cause invalidity (ring crossings, hole collapse), and it won't do things like remove the Saanich Inlet, only make it very very simple (like a V). The dilation/erosion actually removes features (inlets, lakes, etc) and smooths lines. The cost is almost certainly higher for the dilation/erosion method.

Arianna Granziera said...

It is a great approach, thanks for sharing. Do you have any ideas on how to do this when you are dealing with more than one polygon? For example, drainage basins each with its own ID (which I need to preserve)?

About Me

My Photo
Victoria, British Columbia, Canada

Blog Archive


bc (43) it (33) postgis (23) video (13) enterprise IT (11) icm (11) gis (9) sprint (9) open source (8) osgeo (8) enterprise (7) foi (7) cio (6) foippa (6) foss4g (6) management (6) spatial it (6) outsourcing (5) politics (5) mapserver (4) bcesis (3) boundless (3) opengeo (3) oracle (3) rant (3) COTS (2) architecture (2) deloitte (2) email (2) esri (2) hp (2) idm (2) javascript (2) natural resources (2) ogc (2) open data (2) openstudent (2) postgresql (2) technology (2) vendor (2) web (2) 1.4.0 (1) HR (1) access to information (1) accounting (1) agile (1) aspen (1) bcpoli (1) benchmark (1) buffer (1) build vs buy (1) business (1) business process (1) c (1) career (1) cartodb (1) cathedral (1) client (1) cloud (1) code (1) common sense (1) consulting (1) contracting (1) core review (1) crm (1) crockofshit (1) cunit (1) custom (1) data science (1) data warehouse (1) design (1) development (1) digital (1) environment (1) essentials (1) evil (1) exadata (1) fcuk (1) fgdb (1) fme (1) foocamp (1) foss4g2007 (1) ftp (1) gdal (1) gds (1) geocortex (1) geometry (1) geoserver (1) geotiff (1) google (1) google earth (1) government (1) grass (1) hadoop (1) iaas (1) icio (1) imagery (1) industry (1) innovation (1) integrated case management (1) introversion (1) iso (1) isss (1) isvalid (1) jpeg (1) jts (1) lawyers (1) mapping (1) mcfd (1) media (1) microsoft (1) money (1) mysql (1) new it (1) nosql (1) nrs transformation (1) oipc (1) opengis (1) openlayers (1) oss (1) paas (1) pirates (1) policy (1) portal (1) proprietary software (1) public accounts (1) qgis (1) r (1) rdbms (1) recursion (1) redistribution (1) regression (1) rfc (1) right to information (1) saas (1) salesforce (1) sardonic (1) scandal (1) seibel (1) sermon (1) server (1) siebel (1) snark (1) spatial (1) standards (1) statistics (1) svr (1) taxi (1) tempest (1) texas (1) tired (1) transit (1) tripledelete (1) twitter (1) uber (1) udig (1) uk (1) uk gds (1) verbal culture (1) victoria (1) waterfall (1) wfs (1) where (1) with recursive (1) wkb (1)