耳切法三角剖分多边形，C++代码实现

可以参考以下的 C 代码实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_POLYGON_VERTICES 1000

typedef struct {
    double x, y;
} Point;

typedef struct {
    int a, b, c;
} Triangle;

int earClipping(Point* polygon, int numVertices, Triangle* triangles) {
    // 初始化三角剖分结果为空
    int numTriangles = 0;

    // 每次剪掉一个“耳朵”后多边形的边数都会减少，最后只剩下 3 个点
    while (numVertices > 3) {
        // 遍历所有顶点，找到一个“耳朵”
        for (int i = 0; i < numVertices; i++) {
            // 确定当前顶点 i 对应的边所在的两个顶点
            int iPrev = (i + numVertices - 1) % numVertices;
            int iNext = (i + 1) % numVertices;

            // 判断顶点 i 是否是凸顶点
            Point pi = polygon[i];
            Point piPrev = polygon[iPrev];
            Point piNext = polygon[iNext];
            double crossProduct = (pi.x - piPrev.x) * (piNext.y - pi.y) - (piNext.x - pi.x) * (pi.y - piPrev.y);
            if (crossProduct >= 0) {
                continue;
            }

            // 判断顶点 i 是否成为凸耳朵
            // 如果顶点 i 成为凸耳朵，需要确定凸耳朵的另外两个顶点
            int isEar = 1;
            for (int j = 0; j < numVertices; j++) {
                if (j == i || j == iPrev || j == iNext) {
                    continue;
                }
                if ((polygon[j].x - pi.x) * (piPrev.y - pi.y) + (piPrev.x - pi.x) * (pi.y - polygon[j].y) >= 0 &&
                    (piPrev.x - pi.x) * (piNext.y - pi.y) + (piNext.x - pi.x) * (pi.y - piPrev.y) >= 0 &&
                    (piNext.x - pi.x) * (polygon[j].y - pi.y) + (polygon[j].x - pi.x) * (pi.y - piNext.y) >= 0) {
                    isEar = 0;
                    break;
                }
            }
            if (!isEar) {
                continue;
            }

            // 找到一个凸耳朵，将它对应的三角形加入到三角剖分结果中
            Triangle triangle = { iPrev, i, iNext };
            triangles[numTriangles++] = triangle;

            // 从多边形中剪掉凸耳朵 i
            for (int j = i + 1; j < numVertices; j++) {
                polygon[j - 1] = polygon[j];
            }
            numVertices--;
            i--;
        }
    }

    // 将多边形剩余的三个顶点构成最后一个三角形
    Triangle triangle = { 0, 1, 2 };
    triangles[numTriangles++] = triangle;

    return numTriangles;
}

int main() {
    Point polygon[MAX_POLYGON_VERTICES];
    int numVertices;

    // 读取多边形顶点坐标
    scanf("%d", &numVertices);
    for (int i = 0; i < numVertices; i++) {
        scanf("%lf%lf", &polygon[i].x, &polygon[i].y);
    }

    // 进行三角剖分
    Triangle triangles[MAX_POLYGON_VERTICES];
    int numTriangles = earClipping(polygon, numVertices, triangles);

    // 输出三角剖分结果
    printf("%d\n", numTriangles);
    for (int i = 0; i < numTriangles; i++) {
        printf("%d %d %d\n", triangles[i].a, triangles[i].b, triangles[i].c);
    }

    return 0;
}