Method EarCutTriangulation

Common/DataModel/vtkPolygon.cxx:1612–1688

------------------------------------------------------------------------------ Triangulation method based on ear-cutting. Triangles, or ears, are repeatedly cut off from the polygon based on a measure of the vertex. Vertices must be convex, but different measures will produce different triangulations. While the algorithm works in 3D (the points don't have to be projected into 2D), it is assumed th

// don't have to be projected into 2D), it is assumed the polygon is planar -
// if not, poor results may occur.
int vtkPolygon::EarCutTriangulation(vtkIdList* outTris, int measure)
{
  // Initialize the list of output triangles
  outTris->Reset();

  // Make sure there are at least 3 vertices
  if (this->PointIds->GetNumberOfIds() < 3)
  {
    return (this->SuccessfulTriangulation = 0);
  }

  // Compute the tolerance local to this polygon
  this->ComputeTolerance();

  // Check for trivial triangulation cases
  if (::SimpleTriangulation(this->PointIds, this->Points, this->Tol * this->Tol, outTris))
  {
    return (this->SuccessfulTriangulation = 1);
  }

  // If npts is 4 and ::SimpleTriangulation() failed, the quad is poorly shaped.
  // Triangulate by the shorter diagonal

  // Establish a more convenient structure for the triangulation process
  vtkPolyVertexList poly(this->PointIds, this->Points, this->Tol * this->Tol, measure);
  vtkLocalPolyVertex* vtx;
  int i, id;

  // The polygon normal is needed during triangulation
  //
  if (!poly.ComputeNormal())
  {
    return (this->SuccessfulTriangulation = 0);
  }

  // Now compute the angles between edges incident to each
  // vertex. Place the structure into a priority queue (those
  // vertices with smallest measure are to be removed first).
  //
  vtkPriorityQueue* VertexQueue = vtkPriorityQueue::New();
  VertexQueue->Allocate(poly.NumberOfVerts);
  for (i = 0, vtx = poly.Head; i < poly.NumberOfVerts; i++, vtx = vtx->next)
  {
    // concave (negative measure) vertices are not eligible for removal
    if (poly.ComputeMeasure(vtx) > 0.0)
    {
      VertexQueue->Insert(vtx->measure, vtx->id);
    }
  }

  // For each vertex in the priority queue, and as long as there
  // are three or more vertices, remove the vertex (if possible)
  // and create a new triangle. NOTE: at one time this code checked the
  // number of verts in the removal queue, and if it was equal to the number
  // of remaining vertices, it assumed a convex polygon and indiscrimately
  // removed vertices. This tends to produce bad results as some triangles
  // were nearly flat etc. so the code was removed.
  //