Details

    • Type: Sub-task Sub-task
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 3.3
    • Labels:

      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.

      1. MATH-749.tar.gz
        4 kB
        Thomas Neidhart

        Issue Links

          Activity

          Luc Maisonobe made changes -
          Status Resolved [ 5 ] Closed [ 6 ]
          Hide
          Luc Maisonobe added a comment -

          Closing all resolved issue now available in released 3.3 version.

          Show
          Luc Maisonobe added a comment - Closing all resolved issue now available in released 3.3 version.
          Thomas Neidhart made changes -
          Status Reopened [ 4 ] Resolved [ 5 ]
          Resolution Fixed [ 1 ]
          Hide
          Thomas Neidhart added a comment -

          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.

          Show
          Thomas Neidhart added a comment - 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.
          Thomas Neidhart made changes -
          Resolution Fixed [ 1 ]
          Status Resolved [ 5 ] Reopened [ 4 ]
          Hide
          Thomas Neidhart added a comment -

          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.

          Show
          Thomas Neidhart added a comment - 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.
          Thomas Neidhart made changes -
          Status Open [ 1 ] Resolved [ 5 ]
          Resolution Fixed [ 1 ]
          Hide
          Thomas Neidhart added a comment -

          Resolving for 3.3 and postpone further changes for later versions in favor of other, more pressing issues.

          Show
          Thomas Neidhart added a comment - Resolving for 3.3 and postpone further changes for later versions in favor of other, more pressing issues.
          Thomas Neidhart made changes -
          Fix Version/s 3.3 [ 12324600 ]
          Hide
          Thomas Neidhart added a comment -

          Added so far the following algorithms:

          • GrahamScan (most known)
          • MonotoneChain (good for pre-sorted points)
          • GiftWrap (used within Chan's algorithm)

          I plan to complete this issue with the implementation of Chan's algorithm which is a optimal output-sensitive algorithm with complexity of O(n log h).

          All algorithms are implemented with special care for identical and collinear points and there exist several test cases to ensure this.

          Show
          Thomas Neidhart added a comment - Added so far the following algorithms: GrahamScan (most known) MonotoneChain (good for pre-sorted points) GiftWrap (used within Chan's algorithm) I plan to complete this issue with the implementation of Chan's algorithm which is a optimal output-sensitive algorithm with complexity of O(n log h). All algorithms are implemented with special care for identical and collinear points and there exist several test cases to ensure this.
          Luc Maisonobe made changes -
          Link This issue relates to MATH-1095 [ MATH-1095 ]
          Thomas Neidhart made changes -
          Attachment MATH-749.tar.gz [ 12625289 ]
          Hide
          Thomas Neidhart added a comment -

          Attached patch containing implementation of Graham's scan method for 2D.

          Show
          Thomas Neidhart added a comment - Attached patch containing implementation of Graham's scan method for 2D.
          Hide
          Thomas Neidhart added a comment -

          Ok, but just taking this as an example and we add more geometrical algorithms (see other feature requests), they would also reside in their own subpackage, which will accumulate over time.

          I am fine with this, but wanted to make sure everybody else too.

          Show
          Thomas Neidhart added a comment - Ok, but just taking this as an example and we add more geometrical algorithms (see other feature requests), they would also reside in their own subpackage, which will accumulate over time. I am fine with this, but wanted to make sure everybody else too.
          Hide
          Gilles added a comment -

          make a subpackage for each space, e.g. g.e.twod.hull.GrahamScan2D

          +1

          Show
          Gilles added a comment - make a subpackage for each space, e.g. g.e.twod.hull.GrahamScan2D +1
          Hide
          Thomas Neidhart added a comment -

          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?

          Show
          Thomas Neidhart added a comment - 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?
          Thomas Neidhart made changes -
          Assignee Thomas Neidhart [ tn ]
          Thomas Neidhart made changes -
          Fix Version/s 3.2 [ 12322545 ]
          Thomas Neidhart made changes -
          Fix Version/s 3.2 [ 12322545 ]
          Fix Version/s 3.1 [ 12317576 ]
          Thomas Neidhart made changes -
          Parent MATH-751 [ 12543643 ]
          Issue Type New Feature [ 2 ] Sub-task [ 7 ]
          Thomas Neidhart made changes -
          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.
          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.
          Thomas Neidhart made changes -
          Description 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. 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.
          Thomas Neidhart made changes -
          Field Original Value New Value
          Priority Major [ 3 ] Minor [ 4 ]
          Thomas Neidhart created issue -

            People

            • Assignee:
              Thomas Neidhart
              Reporter:
              Thomas Neidhart
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development