forked from georust/geo
-
Notifications
You must be signed in to change notification settings - Fork 0
Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
731: Fix polygon distance fast path r=frewsxcv a=urschrei This replaces the previous, buggy iteration logic: we now rely upon the fact that this is a linear algorithm (thank you for the inspiration for the fix `@msalib)` so the minimum distance can be calculated by spinning the calipers at most n times, where n is the <s>number of edges in the larger of the two polygons</s> total number of vertices in both polygons' exteriors. Other improvements include re-calculating the slope according to the same logic in the original algorithm, fixing a branching difference in our port, and new tests that cover both the original and minimised errors that were found. # THAT HAVING BEEN SAID: This algorithm's implementation is **extremely** magical and if it were proposed for addition today I would be dubious about its inclusion: why does the `100.00` value work in various functions, but `float::max_value()` doesn't? Why is the epsilon (`0.002`) comparatively large, and why does substituting `float::min_value()` not work? Nobody knows. - [x] I agree to follow the project's [code of conduct](https://github.com/georust/geo/blob/master/CODE_OF_CONDUCT.md). - [ ] I added an entry to `CHANGES.md` if knowledge of this change could be valuable to users. --- Co-authored-by: Stephan Hügel <shugel@tcd.ie>
- Loading branch information
Showing
2 changed files
with
68 additions
and
22 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters