de.lmu.ifi.dbs.elki.math.geometry

Class GrahamScanConvexHull2D

java.lang.Object

de.lmu.ifi.dbs.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 and 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 and Description
GrahamScanConvexHull2D() Constructor.

Method Summary

Modifier and Type	Method and 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

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