commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Thomas Neidhart (JIRA)" <>
Subject [jira] [Resolved] (MATH-749) Convex Hull algorithm
Date Sun, 16 Feb 2014 12:24:19 GMT


Thomas Neidhart resolved MATH-749.

    Resolution: Fixed

In r1568752 I did the following changes:

 * removed GrahamScan and GiftWrap as they are not robust wrt collinear points
 * add ConvergenceException in case the convex hull generator can not find a convex hull with
the given tolerance value
 * ConvexHull2D ctor is public now and throws an IllegalArgumentException if the provided
vertices do not form a convex hull
 * Improved robustness of MonotoneChain wrt collinear points
 * Improved GeometryExample in userguide examples

I am now confident that the MonotoneChain algorithm is really robust for all kinds of input.

> Convex Hull algorithm
> ---------------------
>                 Key: MATH-749
>                 URL:
>             Project: Commons Math
>          Issue Type: Sub-task
>            Reporter: Thomas Neidhart
>            Assignee: Thomas Neidhart
>            Priority: Minor
>              Labels: 2d, geometric
>             Fix For: 3.3
>         Attachments: MATH-749.tar.gz
> It would be nice to have convex hull implementations for 2D/3D space. There are several
known algorithms []:
>  * Graham scan: O(n log n)
>  * Incremental: O(n log n)
>  * Divide and Conquer: O(n log n)
>  * Kirkpatrick-Seidel: O(n log h)
>  * Chan: O(n log h)
> The preference would be on an algorithm that is easily extensible for higher dimensions,
so *Incremental* and *Divide and Conquer* would be prefered.

This message was sent by Atlassian JIRA

View raw message