The case contains points which are extremely close (below the precision of double-precision floating point). This caused the old code to fail, since it was unable to robustly compute a different distance for the close points, and thus sorted the points incorrectly. This in turn caused an incorrect result from the Graham Scan algorithm:
The fix is to use a more robust way of computing relative distance for the radial sort.
Improves the robustness of the radial sorting used by the
ConvexHullGraham scan algorithm.This fixes a failure case reported in GEOS: https://github.com/libgeos/geos/issues/722.
The case is
The case contains points which are extremely close (below the precision of double-precision floating point). This caused the old code to fail, since it was unable to robustly compute a different distance for the close points, and thus sorted the points incorrectly. This in turn caused an incorrect result from the Graham Scan algorithm:
The fix is to use a more robust way of computing relative distance for the radial sort.
Signed-off-by: Martin Davis mtnclimb@gmail.com