joshuaclayton/polylines — pull request #2 by joshuacronemeyer (2012-11-14 11:13:09+00:00)
Title: Fix rounding errors due to calculating deltas before e5 conversion

Hey, I'm using your gem on a project where I have some really long paths. I was noticing that over long distances the paths were drifting away from the actual coordinates they were at. Have a look at this screenshot. Polyline not matching up with a marker that should be on it. https://twitter.com/cuberick/status/268654967051661312/photo/1 I started investigating and noticed that your gem was getting different results from the official google implementation: https://developers.google.com/maps/documentation/utilities/polylineutility I think I tracked down the reason you had a different result. In the algorithm description Google isn't very explicit about when they calculate the deltas but you can infer from the table on the page that they calculate the deltas after they've already done the e5 rounding. Your algorithm was calculating deltas then doing e5 rounding. My pull request supplies a test case that will fail unless you do the rounding before calculating the delta. And I've supplied a fix. I'm not totally happy with the fix becuase it rounds, unrounds and rounds again, but it was a low risk fix. I considered a few other types of fixes but they were either drastic or worse. Let me know if you have a particular suggestion for a fix you'd like to see.

If you'd like to see what's happening with the rounding before and after the fix here is a puts statement with values based on the test I supplied. Here is the array of first point plus deltas with the old code

[39.13594499, -94.4243478, -0.00035742000000027474, 7.000000010748408e-07]"

Here is the array with the new code

[3913594, -9442435, -35, 0]"

Notice that the 3rd value (a delta) has been rounded to -35. With the old code -0.00035742000000027474 gets rounded to -36 in step_2. After I fixed this problem here is the new screenshot: https://twitter.com/cuberick/status/268655159280820224/photo/1