OpenCV Delaunay 三角剖分與 Voronoi 圖實戰解析

理論基礎

Delaunay 三角剖分 是平面點集劃分的核心算法，具有兩大關鍵性質：

• 空外接圓性質：任意三角形外接圓不包含其他點
• 最大最小角度性質：所有剖分中最小角度最大，避免細長三角形

Voronoi 圖 是其對偶圖，每個種子點對應一個多邊形區域，區域內任意點到該種子點距離最近。OpenCV 1.x (C API) 通過 CvSubdiv2D 實現兩者統一計算。

核心數據結構：Quad-Edge (四方邊)

OpenCV 採用 Guibas-Stolfi 的 Quad-Edge 數據結構，每條邊包含 4 個方向指針：

typedef struct CvQuadEdge2D {
    int flags;
    struct CvSubdiv2DPoint* pt[4];  // 4 個端點
    CvSubdiv2DEdge next[4];         // 4 條關聯邊
} CvQuadEdge2D;

四條邊語義 (以邊 e 為基準)：

對偶邊：eRot = cvSubdiv2DRotateEdge(e, 1) (旋轉 90°)

應用 1：提取 Delaunay 三角形拓撲

bool FindTriangleFromEdge(CvSubdiv2DEdge e) {
    CvSubdiv2DEdge t = e;
    CvPoint buf[3];
    for (int j = 0; j < 3; j++) {
        CvSubdiv2DPoint* pt = cvSubdiv2DEdgeOrg(t);  // 獲取起點
        if (!pt) return false;
        buf[j] = cvPoint(cvRound(pt->pt.x), cvRound(pt->pt.y));
        t = cvSubdiv2DGetEdge(t, CV_NEXT_AROUND_LEFT);  // 逆時針繞左面
    }
    AddTriangle(buf);  // 存儲三角形頂點
    return true;
}

// 遍歷所有邊提取三角形
for (int i = 0; i < total; i++) {
    CvQuadEdge2D* edge = (CvQuadEdge2D*)(reader.ptr);
    if (CV_IS_SET_ELEM(edge)) {
        CvSubdiv2DEdge e = (CvSubdiv2DEdge)edge;
        FindTriangleFromEdge(e);
        // 必須同時處理對偶邊 (eRot)，否則遺漏三角形
        CvSubdiv2DEdge e1 = cvSubdiv2DRotateEdge(e, 2);  // next[2] 即 eRot
        FindTriangleFromEdge(e1);
    }
    CV_NEXT_SEQ_ELEM(elem_size, reader);
}

關鍵點：Delaunay 邊有方向性，單向遍歷會漏掉三角形，必須同時處理原邊與對偶邊 (旋轉 2 位)。

應用 2：提取 Voronoi 多邊形

參考 OpenCV 範例 paint_voronoi 函數，核心邏輯：

1. 遍歷所有 Voronoi 邊 (即 Delaunay 對偶邊)
2. 對每條邊，沿 CV_NEXT_AROUND_LEFT 繞行收集頂點形成多邊形
3. 過濾無效/無窮遠點 (座標極大值)
4. 使用 cvPolyLine 繪製填充

結果演示

16 點 Delaunay 三角剖分	對應 Voronoi 劃分

編譯環境要求

• OpenCV 1.0 正式版 (舊版 C API)
• 建議安裝至默認路徑，否則需調整項目包含/庫目錄
• 現代 OpenCV 2.x/3.x/4.x 已遷移至 C++ API (cv::Subdiv2D)，本文代碼需適配升級

常見問題與避坑

1. 重複三角形：遍歷會產生重複，需用點集哈希去重
2. 無窮遠點：凸包邊緣的 Voronoi 區域無限延伸，OpenCV 用極大座標表示，繪圖時需裁剪
3. 數值穩定性：共線/共圓點導致剖分退化，需預處理去抖動
4. 性能優化：大規模點集 (10k+) 建議使用分治法或增量插入優化，或改用 CGAL/Triangle 庫

現代 C++ API 對比 (OpenCV 4.x)

// 現代風格
cv::Subdiv2D subdiv(cv::Rect(0, 0, width, height));
for (const auto& pt : points) subdiv.insert(pt);

// 獲取三角形列表
std::vector triangleList;
subdiv.getTriangleList(triangleList);

// 獲取 Voronoi 圖
std::vector> facets;
std::vector centers;
subdiv.getVoronoiFacetList(std::vector(), facets, centers);

總結

深入理解 Quad-Edge 數據結構是掌握 OpenCV 平面劃分的鑰匙。通過邊的拓撲遍歷 (CV_NEXT_AROUND_LEFT 等宏) 可提取豐富的幾何拓撲信息。雖然 OpenCV 1.x API 已過時，但其數據結構設計思想在計算幾何領域極具參考價值。現代項目建議遷移至 cv::Subdiv2D 或更專業的 CGAL 庫。