Package com.irurueta.geometry

Class VanGoghTriangulator2D

java.lang.Object
com.irurueta.geometry.Triangulator2D
com.irurueta.geometry.VanGoghTriangulator2D
public class VanGoghTriangulator2D extends Triangulator2D
This class defines a triangulator for 2D polygons. Triangulators divide polygons into triangles, which are the simplest geometric figure. This implementation uses Van Gogh or Ear Cutting algorithm for triangulation.

  • Constructor Details

    • VanGoghTriangulator2D

      public VanGoghTriangulator2D()

  • Method Details

    • getMethod

      public TriangulatorMethod getMethod()
      Returns triangulator method. Each method implementation will divide polygons into triangles using different techniques.
      Specified by:
      getMethod in class Triangulator2D
      Returns:
      Triangulator method.

    • triangulate

      public List<Triangle2D> triangulate(Polygon2D polygon) throws TriangulatorException
      Triangulates provided polygon by dividing it into a set of triangles.
      Specified by:
      triangulate in class Triangulator2D
      Parameters:
      polygon - Polygon to be triangulated.
      Returns:
      List of triangles forming the polygon that has been triangulated.
      Throws:
      TriangulatorException - Raised if triangulation cannot be done. Usually this indicates numerical instability or polygon degeneracy.

    • triangulate

      public List<Triangle2D> triangulate(List<Point2D> vertices) throws TriangulatorException
      Triangulates a polygon formed by provided vertices.
      Specified by:
      triangulate in class Triangulator2D
      Parameters:
      vertices - List of points considered as vertices of a polygon.
      Returns:
      List of triangles forming the polygon that has been triangulated.
      Throws:
      TriangulatorException - Raised if triangulation cannot be done. Usually this indicates numerical instability or polygon degeneracy.

    • triangulate

      public List<Triangle2D> triangulate(List<Point2D> vertices, List<int[]> indices) throws TriangulatorException
      Triangulates a polygon formed by provided vertices.
      Specified by:
      triangulate in class Triangulator2D
      Parameters:
      vertices - List of points considered as vertices of a polygon.
      indices - List where indices of original vertices will be stored. This list can be used to refer to the original order of vertices. Notice that vertices indices might be repeated because vertices might appear in more than one triangle after triangulation. If this parameter is null, indices won't be stored in this list.
      Returns:
      List of triangles forming the polygon that has been triangulated
      Throws:
      TriangulatorException - Raised if triangulation cannot be done. Usually this indicates numerical instability or polygon degeneracy.

    • internalTriangulate

      private static List<Triangle2D> internalTriangulate(List<Point2D> verticesCopy, List<int[]> indices, List<Point2D> originalVertices) throws TriangulatorException
      Internal method that computes the actual triangulation.
      Parameters:
      verticesCopy - List of points considered as verticesCopy of a polygon. This list will be modified after execution of this method.
      indices - List where indices of original verticesCopy will be stored. This list can be used to refer to the original order of verticesCopy. Notice that verticesCopy indices might be repeated because verticesCopy might appear in more than one triangle after triangulation. If this parameter is null, indices won't be stored in this list.
      originalVertices - Reference to original list of vertices that won't be modified.
      Returns:
      List of triangles forming the polygon that has been triangulated.
      Throws:
      TriangulatorException - Raised if triangulation cannot be done. Usually this indicates numerical instability or polygon degeneracy.

    • computeIndices

      private static void computeIndices(List<Point2D> vertices, List<Triangle2D> triangles, List<int[]> indices)
      Computes indices of resulting triangles vertices respect to original polygon vertices. Indices are stored in provided indices list.
      Parameters:
      vertices - Vertices of polygon.
      triangles - Triangles obtained after triangulation.
      indices - Indices of original positions of resulting triangle's vertices.

    • isEar

      private static boolean isEar(Triangle2D triangle, List<Point2D> polygonVertices)
      Determines if provided triangle can be considered as an ear of the remaining polygon formed by provided vertices. An ear is usually a triangle located at a corner of a polygon. A triangle is considered an ear if no other vertex of the polygon lies within the triangle and if the triangle is not convex (is concave).
      Parameters:
      triangle - A triangle.
      polygonVertices - A list of points forming the remaining polygon
      Returns:
      true if triangle is ear, false otherwise.