You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Thomas Neidhart (Created) (JIRA)" <ji...@apache.org> on 2012/02/18 19:46:00 UTC
[jira] [Created] (MATH-749) Convex Hull algorithm
Convex Hull algorithm
---------------------
Key: MATH-749
URL: https://issues.apache.org/jira/browse/MATH-749
Project: Commons Math
Issue Type: New Feature
Reporter: Thomas Neidhart
Fix For: 3.1
It would be nice to have an implementation of Graham's scan algorithm to compute the convex hull of a set of points in a plane.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-749) Convex Hull algorithm
Posted by "Thomas Neidhart (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-749?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Thomas Neidhart updated MATH-749:
---------------------------------
Priority: Minor (was: Major)
> Convex Hull algorithm
> ---------------------
>
> Key: MATH-749
> URL: https://issues.apache.org/jira/browse/MATH-749
> Project: Commons Math
> Issue Type: New Feature
> Reporter: Thomas Neidhart
> Priority: Minor
> Labels: 2d, geometric
> Fix For: 3.1
>
>
> It would be nice to have an implementation of Graham's scan algorithm to compute the convex hull of a set of points in a plane.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-749) Convex Hull algorithm
Posted by "Thomas Neidhart (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-749?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Thomas Neidhart updated MATH-749:
---------------------------------
Description:
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)
* 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, TBD.
was:It would be nice to have an implementation of Graham's scan algorithm to compute the convex hull of a set of points in a plane.
> Convex Hull algorithm
> ---------------------
>
> Key: MATH-749
> URL: https://issues.apache.org/jira/browse/MATH-749
> Project: Commons Math
> Issue Type: New Feature
> Reporter: Thomas Neidhart
> Priority: Minor
> Labels: 2d, geometric
> Fix For: 3.1
>
>
> 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)
> * 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, TBD.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-749) Convex Hull algorithm
Posted by "Thomas Neidhart (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-749?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Thomas Neidhart updated MATH-749:
---------------------------------
Issue Type: Sub-task (was: New Feature)
Parent: MATH-751
> 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
> Priority: Minor
> Labels: 2d, geometric
> Fix For: 3.1
>
>
> 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 is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-749) Convex Hull algorithm
Posted by "Thomas Neidhart (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-749?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Thomas Neidhart updated MATH-749:
---------------------------------
Description:
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.
was:
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)
* 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, TBD.
> Convex Hull algorithm
> ---------------------
>
> Key: MATH-749
> URL: https://issues.apache.org/jira/browse/MATH-749
> Project: Commons Math
> Issue Type: New Feature
> Reporter: Thomas Neidhart
> Priority: Minor
> Labels: 2d, geometric
> Fix For: 3.1
>
>
> 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 is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-749) Convex Hull algorithm
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-749?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Thomas Neidhart updated MATH-749:
---------------------------------
Fix Version/s: (was: 3.1)
3.2
> 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
> Priority: Minor
> Labels: 2d, geometric
> Fix For: 3.2
>
>
> 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 is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira