[GIS] Algorithm to move polygon nodes when simplifying

algorithmpolygonsimplify

I want to simplify polygons that come from a raster analysis. In order to avoid overlap and gaps, I first convert my polygons to lines. The problem is that all algorithm are then keeping the two end points, which are not necessarily at the best position. The image below illustrates my problem (it is difficult to explain by words). The "manual" case is the kind of result that I expect (of course I cannot do this manually for all features because I have far to many of them):

  • With Wang's algorithm, I have some bends around the node and it is
    away from the straight line that I would like

  • With DP algorithm, I have the straight lines but they are shifted compared with the line that I would like.

My priority is to keep a good positional accuracy (minimizing the distance from the "middle" of the line). I would like a "T"(though not necessarily right angles) like I have with DP algorithm, but at a location that would make the lines close to the "middle" of the original lines.

I prefer solutions in QGIS 2.0 or ArcGIS 10.1 (advanced) but the implementation is a bonus for me. My question is about an algorithm that would help me find the best location of the polygon nodes for "non shifted straight lines".

enter image description here

Best Answer

Look at the scw answer in Simplifying geometries (generalization)

...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...

but:

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

And the other algorithms provided by v.generalize are:

Generalization algorithm
Options: douglas,douglas_reduction,lang,reduction,reumann,boyle,sliding_averaging,distance_weighting,chaiken,hermite,snakes,network,displacement
douglas: Douglas-Peucker Algorithm
douglas_reduction: Douglas-Peucker Algorithm with reduction parameter
lang: Lang Simplification Algorithm
reduction: Vertex Reduction Algorithm eliminates points close to each other
reumann: Reumann-Witkam Algorithm
boyle: Boyle's Forward-Looking Algorithm
sliding_averaging: McMaster's Sliding Averaging Algorithm
distance_weighting: McMaster's Distance-Weighting Algorithm
chaiken: Chaiken's Algorithm
hermite: Interpolation by Cubic Hermite Splines
snakes: Snakes method for line smoothing
network: Network generalization
displacement: Displacement of lines close to each other

If you don't want to use GRASS GIS, you can use v.generalize directly in QGIS (via the Processing Toolbox).

Good luck to try them !

Related Question