Package elki.math.geometry
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 Xprivate DoubleMinMax
minmaxY
Min/Max in Yprivate 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 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.
-
-
-
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?
-
-
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[] Ab
- double[] Bo
- 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[] Ab
- double[] B- Returns:
- Manhattan distance
-
isConvex
private boolean isConvex(double[] a, double[] b, double[] c)
Simple convexity test.- Parameters:
a
- double[] Ab
- double[] Bc
- 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
-
-