search

peterstace / simplefeatures

Simple Features is a pure Go Implementation of the OpenGIS Simple Feature Access Specification
MIT License
133 stars 19 forks source link

Reimplement convex hull using Monotone Chain Algorithm #246

Closed peterstace closed 3 years ago

peterstace commented 4 years ago

Link: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

Why would we want to do that?

Monotone chain seems to be a more numerically stable algorithm compared to Graham's Scan. We've seen some problems with Graham scan in the past, e.g. https://github.com/peterstace/simplefeatures/pull/245

Monotone chain only checks 3-point orientations as it iterates through the points. The pre-sort phase sorts the points by X and then Y (rather than by 3-point orientation, which is what Graham's Scan does). This side steps problems where the 3-point orientation may disagree between various parts of the algorithm depending on argument ordering.

peterstace commented 3 years ago

Another instance of this is possibly: https://github.com/peterstace/simplefeatures/issues/356

peterstace commented 3 years ago

Closed via #357