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

Class SweepHullDelaunay2D

java.lang.Object

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

@Reference(authors="David Sinclair",
           title="S-hull: a fast sweep-hull routine for Delaunay triangulation",
           booktitle="Online: http://s-hull.org/")
public class SweepHullDelaunay2D
extends 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!

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
(package 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 LinkedList<IntIntPair>	hull Internal representation of the hull
private static Logging	LOG Class logger
private List<Vector>	points The current set of points.
private ArrayList<SweepHullDelaunay2D.Triangle>	tris Triangles

Constructor Summary

Constructors

Constructor and Description
SweepHullDelaunay2D() Constructor.
SweepHullDelaunay2D(List<Vector> points) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
void	add(Vector point) Add a single point to the list (this does not compute or update the triangulation!)
(package private) void	debugHull() Debug helper
(package private) int	flipTriangle(int i, long[] flipped) Flip a single triangle, if necessary.
(package private) int	flipTriangles(long[] flippedA, long[] flippedB) Flip triangles as necessary
ArrayList<SweepHullDelaunay2D.Triangle>	getDelaunay() Get the Delaunay triangulation.
Polygon	getHull() Get the convex hull only.
(package private) boolean	leftOf(Vector a, Vector b, Vector d) Test if the vector AD is right of AB.
static void	main(String[] args)
static double	quadraticEuclidean(Vector v1, Vector 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 List<Vector> 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 ArrayList<SweepHullDelaunay2D.Triangle> tris

Triangles

hull

private LinkedList<IntIntPair> hull

Internal representation of the hull

Constructor Detail

SweepHullDelaunay2D

public SweepHullDelaunay2D()

Constructor.

SweepHullDelaunay2D

public SweepHullDelaunay2D(List<Vector> points)

Constructor.

Parameters:

points - Existing points

Method Detail

add

public void add(Vector 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 -

debugHull

void debugHull()

Debug helper

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 ArrayList<SweepHullDelaunay2D.Triangle> getDelaunay()

Get the Delaunay triangulation.

Returns:

Triangle list

quadraticEuclidean

public static double quadraticEuclidean(Vector v1,
                        Vector v2)

Squared euclidean distance. 2d.

Parameters:

v1 - First vector

v2 - Second vector

Returns:

Quadratic distance

leftOf

boolean leftOf(Vector a,
             Vector b,
             Vector d)

Test if the vector AD is right of AB.

Parameters:

a - Starting point

b - Reference point

d - Test point

Returns:

true when on the left side

main

public static void main(String[] args)