Package elki.math.geometry

Class GrahamScanConvexHull2D

  • @Reference(authors="P. Graham",
           title="An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set",
           booktitle="Information Processing Letters 1",
           url="https://doi.org/10.1016/0020-0190(72)90045-2",
           bibkey="DBLP:journals/ipl/Graham72")
public class GrahamScanConvexHull2D
extends java.lang.Object
    Classes to compute the convex hull of a set of points in 2D, using the classic Grahams scan. Also computes a bounding box.

    Reference:

    P. Graham
    An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set
    Information Processing Letters 1

    Since:
    0.4.0
    Author:
    Erich Schubert

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private double factor
      Scaling factor if we have very small polygons.
      private DoubleMinMax minmaxX
      Min/Max in X
      private DoubleMinMax minmaxY
      Min/Max in Y
      private boolean ok
      Flag to indicate that the hull has been computed.
      private java.util.List<double[]> points
      The current set of points

    • Method Summary

      All 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 the hull!)
      private void computeConvexHull()
      Compute the convex hull.
      private void findStartingPoint()
      Find the starting point, and sort it to the beginning of the list.
      Polygon getHull()
      Compute the convex hull, and return the resulting polygon.
      private double getRX​(double[] a, double[] origin)
      Get the relative X coordinate to the origin.
      private double getRY​(double[] a, double[] origin)
      Get the relative Y coordinate to the origin.
      private void grahamScan()
      The actual graham scan main loop.
      private boolean isConvex​(double[] a, double[] b, double[] c)
      Simple convexity test.
      protected int isLeft​(double[] a, double[] b, double[] o)
      Test whether a point is left of the other wrt. the origin.
      private double mdist​(double[] a, double[] b)
      Manhattan distance.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • points

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

      • ok

        private boolean ok
        Flag to indicate that the hull has been computed.

      • factor

        private double factor
        Scaling factor if we have very small polygons. TODO: needed? Does this actually improve things?

    • Constructor Detail

      • GrahamScanConvexHull2D

        public GrahamScanConvexHull2D()
        Constructor.

    • Method Detail

      • add

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

      • computeConvexHull

        private void computeConvexHull()
        Compute the convex hull.

      • findStartingPoint

        private void findStartingPoint()
        Find the starting point, and sort it to the beginning of the list. The starting point must be on the outer hull. Any "most extreme" point will do, e.g., the one with the lowest Y coordinate and for ties with the lowest X.

      • getRX

        private double getRX​(double[] a,
                     double[] origin)
        Get the relative X coordinate to the origin.
        Parameters:
        a -
        origin - origin double[]
        Returns:
        relative X coordinate

      • getRY

        private double getRY​(double[] a,
                     double[] origin)
        Get the relative Y coordinate to the origin.
        Parameters:
        a -
        origin - origin double[]
        Returns:
        relative Y coordinate

      • isLeft

        protected final int isLeft​(double[] a,
                           double[] b,
                           double[] o)
        Test whether a point is left of the other wrt. the origin.
        Parameters:
        a - double[] A
        b - double[] B
        o - Origin double[]
        Returns:
        +1 when left, 0 when same, -1 when right

      • mdist

        private double mdist​(double[] a,
                     double[] b)
        Manhattan distance.
        Parameters:
        a - double[] A
        b - double[] B
        Returns:
        Manhattan distance

      • isConvex

        private boolean isConvex​(double[] a,
                         double[] b,
                         double[] c)
        Simple convexity test.
        Parameters:
        a - double[] A
        b - double[] B
        c - double[] C
        Returns:
        convexity

      • grahamScan

        private void grahamScan()
        The actual graham scan main loop.

      • getHull

        public Polygon getHull()
        Compute the convex hull, and return the resulting polygon.
        Returns:
        Polygon of the hull