commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Thomas Neidhart (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (MATH-749) Convex Hull algorithm
Date Fri, 08 Nov 2013 16:23:17 GMT

    [ https://issues.apache.org/jira/browse/MATH-749?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13817403#comment-13817403
] 

Thomas Neidhart commented on MATH-749:
--------------------------------------

I have a patch for this ready, but still wonder where to put the implementations:

 * directly in geometry.euclidean.twod.GrahamScan2D
 * make a subpackage for each space, e.g. g.e.twod.hull.GrahamScan2D
 * make a subpackage for geometry, e.g. g.hull.GrahamScan2D

Any ideas?

> 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
>
> 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#6144)

Mime
View raw message