Package micycle.pgs

Class PGS_Triangulation

java.lang.Object
micycle.pgs.PGS_Triangulation
public final class PGS_Triangulation extends Object
Triangulation utilities for 2D PShape polygons and point sets.

This class provides:

  • Delaunay triangulation of point sets (and optional polygonal constraints),
  • Refinement of an existing Delaunay TIN (adding Steiner points to improve triangle quality),
  • Earcut triangulation for fast polygon-to-triangles conversion,
  • and helpers to convert triangulations to PShape, JTS Geometry, or graphs.

Delaunay vs. Earcut (when to use which)

  • Earcut triangulates a polygon (including holes) into triangles that exactly cover the polygon interior. It does not attempt to optimise triangle quality.
  • Delaunay triangulates a set of points to maximise the minimum angle (in the unconstrained case), producing generally “well-shaped” triangles. When used with a boundary shape, results are typically clipped/filtered to the shape and may be optionally refined.
Author:
Michael Carleton

  • Method Summary

    Modifier and Type
    Method
    Description
    static processing.core.PShape
    delaunayTriangulation(Collection<processing.core.PVector> points)
    Generates a Delaunay Triangulation from a collection of points.
    static processing.core.PShape
    delaunayTriangulation(Collection<processing.core.PVector> points, processing.core.PShape shapeConstraint)
    Generates a Delaunay Triangulation having a shape constraint from a collection of points.
    static processing.core.PShape
    delaunayTriangulation(processing.core.PShape shape)
    Generates a constrained Delaunay Triangulation from the given shape.
    static processing.core.PShape
    delaunayTriangulation(processing.core.PShape shape, Collection<processing.core.PVector> steinerPoints, boolean constrain, int refinements, boolean pretty)
    Generates a Delaunay Triangulation from the given shape.
    static org.tinfour.common.IIncrementalTin
    delaunayTriangulationMesh(Collection<processing.core.PVector> points)
    Generates a Delaunay Triangulation from a collection of points.
    static org.tinfour.common.IIncrementalTin
    delaunayTriangulationMesh(Collection<processing.core.PVector> points, processing.core.PShape shapeConstraint)
    Generates a Delaunay Triangulation having a shape constraint from a collection of points.
    static org.tinfour.common.IIncrementalTin
    delaunayTriangulationMesh(processing.core.PShape shape)
    Generates a constrained Delaunay Triangulation from the given shape.
    static org.tinfour.common.IIncrementalTin
    delaunayTriangulationMesh(processing.core.PShape shape, Collection<processing.core.PVector> steinerPoints, boolean constrain, int refinements, boolean pretty)
    Generates a Delaunay Triangulation of the given shape and returns it in raw form as a Triangulated Irregular Network (mesh).
    static List<processing.core.PVector>
    delaunayTriangulationPoints(Collection<processing.core.PVector> points)
    Generates a Delaunay Triangulation from a collection of points.
    static List<processing.core.PVector>
    delaunayTriangulationPoints(processing.core.PShape shape)
    Generates a constrained Delaunay Triangulation from a collection of points.
    static List<processing.core.PVector>
    delaunayTriangulationPoints(processing.core.PShape shape, Collection<processing.core.PVector> steinerPoints, boolean constrain, int refinements, boolean pretty)
    Generates a Delaunay Triangulation from the given shape.
    static processing.core.PShape
    earCutTriangulation(processing.core.PShape shape)
    Computes a triangulation of the shape according to the ear clipping ("earcut") method.
    static processing.core.PShape
    poissonTriangulation(processing.core.PShape shape, double spacing)
    Creates a Delaunay triangulation of the shape where additional steiner points, populated by poisson sampling, are included.
    static org.tinfour.common.IIncrementalTin
    poissonTriangulationMesh(processing.core.PShape shape, double spacing)
    Creates a Delaunay triangulation of the shape where additional steiner points, populated by poisson sampling, are included.
    static List<processing.core.PVector>
    poissonTriangulationPoints(processing.core.PShape shape, double spacing)
    Creates a Delaunay triangulation of the shape where additional steiner points, populated by poisson sampling, are included.
    static void
    refine(org.tinfour.common.IIncrementalTin triangulation, double minAngleDeg)
    Refines an existing triangulation using Ruppert's Delaunay refinement algorithm.
    static void
    refine(org.tinfour.common.IIncrementalTin triangulation, double minAngleDeg, double minTriangleArea)
    Refines an existing triangulation using Ruppert's Delaunay refinement algorithm, while also enforcing a minimum triangle area threshold.
    static org.jgrapht.graph.SimpleGraph<org.tinfour.common.SimpleTriangle,org.jgrapht.graph.DefaultEdge>
    toDualGraph(org.tinfour.common.IIncrementalTin triangulation)
    Finds the dual-graph of a triangulation.
    static org.jgrapht.graph.SimpleGraph<processing.core.PVector,micycle.pgs.commons.PEdge>
    toGraph(org.tinfour.common.IIncrementalTin triangulation)
    Finds the graph equivalent to a triangulation.
    static processing.core.PShape
    toPShape(org.tinfour.common.IIncrementalTin triangulation)
    Converts a triangulated mesh object to a PShape representing the triangulation.
    static org.jgrapht.graph.SimpleGraph<org.tinfour.common.Vertex,org.tinfour.common.IQuadEdge>
    toTinfourGraph(org.tinfour.common.IIncrementalTin triangulation)
    Finds the graph equivalent to a triangulation.

    Methods inherited from class java.lang.Object

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

  • Method Details

    • delaunayTriangulation

      public static processing.core.PShape delaunayTriangulation(processing.core.PShape shape)
      Generates a constrained Delaunay Triangulation from the given shape.
      Parameters:
      shape - the shape whose vertices to generate a triangulation from
      Returns:
      a GROUP PShape, where each child shape is one triangle
      See Also:

    • delaunayTriangulation

      public static processing.core.PShape delaunayTriangulation(processing.core.PShape shape, @Nullable Collection<processing.core.PVector> steinerPoints, boolean constrain, int refinements, boolean pretty)
      Generates a Delaunay Triangulation from the given shape. The triangulation can be both constrained (meaning the triangulation is masked by the original shape) and refined (meaning additional points are inserted, usually leading to more uniform triangle shapes and sizes).
      Parameters:
      shape - the shape whose vertices to generate a triangulation from
      steinerPoints - A list of additional points to insert into the triangulation in addition to the vertices of the input shape. Can be null.
      constrain - Constrain the triangulation output using the shape boundary (from point set). With shapes, you'll probably want to this to be true.
      refinements - The number of triangulation refinement passes to perform. Each pass inserts the centroids of every existing triangle into the triangulation. Should be 0 or greater (probably no more than 5).
      pretty - Whether to maintain the Delaunay nature when constraining the triangulation, and whether to check that centroid locations lie within the shape during refinement. When pretty=true, triangles in the triangulation may be slightly more regular in shape/size. There is a small performance overhead which becomes more considerable at higher refinement levels. When constrain=false and refinements=0, this argument has no effect.
      Returns:
      a GROUP PShape, where each child shape is one triangle
      See Also:

    • delaunayTriangulation

      public static processing.core.PShape delaunayTriangulation(Collection<processing.core.PVector> points)
      Generates a Delaunay Triangulation from a collection of points.
      Parameters:
      points - the point collection to triangulate
      Returns:
      a GROUP PShape, where each child shape is one triangle
      Since:
      1.1.0
      See Also:

    • delaunayTriangulation

      public static processing.core.PShape delaunayTriangulation(Collection<processing.core.PVector> points, processing.core.PShape shapeConstraint)
      Generates a Delaunay Triangulation having a shape constraint from a collection of points.
      Parameters:
      points - the collection of points to triangulate
      shapeConstraint - a shape that defines the boundary constraint on the triangulation
      Returns:
      a GROUP PShape, where each child shape is one triangle
      Since:
      2.0
      See Also:

    • delaunayTriangulationPoints

      public static List<processing.core.PVector> delaunayTriangulationPoints(processing.core.PShape shape)
      Generates a constrained Delaunay Triangulation from a collection of points.

      This method returns the triangulation as a list of points, rather than a PShape.

      Parameters:
      shape - the shape whose vertices to generate a triangulation from
      Returns:
      List of PVector coordinates, where each consecutive triplet of coordinates are the 3 vertices belonging to one triangle

    • delaunayTriangulationPoints

      public static List<processing.core.PVector> delaunayTriangulationPoints(processing.core.PShape shape, @Nullable Collection<processing.core.PVector> steinerPoints, boolean constrain, int refinements, boolean pretty)
      Generates a Delaunay Triangulation from the given shape. The triangulation can be both constrained (meaning the triangulation is masked by the original shape) and refined (meaning additional points are inserted, usually leading to more uniform triangle shapes and sizes).

      This method returns the triangulation as a list of points, rather than a PShape.

      Parameters:
      shape - the shape whose vertices to generate a triangulation of
      steinerPoints - A list of additional points to insert into the triangulation in addition to the vertices of the input shape. Can be null.
      constrain - Constrain the triangulation output using the shape boundary (from point set). With shapes, you'll probably want to this to be true.
      refinements - The number of triangulation refinement passes to perform. Each pass inserts the centroids of every existing triangle into the triangulation. Should be 0 or greater (probably no more than 5).
      pretty - Whether to maintain the Delaunay nature when constraining the triangulation, and whether to check that centroid locations lie within the shape during refinement. When pretty=true, triangles in the triangulation may be slightly more regular in shape/size. There is a small performance overhead which becomes more considerable at higher refinement levels. When constrain=false and refinements=0, this argument has no effect.
      Returns:
      List of PVector coordinates, where each consecutive triplet of coordinates are the 3 vertices belonging to one triangle
      See Also:

    • delaunayTriangulationPoints

      public static List<processing.core.PVector> delaunayTriangulationPoints(Collection<processing.core.PVector> points)
      Generates a Delaunay Triangulation from a collection of points.

      This method returns the triangulation as a list of points, rather than a PShape.

      Parameters:
      points - the point collection to triangulate
      Returns:
      List of PVector coordinates, where each consecutive triplet of coordinates are the 3 vertices belonging to one triangle
      Since:
      1.1.0
      See Also:

    • delaunayTriangulationMesh

      public static org.tinfour.common.IIncrementalTin delaunayTriangulationMesh(processing.core.PShape shape)
      Generates a constrained Delaunay Triangulation from the given shape.

      This method returns the triangulation in its raw form: a Triangulated Irregular Network (mesh).

      Parameters:
      shape - the shape whose vertices to generate a triangulation from
      Returns:
      Triangulated Irregular Network object (mesh)
      See Also:

    • delaunayTriangulationMesh

      public static org.tinfour.common.IIncrementalTin delaunayTriangulationMesh(@Nullable processing.core.PShape shape, @Nullable Collection<processing.core.PVector> steinerPoints, boolean constrain, int refinements, boolean pretty)
      Generates a Delaunay Triangulation of the given shape and returns it in raw form as a Triangulated Irregular Network (mesh).

      The triangulation can be constrained to the shape's boundary and refined by adding additional points, resulting in more uniform triangle shapes and sizes.

      Parameters:
      shape - the shape to generate a triangulation from. Can be null.
      steinerPoints - A list of additional points to insert into the triangulation in addition to the vertices of the input shape. Can be null.
      constrain - whether to constrain the triangulation to the shape's boundary. If using a shape, it is recommended to set this to true.
      refinements - The number of times to subdivide the triangulation by inserting the centroid of each triangle. Should be 0 or greater, typically no more than 5.
      pretty - Whether to maintain Delaunay nature when constraining the triangulation and check that centroid locations are within the shape during refinement. This can result in more regular triangle shapes and sizes, but with a performance overhead that increases with higher refinement levels. Has no effect if constrain=false and refinements=0.
      Returns:
      Triangulated Irregular Network object (mesh)
      See Also:

    • delaunayTriangulationMesh

      public static org.tinfour.common.IIncrementalTin delaunayTriangulationMesh(Collection<processing.core.PVector> points)
      Generates a Delaunay Triangulation from a collection of points.

      This method returns the triangulation in its raw form: a Triangulated Irregular Network (mesh).

      Parameters:
      points - the point collection to triangulate
      Returns:
      Triangulated Irregular Network object (mesh)
      Since:
      1.1.0
      See Also:

    • delaunayTriangulationMesh

      public static org.tinfour.common.IIncrementalTin delaunayTriangulationMesh(Collection<processing.core.PVector> points, processing.core.PShape shapeConstraint)
      Generates a Delaunay Triangulation having a shape constraint from a collection of points.

      This method returns the triangulation in its raw form: a Triangulated Irregular Network (mesh).

      Parameters:
      points - the collection of points to triangulate
      shapeConstraint - a shape that defines the boundary constraint on the triangulation
      Returns:
      Triangulated Irregular Network object (mesh)
      Since:
      2.0
      See Also:

    • refine

      public static void refine(org.tinfour.common.IIncrementalTin triangulation, double minAngleDeg)
      Refines an existing triangulation using Ruppert's Delaunay refinement algorithm.

      Refinement inserts additional Steiner points in order to improve triangle quality, primarily by eliminating "skinny" triangles whose minimum internal angle is below minAngleDeg. The provided IIncrementalTin is modified in place.

      Typical values for minAngleDeg are in the range 20–33 degrees. Larger values produce more regular triangles but may significantly increase the number of inserted points (and runtime). Extremely large values may not be achievable for constrained triangulations.

      Parameters:
      triangulation - the triangulation to refine (modified in place); must not be null
      minAngleDeg - the minimum allowed triangle angle, in degrees
      Since:
      2.2

    • refine

      public static void refine(org.tinfour.common.IIncrementalTin triangulation, double minAngleDeg, double minTriangleArea)
      Refines an existing triangulation using Ruppert's Delaunay refinement algorithm, while also enforcing a minimum triangle area threshold.

      Refinement inserts additional Steiner points to improve triangle quality by removing triangles with angles below minAngleDeg. The minTriangleArea parameter acts as a stop condition to avoid over-refining very small triangles. The provided IIncrementalTin is modified in place.

      Parameters:
      triangulation - the triangulation to refine (modified in place); must not be null
      minAngleDeg - the minimum allowed triangle angle, in degrees
      minTriangleArea - triangles with area less than or equal to this value will not be further refined
      Since:
      2.2

    • poissonTriangulation

      public static processing.core.PShape poissonTriangulation(processing.core.PShape shape, double spacing)
      Creates a Delaunay triangulation of the shape where additional steiner points, populated by poisson sampling, are included.
      Parameters:
      shape -
      spacing - (Minimum) spacing between poisson points
      Returns:
      a GROUP PShape, where each child shape is one triangle
      See Also:

    • poissonTriangulationPoints

      public static List<processing.core.PVector> poissonTriangulationPoints(processing.core.PShape shape, double spacing)
      Creates a Delaunay triangulation of the shape where additional steiner points, populated by poisson sampling, are included.
      Parameters:
      shape -
      spacing - (Minimum) spacing between poisson points
      Returns:
      list of PVectors, where each successive triplet of PVectors correspond to the 3 vertices of one triangle
      See Also:

    • poissonTriangulationMesh

      public static org.tinfour.common.IIncrementalTin poissonTriangulationMesh(processing.core.PShape shape, double spacing)
      Creates a Delaunay triangulation of the shape where additional steiner points, populated by poisson sampling, are included.

      This method returns the triangulation in its raw form: a TriangulatedIrregular Network (mesh).

      Parameters:
      shape -
      spacing - (Minimum) spacing between poisson points
      Returns:
      Triangulated Irregular Network object (mesh)
      See Also:

    • earCutTriangulation

      public static processing.core.PShape earCutTriangulation(processing.core.PShape shape)
      Computes a triangulation of the shape according to the ear clipping ("earcut") method. The triangulation is constrained to the shape outline.
      Parameters:
      shape - shape whose vertices to triangulate
      Returns:
      a GROUP PShape, where each child shape is one triangle
      Since:
      1.1.0, Supports holes since 1.3.0

    • toPShape

      public static processing.core.PShape toPShape(org.tinfour.common.IIncrementalTin triangulation)
      Converts a triangulated mesh object to a PShape representing the triangulation.
      Parameters:
      triangulation - the IIncrementalTin object to convert
      Returns:
      a GROUP PShape, where each child shape is one triangle
      Since:
      1.4.0

    • toGraph

      public static org.jgrapht.graph.SimpleGraph<processing.core.PVector,micycle.pgs.commons.PEdge> toGraph(org.tinfour.common.IIncrementalTin triangulation)
      Finds the graph equivalent to a triangulation. Graph vertices are triangulation vertices; graph edges are triangulation edges.

      The output is an undirected weighted graph of Processing primitives; edge weights are their euclidean length of their triangulation equivalent.

      Parameters:
      triangulation - triangulation mesh
      Since:
      1.3.0
      See Also:

    • toTinfourGraph

      public static org.jgrapht.graph.SimpleGraph<org.tinfour.common.Vertex,org.tinfour.common.IQuadEdge> toTinfourGraph(org.tinfour.common.IIncrementalTin triangulation)
      Finds the graph equivalent to a triangulation. Graph vertices are triangulation vertices; graph edges are triangulation edges.

      The output is an undirected weighted graph of Tinfour primitives; edge weights are their euclidean length of their triangulation equivalent.

      Parameters:
      triangulation - triangulation mesh
      Since:
      1.3.0
      See Also:

    • toDualGraph

      public static org.jgrapht.graph.SimpleGraph<org.tinfour.common.SimpleTriangle,org.jgrapht.graph.DefaultEdge> toDualGraph(org.tinfour.common.IIncrementalTin triangulation)
      Finds the dual-graph of a triangulation.

      A dual graph of a triangulation has a vertex for each constrained triangle of the input, and an edge connecting each pair of triangles that are adjacent.

      Edges are weighted, where weights represent a quality measure ([0...1], where 1 is a perfect square) for the quadrilateral formed by collapsing the shared edge between the two triangles.

      Parameters:
      triangulation - triangulation mesh
      Returns:
      a simple weighted dual graph
      Since:
      1.3.0
      See Also: