貝茲曲線遞歸細分演算法：多邊形逼近與 C++ 實作

貝茲曲線細分核心概念

貝茲曲線細分：將曲線遞歸分解為逼近多邊形，用於點選判斷、旋轉顯示等。每個頂點擁有兩個控制點控制兩側曲率。頂點陣列儲存格式：控制點 + 頂點 + 控制點 + 控制點 + 頂點 + 控制點 + ...，相鄰兩頂點間的曲線由兩頂點及其中兩控制點決定 (共 4 點定義一段三次貝茲曲線)。

主函式：PolyBezierToPolys

typedef CArray<CPoint, CPoint> CPtArray; // 點動態陣列

// 參數：bezierPts[輸入] 貝茲頂點與控制點陣列
//       bClose[輸入] 是否閉合曲線
//       polyPt[輸出] 細分後多邊形頂點陣列
//       precision[輸入] 細分精度
bool PolyBezierToPolys(CPtArray &bezierPts, bool bClose, CPtArray &polyPt, int precision) {
    polyPt.RemoveAll(); CPtArray apt;
    int count = bezierPts.GetSize();
    // 從索引 1 開始 (索引 0 為第一段的起始控制點，非閉合時無用)
    // 每段步進 3 (下一頂點在下組復用)
    for (int i = 1; i < count - 2; i += 3) {
        BezierToPoly(&bezierPts[i], apt, precision); // 細分每一段
        polyPt.Append(apt);
    }
    // 閉合曲線：最後一頂點與第一頂點連接
    if (bClose) {
        CPoint ptBuffer[4] = { bezierPts[count-2], bezierPts[count-1], bezierPts[0], bezierPts[1] };
        BezierToPoly(ptBuffer, apt, precision);
        polyPt.Append(apt);
    }
    // 過濾相鄰重複點 (精度誤差產生)
    for (int i = 0; i < polyPt.GetSize() - 1; ) {
        if (polyPt[i] == polyPt[i+1]) { polyPt.RemoveAt(i+1); }
        else i++;
    }
    return true;
}

核心細分函式：InciseBezier (德卡斯特里奧演算法)

bool InciseBezier(CPoint *pSrcPt, CPoint *pDstPt) {
    CPoint buffer[3][3];
    // 第一層中點
    for (int i = 0; i < 3; i++) {
        buffer[0][i] = (pSrcPt[i] + pSrcPt[i+1]) / 2;
    }
    // 第二層中點
    for (int i = 0; i < 2; i++) {
        buffer[1][i] = (buffer[0][i] + buffer[0][i+1]) / 2;
    }
    // 第三層中點 (曲線中點)
    buffer[2][0] = (buffer[1][0] + buffer[1][1]) / 2;

    // 左半段控制點: P0, Q0, R0, S
    // 右半段控制點: S, R1, Q2, P3
    pDstPt[0] = pSrcPt[0];
    pDstPt[1] = buffer[0][0];
    pDstPt[2] = buffer[1][0];
    pDstPt[3] = buffer[2][0];
    pDstPt[4] = buffer[1][1];
    pDstPt[5] = buffer[0][2];
    pDstPt[6] = pSrcPt[3];
    return true;
}

遞歸細分控制：BezierToPoly

bool BezierToPoly(CPoint *pSrcPts, CPtArray &polyPt, int precision) {
    polyPt.RemoveAll(); polyPt.SetSize(4);
    for (int i = 0; i < 4; i++) polyPt[i] = pSrcPts[i];

    CPoint ptBuffer[7]; bool bExit;
    while (true) {
        bExit = true;
        for (int i = 0; i < polyPt.GetSize() - 1; i += 3) {
            // 判斷是否需進一步細分 (幾何誤差檢測)
            if (!EndBezierCut(&polyPt[i], precision)) {
                bExit = false;
                InciseBezier(&polyPt[i], ptBuffer); // 一分為二
                polyPt.RemoveAt(i+1, 2); // 移除中間兩點
                polyPt.InsertAt(i+1, ptBuffer[1], 5); // 插入 5 新點
                for (int j = 0; j < 4; j++) polyPt[i+2+j] = ptBuffer[2+j];
                i += 3; // 跳過新增段
            }
        }
        if (bExit) break;
    }
    // 再次過濾重複點
    for (int i = 0; i < polyPt.GetSize() - 1; ) {
        if (polyPt[i] == polyPt[i+1]) { polyPt.RemoveAt(i+1); }
        else i++;
    }
    return true;
}

終止條件判斷：EndBezierCut

利用控制點到弦線距離判斷曲線平直度：

bool EndBezierCut(CPoint *ptBezier, int nExtent) {
    if (nExtent < 2) nExtent = 2;
    double dx = ptBezier[3].x - ptBezier[0].x;
    double dy = ptBezier[3].y - ptBezier[0].y;
    double C = dx * ptBezier[0].y - dy * ptBezier[0].x;
    double delt = nExtent * nExtent * (dy*dy + dx*dx);
    double delt1 = dy * ptBezier[1].x - dx * ptBezier[1].y + C;
    double delt2 = dy * ptBezier[2].x - dx * ptBezier[2].y + C;
    delt1 *= delt1; delt2 *= delt2;
    return (delt1 <= delt && delt2 <= delt); // 兩控制點距弦線距離平方均在容許範圍
}

演算法以遞歸中點細分配合幾何誤差判斷，高效生成精度可控的多邊形逼近，適用於即時繪圖與碰撞偵測。