Implementing triangulation algorithm for concave shapes

Question

I have some problems with implementing the Triangulation algorithm in c. Some of the chosen points are wrong, and I don't know where possibly I could make a mistake, but for my inexperienced eye it looks fine.

EDIT: I am using msvc c++ compiler for some operator overloads for v3 struct.

Here is my main code:

struct shape
{
    u32 VerticesCount;
    v3* Vertices;

    u32 TrianglesCount;
    int* Triangles;
};    

static void PolygonTriangulate(shape* Shape)
{
    bool Result = false;

    int  ListSize  = Shape->VerticesCount;
    int* IndexList = (int*)malloc(sizeof(int) * ListSize);
    for(int i = 0; i < ListSize; ++i)
    {
        IndexList[i] = i;
    }

    int TotalTriangleCount = Shape->VerticesCount - 2;
    int TotalTriangleCountIdx = TotalTriangleCount*3;

    int* TrianglesResult = (int*)malloc(sizeof(int)*TotalTriangleCountIdx);
    int  TriangleIdx = 0;

    while(ListSize > 3)
    {
        for(int PolyIdx = 0; PolyIdx < ListSize; ++PolyIdx)
        {
            int cur  = IndexList[PolyIdx];
            int prev = GetListElement(IndexList, ListSize, PolyIdx - 1);
            int next = GetListElement(IndexList, ListSize, PolyIdx + 1);

            v3 A = Shape->Vertices[cur];
            v3 B = Shape->Vertices[prev];
            v3 C = Shape->Vertices[next];

            v3 AB = B - A;
            v3 AC = C - A;
            
            if(Cross(AB, AC).Z < 0.0f)
            {
                continue;
            }

            bool IsEar = true;

            for(int i = 0; i < Shape->VerticesCount; ++i)
            {
                if((cur == i) || (prev == i) || (next == i))
                {
                    continue;
                }

                v3 Point = Shape->Vertices[i];
                
                if(IsPointInTriangle(Point, B, A, C))
                {
                    IsEar = false;
                    break;
                }
            }

            if(IsEar)
            {
                TrianglesResult[TriangleIdx++] = prev;
                TrianglesResult[TriangleIdx++] = cur;
                TrianglesResult[TriangleIdx++] = next;

                RemoveElementFromList(IndexList, &ListSize, PolyIdx);
                break;
            }
        }
    }

    TrianglesResult[TriangleIdx++] = IndexList[0];
    TrianglesResult[TriangleIdx++] = IndexList[1];
    TrianglesResult[TriangleIdx++] = IndexList[2];

    Shape->TrianglesCount = TriangleIdx;
    Shape->Triangles = TrianglesResult;
}

Helpers functions:

static bool IsPointInTriangle(v3 Point, v3 A, v3 B, v3 C)
{
    v3 AB = B - A;
    v3 BC = C - B;
    v3 CA = A - C;

    v3 AP = Point - A;
    v3 BP = Point - B;
    v3 CP = Point - C;

    float Cross1 = Cross(AB, AP).Z;
    float Cross2 = Cross(BC, BP).Z;
    float Cross3 = Cross(CA, CP).Z;

    if((Cross1 <= 0.0f) && (Cross2 <= 0.0f) && (Cross3 <= 0.0f))
    {
        return true;
    } 

    return false;
}

int GetListElement(int* IndexList, int ListSize, int PolyIdx)
{
    int Result;

    if(PolyIdx < 0)
    {
        Result = IndexList[PolyIdx % ListSize + ListSize];
    }
    else if(PolyIdx >= ListSize)
    {
        Result = IndexList[PolyIdx % ListSize];
    }
    else
    {
        Result = IndexList[PolyIdx];
    }

    return Result;
}

void RemoveElementFromList(int* IndexList, int* ListSize, int PolyIdx)
{
    for(int i = 0; i < *ListSize; ++i)
    {
        if(IndexList[i] >= PolyIdx)
        {
            IndexList[i] = IndexList[i + 1];
        }
    }
    *ListSize -= 1;
}

And the place where I render my shape, but I don't think there could be a problem:

for(u32 CoordIdx = 0; CoordIdx < Shape->TrianglesCount; CoordIdx += 3)
    {
        triangle_t Triangle = {};

        Triangle.points[0] = 20*Shape->Vertices[Shape->Triangles[CoordIdx  ]].XY + Center;
        Triangle.points[1] = 20*Shape->Vertices[Shape->Triangles[CoordIdx+1]].XY + Center;
        Triangle.points[2] = 20*Shape->Vertices[Shape->Triangles[CoordIdx+2]].XY + Center;

        DrawTriangle(Triangle, CreateColor(V3(1.0f, 1.0f, 0.0f)));
    }

My result:

My result how it should be, but without inner triangles:

And expected result:

Note for images above: I use a different render system, that's why It looks inverted, which should not influence a result. Thank you.

Answer 1

Ok, as Matt Timmermans mentioned, I just got simple typo in RemoveElementFromList function.

Instead of if (IndexList[i] >= PolyIdx) should be if (i >= PolyIdx):

void RemoveElementFromList(int* IndexList, int* ListSize, int PolyIdx)
{
    for(int i = 0; i < *ListSize; ++i)
    {
        if(i >= PolyIdx)
        {
            IndexList[i] = IndexList[i + 1];
        }
    }
    *ListSize -= 1;
}

Just that simple.