## Class GrahamScanConvexHull2D

• java.lang.Object
• elki.math.geometry.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
• ### Constructor Summary

Constructors
Constructor Description
GrahamScanConvexHull2D()
Constructor.
• ### Method Summary

All 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
• #### minmaxX

private DoubleMinMax minmaxX
Min/Max in X
• #### minmaxY

private DoubleMinMax minmaxY
Min/Max in Y
• #### 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

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