Mailing-List: contact issues-help@commons.apache.org; run by ezmlm
Precedence: bulk
Reply-To: issues@commons.apache.org
Date: Wed, 12 Feb 2014 23:00:25 +0000 (UTC)
From: "Thomas Neidhart (JIRA)" <jira@apache.org>
To: issues@commons.apache.org
Message-ID: <JIRA.12543165.1329590683452.33597.1392246025906@arcas>
In-Reply-To: <JIRA.12543165.1329590683452@arcas>
References: <JIRA.12543165.1329590683452@arcas>
Subject: [jira] [Reopened] (MATH-749) Convex Hull algorithm
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


     [ https://issues.apache.org/jira/browse/MATH-749?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Thomas Neidhart reopened MATH-749:
----------------------------------


Discovered problems with collinear points when testing the graphical test program. GiftWrap and GrahamScan make problems when there are multiple points e.g. with the smallest x-coordinate.

> Convex Hull algorithm
> ---------------------
>
>                 Key: MATH-749
>                 URL: https://issues.apache.org/jira/browse/MATH-749
>             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 [http://en.wikipedia.org/wiki/Convex_hull_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
(v6.1.5#6160)