Package elki.math.geometry

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