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

Class SweepHullDelaunay2D

java.lang.Object

de.lmu.ifi.dbs.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 and 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 and Description
private java.util.LinkedList<IntIntPair>	hull Internal representation of the hull
private static Logging	LOG Class logger
private java.util.List<double[]>	points The current set of points.
private java.util.ArrayList<SweepHullDelaunay2D.Triangle>	tris Triangles

Constructor Summary

Constructors

Constructor and Description
SweepHullDelaunay2D() Constructor.
SweepHullDelaunay2D(java.util.List<double[]> points) Constructor.

Method Summary

Modifier and Type	Method and 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 helper
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 necessary
java.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

Methods inherited from class java.lang.Object

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

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

Constructor Detail

SweepHullDelaunay2D

public SweepHullDelaunay2D()

Constructor.

SweepHullDelaunay2D

public SweepHullDelaunay2D(java.util.List<double[]> points)

Constructor.

Parameters:

points - Existing points

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

public SweepHullDelaunay2D.Triangle findSmallest(int seedid,
                                                 int seed2id,
                                                 double[] sortd,
                                                 int[] sorti,
                                                 int len)

Parameters:

seedid - First seed point

seed2id - Second seed point

sorti - Points

len - 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 test

flippedB - Bit set to mark triangles as done

flipTriangle

int flipTriangle(int i,
                 long[] flipped)

Flip a single triangle, if necessary.

Parameters:

i - Triangle number

flipped - 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 point

b - Reference point

d - Test point

Returns:

true when on the left side