Package squidpony.squidmath

Class DelaunayTriangulator

java.lang.Object

squidpony.squidmath.DelaunayTriangulator

All Implemented Interfaces:

Serializable

public class DelaunayTriangulator
extends Object
implements Serializable

A Java implementation of an incremental 2D Delaunay triangulation algorithm. This is a port of Johannes Diemke's code, with some substantial non-algorithmic changes to better work in SquidLib and to reduce allocations. You should consider using the com.badlogic.gdx.math.DelaunayTriangulator class if you use libGDX, which allocates fewer objects, or IndexedDelaunayTriangulator for a version of that libGDX class ported to use doubles.

Author:

Johannes Diemke, Tommy Ettinger

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	DelaunayTriangulator.Edge
static class	DelaunayTriangulator.Triangle

Constructor Summary

Constructors

Constructor	Description
DelaunayTriangulator()	Constructs a triangulator instance but does not insert any points; you should add points to getPoints(), which is an array that can hold 256 points, before running triangulate().
DelaunayTriangulator(Collection<CoordDouble> points)	Constructs a new triangulator instance using the specified point set.

Method Summary

Modifier and Type	Method	Description
DelaunayTriangulator.Triangle	findContainingTriangle(CoordDouble point)	Returns the triangle from this triangle soup that contains the specified point or null if no triangle from the triangle soup contains the point.
DelaunayTriangulator.Edge	findNearestEdge(CoordDouble point)	Returns the edge from the triangle soup nearest to the specified point.
DelaunayTriangulator.Triangle	findNeighbor(DelaunayTriangulator.Triangle triangle, CoordDouble ea, CoordDouble eb)
DelaunayTriangulator.Triangle	findNeighbor(DelaunayTriangulator.Triangle triangle, DelaunayTriangulator.Edge edge)	Returns the neighbor triangle of the specified triangle sharing the same edge as specified.
DelaunayTriangulator.Triangle	findOneTriangleSharing(DelaunayTriangulator.Edge edge)	Returns one of the possible triangles sharing the specified edge.
CoordDouble[]	getPoints()	Returns the point set in form of a vector of 2D vectors.
ArrayList<DelaunayTriangulator.Triangle>	getTriangles()	Returns the triangles of the triangulation in form of a list of 2D triangles.
void	removeTrianglesUsing(CoordDouble vertex)	Removes all triangles from this triangle soup that contain the specified vertex.
void	shuffle(IRNG rng)	Creates a random permutation of the specified point set.
ArrayList<DelaunayTriangulator.Triangle>	triangulate()	This method generates a Delaunay triangulation from the specified point set.

Methods inherited from class java.lang.Object

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

Constructor Details

DelaunayTriangulator

public DelaunayTriangulator()

Constructs a triangulator instance but does not insert any points; you should add points to getPoints(), which is an array that can hold 256 points, before running triangulate().

DelaunayTriangulator

public DelaunayTriangulator(Collection<CoordDouble> points)

Constructs a new triangulator instance using the specified point set.

Parameters:

points - The point set to be triangulated

Method Details

findContainingTriangle

public DelaunayTriangulator.Triangle findContainingTriangle(CoordDouble point)

Returns the triangle from this triangle soup that contains the specified point or null if no triangle from the triangle soup contains the point.

Parameters:

point - The point

Returns:

Returns the triangle from this triangle soup that contains the specified point or null

findNeighbor

public DelaunayTriangulator.Triangle findNeighbor(DelaunayTriangulator.Triangle triangle, DelaunayTriangulator.Edge edge)

Returns the neighbor triangle of the specified triangle sharing the same edge as specified. If no neighbor sharing the same edge exists null is returned.

Parameters:

triangle - The triangle

edge - The edge

Returns:

The triangles neighbor triangle sharing the same edge or null if no triangle exists

findNeighbor

public DelaunayTriangulator.Triangle findNeighbor(DelaunayTriangulator.Triangle triangle, CoordDouble ea, CoordDouble eb)

findOneTriangleSharing

public DelaunayTriangulator.Triangle findOneTriangleSharing(DelaunayTriangulator.Edge edge)

Returns one of the possible triangles sharing the specified edge. Based on the ordering of the triangles in this triangle soup the returned triangle may differ. To find the other triangle that shares this edge use the findNeighbor(Triangle, Edge) method.

Parameters:

edge - The edge

Returns:

Returns one triangle that shares the specified edge

findNearestEdge

public DelaunayTriangulator.Edge findNearestEdge(CoordDouble point)

Returns the edge from the triangle soup nearest to the specified point.

Parameters:

point - The point

Returns:

The edge from the triangle soup nearest to the specified point

removeTrianglesUsing

public void removeTrianglesUsing(CoordDouble vertex)

Removes all triangles from this triangle soup that contain the specified vertex.

Parameters:

vertex - The vertex

triangulate

public ArrayList<DelaunayTriangulator.Triangle> triangulate()

This method generates a Delaunay triangulation from the specified point set.

shuffle

public void shuffle(IRNG rng)

Creates a random permutation of the specified point set. Based on the implementation of the Delaunay algorithm this can speed up the computation.

getPoints

public CoordDouble[] getPoints()

Returns the point set in form of a vector of 2D vectors.

Returns:

Returns the points set.

getTriangles

public ArrayList<DelaunayTriangulator.Triangle> getTriangles()

Returns the triangles of the triangulation in form of a list of 2D triangles.

Returns:

Returns the triangles of the triangulation.