[BUG] ConvexHull Hashset loss of order #6605
Description
Description
Problem Statement:
The original ConvexHull code uses a HashSet to collect hull points in the recursive method. While this correctly computes which points belong to the convex hull, it does not preserve any order of the points. Many downstream geometric algorithms, such as Rotating Calipers, require the points of the convex hull to be in counter-clockwise (CCW) order around the polygon. Feeding an unordered hull into such algorithms leads to incorrect results, e.g., incorrect minimum bounding rectangle areas or diameters.
Impact:
Algorithms like Rotating Calipers fail or return wrong values.
Tests that check for specific point ordering fail (ConvexHullTest, RotatingCalipersTest).
Geometric computations relying on consistent traversal around the hull cannot be trusted.
Solution:
Preserve the hull points in a list in CCW order.
Start from a well-defined point, e.g., the bottom-most, left-most point, to make results deterministic.
Remove duplicate points caused by set usage.
I’ve identified the issue with ConvexHull returning unordered points, which breaks downstream algorithms like Rotating Calipers. I’ve prepared a fix that preserves counter-clockwise order. Could I be assigned to submit a PR for this?
Steps to reproduce
Use the original ConvexHull.convexHullRecursive(List) method on a set of points that form a convex polygon, for example:
List points = Arrays.asList(
new Point(0, 3),
new Point(2, 2),
new Point(1, 1),
new Point(2, 1),
new Point(3, 0),
new Point(0, 0),
new Point(3, 3),
new Point(2, -1),
new Point(2, -4),
new Point(1, -3)
);
List hull = ConvexHull.convexHullRecursive(points);
Print or inspect hull. You will notice the points are unordered (not CCW).
Pass this hull to an algorithm that relies on ordered vertices, e.g., RotatingCalipers.minBoundingRectangle(hull):
double area = RotatingCalipers.minBoundingRectangle(hull);
Observe that the returned area is incorrect (e.g., for a diamond shape it returns 1.9999… instead of 4.0).
Excepted behavior
convexHullRecursive should return points in CCW order.
Downstream algorithms like Rotating Calipers should produce correct geometric results.
Screenshots
No response
Additional context
No response