APIdia Launch Partner
Top Description Fields Constructors Methods
com.badlogic.gdx.math

public Class DelaunayTriangulator

extends Object
Class Inheritance
Imports
com.badlogic.gdx.utils.*
Delaunay triangulation. Adapted from Paul Bourke's triangulate: http://paulbourke.net/papers/triangulate/
Authors
Nathan Sweet, Berstanio

Field Summary

Modifier and TypeField and Description
private final Vector2
centroid

private static final int
COMPLETE

private final ShortArray
completedTriangles

private final IntArray
edges

private static final int
INCOMPLETE

private static final int
INSIDE

private final ShortArray
originalIndices

private final ShewchukExactPredicates
predicates

private final IntArray
quicksortStack

private float[]
sortedPoints

private final ShortArray
triangles

Constructor Summary

AccessConstructor and Description
public
DelaunayTriangulator()

Method Summary

Modifier and TypeMethod and Description
private int
circumCircle(float[] points, int end, double xp, double yp, int p1, int p2, int p3)

Returns INSIDE if point xp,yp is inside the circumcircle of the triangle (p1,p2,p3).

private int
circumCircleReal(double xp, double yp, double x1, double y1, double x2, double y2, double x3, double y3)

In-circle test for a triangle of three real vertices.

public ShortArray
computeTriangles(FloatArray points, boolean sorted)

public ShortArray
computeTriangles(float[] polygon, boolean sorted)

public ShortArray

Returns:

triples of indices into the points that describe the triangles in clockwise order. Note the returned array is reused for later calls to the same method.
computeTriangles(float[]
x,y pairs describing points. Duplicate points will result in undefined behavior.
points, int offset, int count, boolean
If false, the points will be sorted by the x coordinate, which is required by the triangulation algorithm. If sorting is done the input array is not modified, the returned indices are for the input array, and count*2 additional working memory is needed.
sorted)

Triangulates the given point cloud to a list of triangle indices that make up the Delaunay triangulation.

private int
quicksortPartition(final float[] values, int lower, int upper, short[] originalIndices)

private void
sort(float[] values, int
Number of indices, must be even.
count)

Sorts x,y pairs of values by the x value.

public void
trim(ShortArray triangles, float[] points, float[] hull, int offset, int count)

Removes all triangles with a centroid outside the specified hull, which may be concave.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

centroidback to summary
private final Vector2 centroid
COMPLETEback to summary
private static final int COMPLETE
completedTrianglesback to summary
private final ShortArray completedTriangles
edgesback to summary
private final IntArray edges
INCOMPLETEback to summary
private static final int INCOMPLETE
INSIDEback to summary
private static final int INSIDE
originalIndicesback to summary
private final ShortArray originalIndices
predicatesback to summary
private final ShewchukExactPredicates predicates
quicksortStackback to summary
private final IntArray quicksortStack
sortedPointsback to summary
private float[] sortedPoints
trianglesback to summary
private final ShortArray triangles

Constructor Detail

DelaunayTriangulatorback to summary
public DelaunayTriangulator()

Method Detail

circumCircleback to summary
private int circumCircle(float[] points, int end, double xp, double yp, int p1, int p2, int p3)

Returns INSIDE if point xp,yp is inside the circumcircle of the triangle (p1,p2,p3). Returns COMPLETE if xp is to the right of the entire circumcircle. Otherwise returns INCOMPLETE. Note: a point on the circumcircle edge is considered outside.

Indices >= end refer to ghost super-triangle vertices at infinity. The number of ghost vertices in the triple selects the test:

  • 0 ghosts: standard in-circle test.
  • 1 ghost: half-plane test on the line through the two real vertices, inside when p is on the ghost's side.
  • 2 ghosts: half-plane test on a line through the real vertex, inside when p is on the ghosts' side.
  • 3 ghosts: always INSIDE (the root super-triangle).
circumCircleRealback to summary
private int circumCircleReal(double xp, double yp, double x1, double y1, double x2, double y2, double x3, double y3)

In-circle test for a triangle of three real vertices.

computeTrianglesback to summary
public ShortArray computeTriangles(FloatArray points, boolean sorted)
See Also
computeTriangles(float[], int, int, boolean)
computeTrianglesback to summary
public ShortArray computeTriangles(float[] polygon, boolean sorted)
See Also
computeTriangles(float[], int, int, boolean)
computeTrianglesback to summary
public ShortArray computeTriangles(float[] points, int offset, int count, boolean sorted)

Triangulates the given point cloud to a list of triangle indices that make up the Delaunay triangulation.

Parameters
points:float[]

x,y pairs describing points. Duplicate points will result in undefined behavior.

sorted:boolean

If false, the points will be sorted by the x coordinate, which is required by the triangulation algorithm. If sorting is done the input array is not modified, the returned indices are for the input array, and count*2 additional working memory is needed.

Returns:ShortArray

triples of indices into the points that describe the triangles in clockwise order. Note the returned array is reused for later calls to the same method.

quicksortPartitionback to summary
private int quicksortPartition(final float[] values, int lower, int upper, short[] originalIndices)
sortback to summary
private void sort(float[] values, int count)

Sorts x,y pairs of values by the x value.

Parameters
count:int

Number of indices, must be even.

trimback to summary
public void trim(ShortArray triangles, float[] points, float[] hull, int offset, int count)

Removes all triangles with a centroid outside the specified hull, which may be concave. Note some triangulations may have triangles whose centroid is inside the hull but a portion is outside.