fix: Apply correction to distanceToLine() measurements

[barbeau]

Please do not merge - work-in-progress

This is an implementation of a fix mentioned in https://github.com/googlemaps/android-maps-utils/issues/720#issuecomment-631263199 for a bug in the distance from a point to a line segment measurement.

TODO:

• [x] Implement correction
• [ ] Additional unit tests to assess and document level of accuracy at different distances (see below)
  • Implement assertions of distance measurements between a point and a line segment at several orders of magnitude (e.g., 1, 10, 100, 1000, ... 1000000 meters) and at different latitude values (e.g., 0, 30, 60, 80) to assess the difference in distance accuracy as the distance and latitude change
  • All measurements used in unit tests should be between a point and a line segment (not the distance from a point to the line extending beyond the provided line end points) on the WGS84 ellipsoid (not straight lines on a projected flat surface). This can be calculated using tools like QGIS and ArcGIS, or using a library like GeoTools (linestrings example, point to line example) or Google's S2geometry for Java (See https://s2geometry.io/about/overview for an example in C++ for measuring distance of a point to a polygon). A diagram showing the distance D that should be measured for each point is below.
  • Assertions should use the appropriate level of precision, and this precision should be documented in the Javadocs for the distanceToLine() method so developers understand the accuracy limitations of the current implementation. For example, if we only expect the algorithm to be accurate within 1 meter when measuring a distance of 10,000 meters between a line segment and point, there shouldn't be any decimal points in the delta value passed to assertEquals(). And the Javadocs should include a note about level of accuracy at this distance.

(Google Slide)

---

Before submitting your PR, there are a few things you can do to make sure it goes smoothly:

• [x] Make sure to open a GitHub issue as a bug/feature request before writing your code! That way we can discuss the change, evaluate designs, and agree on the general idea
• [x] Ensure the tests and linter pass
• [x] Code coverage does not decrease (if any source code was changed)
• [x] Appropriate docs were updated (if necessary)
• [x] Will this cause breaking changes to existing Java or Kotlin integrations? If so, ensure the commit has a BREAKING CHANGE footer so when this change is integrated a major version update is triggered. See: https://www.conventionalcommits.org/en/v1.0.0/

Fixes #720 🦕

[codecov[bot]]

Codecov Report

Merging #767 (8dc0887) into main (217f316) will increase coverage by 0.01%. The diff coverage is 100.00%.

@@            Coverage Diff             @@
##             main     #767      +/-   ##
==========================================
+ Coverage   39.09%   39.10%   +0.01%     
==========================================
  Files          71       71              
  Lines        4088     4089       +1     
  Branches      609      609              
==========================================
+ Hits         1598     1599       +1     
  Misses       2387     2387              
  Partials      103      103              

Impacted Files	Coverage Δ
...rc/main/java/com/google/maps/android/PolyUtil.java	93.97% <100.00%> (+0.02%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 217f316...8dc0887. Read the comment docs.

[alexaguilar89]

help me

[alexaguilar89]

help

[kikoso]

Hi @barbeau .

Can this PR be revived? I have been checking it and seems that solves the original problem.

What would it need, further test coverage?

[barbeau]

Hey @kikoso! Yes, I'd love to see this get merged. See the unchecked checkbox in the original comment - I was hoping to add test coverage to confirm this fixed the issue and prevent it from getting broken again in the future. I don't currently have the bandwidth to work on this, but if you'd like to pick it up feel free.

[kikoso]

Hi @barbeau .

I have added a few tests reflecting different latitudes and magnitudes. I have also added a case for a segment in a different hemisphere than the point, since this is an interesting edge case. Distances have been verified using QGIS

Regarding the accuracy: I can't find too much about how accurate the algorithm is, or what is the accuracy expected. Do we need to document this in the distanceToLine() function, since it is an algorithm-specific issue? Do you have any pointers on where can I find more information about its accuracy?

Thanks.

[barbeau]

I have added a few tests reflecting different latitudes and magnitudes. I have also added a case for a segment in a different hemisphere than the point, since this is an interesting edge case. Distances have been verified using QGIS

Thanks for this!! 💯

Regarding the accuracy: I can't find too much about how accurate the algorithm is, or what is the accuracy expected.

In the interest of getting this actually merged, I think as long as you've manually verified the measurements in QGIS that should be sufficient. IIRC the original thought was to include sufficient precision in the unit tests that someone could confirm it was accurate to X decimal places. To make sure future maintainers know this, can you please add a comment above those unit tests indicating they they were manually verified in QGIS?

Other than that, IMHO this should be good to merge now, although I'd welcome reviews by others.

[barbeau]

For future reference, when I was originally looking at this the point-to-line algorithm seemed to be http://paulbourke.net/geometry/pointlineplane/ or http://geomalgorithms.com/a02-_lines.html (the algorithm implementation pre-dates me). I added a comment for this in the code.

[kikoso]

@barbeau , that makes sense. I have added some comments providing a background introduction to this topic. Let me know what you think. Thanks!

[barbeau]

LGTM, thanks!

[kikoso]

@wangela, feel free to take a last look.

[googlemaps-bot]

:tada: This PR is included in version 2.4.1 :tada:

The release is available on:

• v2.4.1
• GitHub release

Your semantic-release bot :package::rocket: