Skip to content

Polygon2D convex hull winding direction is reversed and ignored for triangles #248

Description

@JayLeo04

Description

Polygon2D.GetConvexHullFromPoints documents clockWise: true as clockwise and false as counter-clockwise, but the current implementation returns the opposite winding for hulls with more than three input points. With exactly three points, the method returns the input order directly, so clockWise has no effect at all.

Reproduction

var square = new[]
{
    new Point2D(0, 0),
    new Point2D(4, 0),
    new Point2D(4, 3),
    new Point2D(0, 3),
    new Point2D(2, 1)
};

var clockwise = Polygon2D.GetConvexHullFromPoints(square, true);
var counterClockwise = Polygon2D.GetConvexHullFromPoints(square, false);

Using the usual shoelace signed-area convention in the XY plane, the current clockwise result has positive area (counter-clockwise), while counterClockwise has negative area (clockwise). The default call behaves like explicit true, so its result is also counter-clockwise.

The same contract is not honored for the smallest accepted input:

var triangle = new[]
{
    new Point2D(0, 0),
    new Point2D(1, 0),
    new Point2D(0, 1)
};

var clockwise = Polygon2D.GetConvexHullFromPoints(triangle, true);
var counterClockwise = Polygon2D.GetConvexHullFromPoints(triangle, false);

Both calls currently preserve the counter-clockwise input order.

Cause

The final ordering measures the signed angle from each centroid-to-vertex vector to the x-axis:

centroid.VectorTo(x).SignedAngleTo(xAxis, clockWise)

Sorting those angles in ascending order produces the reverse of the requested traversal direction. The existing three-point early return bypasses this ordering altogether.

Proposed fix

  • Pass !clockWise to SignedAngleTo during the centroid-angle sort.
  • Let three-point inputs go through the same hull collection and ordering path.
  • Correct the existing SciPy-generated expectations: scipy.spatial.ConvexHull.vertices is counter-clockwise for 2-D hulls.
  • Add regression coverage for explicit clockwise/counter-clockwise direction, the default, and a triangle.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions