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

          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?
          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 -

          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
          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 -

          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.
          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.
          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.
          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.
          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.

            People

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

              Dates

              • Created:
                Updated:
                Resolved:

                Development