systemed/iD — pull request #1831 by paulmach (2013-09-22 04:54:15+00:00)
Title: Better orthogonalization of skinny quads. Fixes #1812

This pull request is meant to fix https://github.com/systemed/iD/issues/1812

The orthogonalizer works by refining the polygon, at each step making the corners more right or straight. The bug was caused by a big step size overshooting the first/best local minimum. I made two changes to address this:

1. Removed the last duplicate node in the way. This actually messed up the algorithm, for the origin node it was computing angles between node ids 0,0,1 This change fixes the first testcase.

2. The other change is to reduce the step size. I wanted to reduce it but still keep some information about the local geometry so we don't over work. I made the 'scale' 2x the minimum length of the 2 side incident the point vs. the sum of the two sides. This lowers it for all cases, some more than others, but gives it a reasonable bound.

Impact? Lowering the step size will cause the code to run ever so slightly slower, but the result will not change.

Since this code is based off of P2, what did P2 do in this case? Nothing, with the bad step size, the refinement initially gets worse before it gets better, so it just quit. P2 will quit if the refinement didn't improve things. In iD the code continues for 1000 iterations or until the error is < 1e-8

For testing, see the ways in the issue:
* http://www.openstreetmap.org/browse/way/236759157
* http://www.openstreetmap.org/browse/way/237927962