Package elki.math.geometry
Class SweepHullDelaunay2D
- java.lang.Object
-
- elki.math.geometry.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 hullprivate static Logging
LOG
Class loggerprivate java.util.List<double[]>
points
The current set of points.private java.util.ArrayList<SweepHullDelaunay2D.Triangle>
tris
Triangles
-
Constructor Summary
Constructors Constructor Description SweepHullDelaunay2D()
Constructor.SweepHullDelaunay2D(java.util.List<double[]> points)
Constructor.
-
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 helperprotected 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 necessaryjava.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
-
-
-
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
-
tris
private java.util.ArrayList<SweepHullDelaunay2D.Triangle> tris
Triangles
-
hull
private java.util.LinkedList<IntIntPair> hull
Internal representation of the hull
-
-
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 pointseed2id
- Second seed pointsorti
- Pointslen
- 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 testflippedB
- Bit set to mark triangles as done
-
flipTriangle
int flipTriangle(int i, long[] flipped)
Flip a single triangle, if necessary.- Parameters:
i
- Triangle numberflipped
- 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 pointb
- Reference pointd
- Test point- Returns:
- true when on the left side
-
-