# Algorithm to move polygon nodes when simplifying

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

• Can you explain why "Manual" is the right answer for your problem? For example, why doesn't the "bend" on the lowest line start higher and end more to the right (so it bisects the last five or six line segments)? Commented Feb 12, 2014 at 9:58
• @BradHards You are right, the "Manual" result is not optimal, but here I only moved the "node" point. I have other problems away from the node points, but I first want to solve this one because I expect that it will affect the results of the entire line. Please also note that the simplification is affected by the rest of the line (which is not shown here). I've updated the figure for more clarity. Commented Feb 12, 2014 at 10:33
• Your "manual" solutions look incorrect to me. You have converted a raster that represents polygons, so the purple features must be their mutual boundaries. If that is so, then the node where three polygons come together is as accurate as it possibly can be and ought to remain fixed. Both the DP and Wang algorithms respect that but the "manual" result moves that node into the interior of the top polygon. Commented Feb 12, 2014 at 20:04
• @whuber Thanks for your comment. However, I should have said that my polygons have been generated by image classification. The pixel that is identified at the corner of three parcels is not the most reliable because of "mix of reflectance". As I expect straight lines in most of the cases, not moving the ends creates some artefacts. In other words, I do not question the accuracy of this point, but its precision. Commented Feb 13, 2014 at 6:41

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 !

• Merci. I will have a look at those. However, what I really want is moving the nodes. I am afraid that I will need to do this before the simplification process, otherwise the result will either not move the node, or move the ends of each nodes apart which will force me to rebuild the topology (and... move the nodes) Commented Feb 13, 2014 at 6:47