Class SweepHullDelaunay2D


  • @Reference(authors="D. Sinclair",
               title="S-hull: a fast sweep-hull routine for Delaunay triangulation",
               booktitle="Online",
               url="http://s-hull.org/",
               bibkey="web/Sinclair16")
    public class SweepHullDelaunay2D
    extends java.lang.Object
    Compute the Convex Hull and/or Delaunay Triangulation, using the sweep-hull approach of David Sinclair.

    Note: This implementation does not check or handle duplicate points!

    TODO: Handle duplicates.

    TODO: optimize data structures for memory usage

    Since:
    0.5.0
    Author:
    Erich Schubert
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      private static class  SweepHullDelaunay2D.Orientation
      The possible orientations two triangles can have to each other.
      static class  SweepHullDelaunay2D.Triangle
      Class representing a triangle, by referencing points in a list.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.LinkedList<IntIntPair> hull
      Internal representation of the hull
      private static Logging LOG
      Class logger
      private java.util.List<double[]> points
      The current set of points.
      private java.util.ArrayList<SweepHullDelaunay2D.Triangle> tris
      Triangles
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(double... point)
      Add a single point to the list (this does not compute or update the triangulation!)
      (package private) void debugHull()
      Debug helper
      protected SweepHullDelaunay2D.Triangle findSmallest​(int seedid, int seed2id, double[] sortd, int[] sorti, int len)  
      (package private) int flipTriangle​(int i, long[] flipped)
      Flip a single triangle, if necessary.
      (package private) int flipTriangles​(long[] flippedB)
      Flip triangles as necessary
      (package private) int flipTriangles​(long[] flippedA, long[] flippedB)
      Flip triangles as necessary
      java.util.ArrayList<SweepHullDelaunay2D.Triangle> getDelaunay()
      Get the Delaunay triangulation.
      Polygon getHull()
      Get the convex hull only.
      (package private) boolean leftOf​(double[] a, double[] b, double[] d)
      Test if the double[] AD is right of AB.
      static double quadraticEuclidean​(double[] v1, double[] v2)
      Squared euclidean distance. 2d.
      (package private) void run​(boolean hullonly)
      Run the actual algorithm
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • LOG

        private static final Logging LOG
        Class logger
      • points

        private java.util.List<double[]> points
        The current set of points.

        Note: this list should not be changed after running the algorithm, since we use it for object indexing, and the ids should not change

      • hull

        private java.util.LinkedList<IntIntPair> hull
        Internal representation of the hull
    • Constructor Detail

      • SweepHullDelaunay2D

        public SweepHullDelaunay2D()
        Constructor.
      • SweepHullDelaunay2D

        public SweepHullDelaunay2D​(java.util.List<double[]> points)
        Constructor.
        Parameters:
        points - Existing points
    • Method Detail

      • add

        public void add​(double... point)
        Add a single point to the list (this does not compute or update the triangulation!)
        Parameters:
        point - Point to add
      • run

        void run​(boolean hullonly)
        Run the actual algorithm
        Parameters:
        hullonly -
      • findSmallest

        protected SweepHullDelaunay2D.Triangle findSmallest​(int seedid,
                                                            int seed2id,
                                                            double[] sortd,
                                                            int[] sorti,
                                                            int len)
        Parameters:
        seedid - First seed point
        seed2id - Second seed point
        sorti - Points
        len - Number of points
        Returns:
        Best triangle
      • debugHull

        void debugHull()
        Debug helper
      • flipTriangles

        int flipTriangles​(long[] flippedB)
        Flip triangles as necessary
        Parameters:
        flippedB - Bit set to mark triangles as done
      • flipTriangles

        int flipTriangles​(long[] flippedA,
                          long[] flippedB)
        Flip triangles as necessary
        Parameters:
        flippedA - Bit set for triangles to test
        flippedB - Bit set to mark triangles as done
      • flipTriangle

        int flipTriangle​(int i,
                         long[] flipped)
        Flip a single triangle, if necessary.
        Parameters:
        i - Triangle number
        flipped - Bitset to modify
        Returns:
        number of other triangle, or -1
      • getHull

        public Polygon getHull()
        Get the convex hull only.

        Note: if you also want the Delaunay Triangulation, you should get that first!

        Returns:
        Convex hull
      • getDelaunay

        public java.util.ArrayList<SweepHullDelaunay2D.Triangle> getDelaunay()
        Get the Delaunay triangulation.
        Returns:
        Triangle list
      • quadraticEuclidean

        public static double quadraticEuclidean​(double[] v1,
                                                double[] v2)
        Squared euclidean distance. 2d.
        Parameters:
        v1 - First double[]
        v2 - Second double[]
        Returns:
        Quadratic distance
      • leftOf

        boolean leftOf​(double[] a,
                       double[] b,
                       double[] d)
        Test if the double[] AD is right of AB.
        Parameters:
        a - Starting point
        b - Reference point
        d - Test point
        Returns:
        true when on the left side