Package georegression.geometry.polygon

Class TriangulateSimpleRemoveEars_F64

java.lang.Object
georegression.geometry.polygon.TriangulateSimpleRemoveEars_F64
public class TriangulateSimpleRemoveEars_F64 extends Object
Triangulates a simple polygon by removing ears. Triangulation breaks a polygon up into triangle components. There are many different ways to triangulate polygons and in most situations there are multiple solutions. The approach employed here is described in [1] and works by selecting "ears" in the polygon and breaking those off into triangles. The overall complexity is O(N^2). If the orientation of the polygon is known then the step where it determines CW or CCW can be skipped by setting knownOrder to true.

[1] Joseph O'Rourke, Computational Geometry in C. 2nd Ed. Chapter 1

  • Field Details

    • tol

      public double tol
      Tolerance for line segments being colinear

    • knownOrder

      public boolean knownOrder
      If true the value of ccw will be assumed to be the polygon's order. Saving some computations

    • ccw

      public boolean ccw
      If the polygon is in ccw order

    • polygon

      protected final CyclicalLinkedList<georegression.geometry.polygon.TriangulateSimpleRemoveEars_F64.Vertex> polygon

    • vertexes

      protected final DogArray<georegression.geometry.polygon.TriangulateSimpleRemoveEars_F64.Vertex> vertexes

  • Constructor Details

    • TriangulateSimpleRemoveEars_F64

      public TriangulateSimpleRemoveEars_F64()

  • Method Details

    • process

      public void process(Polygon2D_F64 input, DogArray<ThreeIndexes> output)
      Converts the polygon into a set of triangles.
      Parameters:
      input - (Input) Input polygon
      output - (Output) Storage for triangulation results. Reset is called.