Triangulation of polygon with holes using ear clipping algorithm

Question

After parsing the contours from a truetype font file, I generated the points that compose the polygon that I want to triangularize. These points are generated by merging the different holes into one polygon:

Generated Polygon of the letter A:

As you can see i "merged" the holes by picking two points between the inner and outer polygon with the minimum distance.

This polygon breaks my current implementation of the ear clipping algorithm:

static bool
is_point_in_triangle(triangle Triangle, vec2 Point) {
      vec2 AB = Triangle.B - Triangle.A;
      vec2 BC = Triangle.C - Triangle.B;
      vec2 CA = Triangle.A - Triangle.C;
      vec2 AP = Point - Triangle.A;
      vec2 BP = Point - Triangle.B;
      vec2 CP = Point - Triangle.C;
      float Cross1 = cross(AB, AP);
      float Cross2 = cross(BC, BP);
      float Cross3 = cross(CA, CP);
      return (Cross1 <= 0.0f) && (Cross2 <= 0.0f) && (Cross3 <= 0.0f);
}

static triangle_list
triangulate_ear_clip(memory_arena* Arena, polygon SimplePolygon) {
      triangle_list List = {};
      
      unsigned int TriangleCount = 0;
      triangle* Triangles = allocate_array(Arena, triangle, SimplePolygon.Count - 2);
      
      unsigned int* Indices = allocate_array(Arena, unsigned int, SimplePolygon.Count);
      int IndexCount = SimplePolygon.Count;
      for(int Index = 0; Index < IndexCount; ++Index) {
            Indices[Index] = Index;
      }
      
      while(IndexCount > 3) {
            for(int Index = 0; Index < IndexCount; ++Index) {
                  int IndexA = Indices[Index];
                  int IndexB = Indices[Index ? (Index - 1) : (IndexCount - 1)];
                  int IndexC = Indices[(Index + 1) % IndexCount];
                  check((IndexA != IndexB) && (IndexA != IndexC) && (IndexC != IndexB));
                  vec2 A = SimplePolygon.Elements[IndexA];
                  vec2 B = SimplePolygon.Elements[IndexB];
                  vec2 C = SimplePolygon.Elements[IndexC];
                  vec2 AB = B - A;
                  vec2 AC = C - A;
                  check((A != B) && (A != C) && (B != C));
                  if(cross(AB, AC) >= 0.0f) {
                        bool IsEar = true;
                        for(int OtherIndex = 0; OtherIndex < (int)SimplePolygon.Count; ++OtherIndex) {
                              if((OtherIndex != IndexA) && (OtherIndex != IndexB) && (OtherIndex != IndexC)) {
                                    vec2 D = SimplePolygon.Elements[OtherIndex];
                                    if(is_point_in_triangle(triangle_from(B, A, C), D)) {
                                          IsEar = false;
                                          break;
                                    }
                              }
                        }
                        
                        if(IsEar) {
                              Triangles[TriangleCount++] = triangle_from(B, A, C);
                              move(Indices + Index, Indices + Index + 1, sizeof(unsigned int) * (IndexCount - Index - 1));
                              IndexCount--;
                              break;
                        }
                  }
            }
      }
      
      check(IndexCount == 3);
      check(TriangleCount == SimplePolygon.Count - 3);
      Triangles[TriangleCount++] = triangle_from(SimplePolygon.Elements[Indices[0]], SimplePolygon.Elements[Indices[1]], SimplePolygon.Elements[Indices[2]]);
      
      List.Count = TriangleCount;
      List.Elements = Triangles;
      return List;
}

For some reason cross(AB, AC) is always negative and the loop stalls forever. I can't figure out why this happens since the polygon should be ok to be triangulated. I also provided a list of the generated points in the second image link.

Even if some types in the provided code are non-standard they should easily be recognizable, feel free to ask otherwise. memory_arena is just a custom allocator i use.

Thanks for your attention. PS: I dont want to use a library

Answer 1

The problem was that in is_point_in_triangle() the function was considering points on the outline inside the triangle (and then not consider the triangle as an ear).

This breaks because when merging the polygon and the hole, some points overlap.

I fixed this by removing the =: (Cross1 < 0.0f) && (Cross2 < 0.0f) && (Cross3 < 0.0f) and by doing a special check:

vec2 D = SimplePolygon.Elements[OtherIndex];                                    
if((D != A) && (D != B) && (D != C)) {
  if(is_point_in_triangle(triangle_from(B, A, C), D)) {
      IsEar = false;
      break;
  }
}