Package squidpony.squidmath

Class IndexedDelaunayTriangulator

java.lang.Object
squidpony.squidmath.IndexedDelaunayTriangulator
public class IndexedDelaunayTriangulator
extends Object
Delaunay triangulation. Adapted from Paul Bourke's triangulate: http://paulbourke.net/papers/triangulate/
Author:
Nathan Sweet

  • Constructor Summary

    Constructors 
    Constructor Description
    IndexedDelaunayTriangulator()  

  • Method Summary

    Modifier and Type Method Description
    IntVLA computeTriangles​(double[] polygon, boolean sorted)  
    IntVLA computeTriangles​(double[] points, int offset, int count, boolean sorted)
    Triangulates the given point cloud to a list of triangle indices that make up the Delaunay triangulation.
    static boolean isPointInPolygon​(double[] polygon, int offset, int count, double x, double y)
    Returns true if the specified point is in the polygon.
    void trim​(IntVLA triangles, double[] points, double[] hull, int offset, int count)
    Removes all triangles with a centroid outside the specified hull, which may be concave.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

  • Method Details

    • computeTriangles

      public IntVLA computeTriangles​(double[] polygon, boolean sorted)
      See Also:
      computeTriangles(double[], int, int, boolean)

    • computeTriangles

      public IntVLA computeTriangles​(double[] 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 - x,y pairs describing points. Duplicate points will result in undefined behavior.
      sorted - If false, the points will be sorted by the x coordinate, which is required by the triangulation algorithm. In that case, the input array is not modified, the returned indices are for the input array, and count*2 additional working memory is needed.
      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.

    • trim

      public void trim​(IntVLA triangles, double[] points, double[] 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.

    • isPointInPolygon

      public static boolean isPointInPolygon​(double[] polygon, int offset, int count, double x, double y)
      Returns true if the specified point is in the polygon.
      Parameters:
      offset - Starting polygon index.
      count - Number of array indices to use after offset.