25

What are the recommended ways of simplifying geometries? Keeping in mind projections, and simplifying state geometries, for example.

I've heard about converting to an 'equi-distant' projection that allows simplification without distortion, and then converting back to your chosen projection.

Kadir Şahbaz
  • 76,800
  • 56
  • 247
  • 389
John Weldon
  • 653
  • 1
  • 7
  • 14

5 Answers5

13

As glennon mentioned, the standard algorithm for doing this is Douglas-Peucker, which is the default algorithm used in software such as PostGIS (i.e. GEOS) via St_Simplify, ArcGIS via Generalize and GRASS via v.generalize. The Wikipedia article also links to a Python implementation.

GRASS supports a number of different algorithms, as explained in the help page for v.generalize.

On the projection issue, I think in this case its a red herring which can be ignored. The only issue which comes to mind is potentially densifying lines to prevent them from being oversimplified.

scw
  • 16,391
  • 6
  • 64
  • 101
6

You might investigage the Douglas–Peucker algorithm--a method for reducing the number of points in a curve approximated by a series of points. See: http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

Whether you overwrite your original geometry or create a secondary store will vary by use.

glennon
  • 2,080
  • 18
  • 21
4

If by "simplification", you mean a simple reduction of point number, use a basic filtering algorithm, like Douglass peucker filter such as provided by mapshaper or ArcGIS generalize.

If you are looking for a more advanced generalisation tools, which deals for example with the enlargement of two small islands, amalgamation of land patches, etc., have a look at RegionSimplify. Here is an example of output:

simplification generalisation boundaries

julien
  • 10,186
  • 6
  • 55
  • 93
  • the sites http://aci.ign.fr are not accessible. Do you know where we can find examples the "advanced generalisation algorithm" that you are mentioning ? – radouxju Dec 22 '13 at 19:55
  • The url has changed, check: http://generalisation.icaci.org/ – julien Dec 23 '13 at 11:20
3

If you're simplifying the geometry due to limitations in computer processing power, you may want to consider generating mipmaps with associated alpha masks for each geometry at various levels.

Jon Bringhurst
  • 499
  • 5
  • 11
  • Very interesting, would you be willing to elaborate? – John Weldon Jul 22 '10 at 20:39
  • Well, to do this you would need to rasterize each vector geometry into a bitmap for each level that you allow users to zoom in and out to on the map. Then, instead of drawing the vector geometry for each level over and over, you would just render the bitmap instead. So, the calculation for rasterizing the geometry (which is expensive if you have a ton of vertices) is done up front instead of each time the user performs an action. The alpha mask comes into the picture when you draw the bitmap -- it's used so only the shape itself is drawn. – Jon Bringhurst Jul 22 '10 at 22:49
2

This is hard topic, since you must take into account some sort of resolution of your dataset. When is a geometry vertex equal to another vertex? I never heard of converting and re-converting, although it would be an interesting test.

Simple geometries, are according to OGC, geometries that do not self-intersect, and in case of polygons, geometries that are correctly oriented, for outer shell(s) and inner shell(s) and subsequently.

George Silva
  • 6,298
  • 3
  • 36
  • 71