C++调用OpenCV Subdiv2D生成Delaunay三角网格边缘有缺口如何解决

问题根因 #

OpenCV的cv::Subdiv2D在实现Delaunay三角剖分时，会自动在用户传入的初始矩形外部生成4个虚拟辅助点用于完成剖分计算，调用getTriangleList()返回的结果会包含这些虚拟点和真实采样点组成的三角形。你当前的代码没有对返回的三角形做合法性校验，部分边界处的真实三角形因为和虚拟点配对，要么被绘制到图像范围外，要么填充逻辑异常，最终导致边缘出现缺口。
另外cv::Rect本身是左闭右开的坐标规则，你传入的边界点坐标width-1、height-1虽然符合范围要求，但部分边缘三角在计算时会被判定为跨出初始剖分区域，不会被纳入有效返回列表。

解决方法 #

修改两处逻辑即可解决问题：

1. 初始化剖分用的矩形时，设置比图像范围稍大的区间，避免边界点和边缘三角被误判为超出范围
2. 绘制三角形前增加校验逻辑，仅绘制三个顶点都落在图像有效范围内的三角单元

修改后的可运行代码 #

#include <opencv2/opencv.hpp>
#include <vector>

void DrawDelaunay(cv::Mat& image, cv::Subdiv2D& subdiv, const cv::Rect& validRect);

int main(int argc,char** argv)
{
    // 图像尺寸
    int width = 3440;
    int height = 2293;
    cv::Rect validRect(0, 0, width, height);
    
    // 采样点坐标
    std::vector<int> x = {0, width-1, width-1, 0, 589, 1015, 1674, 2239, 2432, 3324, 2125, 2110, 3106, 3295, 1298, 1223, 277, 208, 54, 54, 1749, 3245, 431, 1283, 1397, 3166};
    std::vector<int> y = {0, 0, height-1, height-1, 2125, 1739, 1154, 817, 331, 143, 1377, 2006, 1952, 1501, 872, 545, 812, 310, 2180, 54, 2244, 2234, 1387, 1412, 118, 1040};

    // 初始化Delaunay剖分，剖分范围比图像大2个像素，避免边缘判定问题
    cv::Rect subdivRect(-1, -1, width + 2, height + 2);
    cv::Subdiv2D subdiv(subdivRect);
    for(size_t i=0; i < x.size(); ++i)
    {
        cv::Point2f p(x[i], y[i]);
        subdiv.insert(p);
    }
    
    // 绘制网格单元
    cv::Mat image(height, width, CV_8U, cv::Scalar(0));
    DrawDelaunay(image, subdiv, validRect);
    cv::resize(image, image, cv::Size(), 0.3, 0.3);
    cv::imshow("Delaunay", image);

    cv::waitKey(0);
    return 0;
}

void DrawDelaunay(cv::Mat& image, cv::Subdiv2D& subdiv, const cv::Rect& validRect)
{
    std::vector<cv::Vec6f> elements;
    subdiv.getTriangleList(elements);
    std::vector<cv::Point> pt(3);

    for(size_t i=0; i < elements.size(); ++i)
    {
        cv::Vec6f t = elements[i];
        pt[0] = cv::Point(cvRound(t[0]), cvRound(t[1]));
        pt[1] = cv::Point(cvRound(t[2]), cvRound(t[3]));
        pt[2] = cv::Point(cvRound(t[4]), cvRound(t[5]));

        // 仅绘制三个顶点都在图像有效范围内的三角形
        if (validRect.contains(pt[0]) && validRect.contains(pt[1]) && validRect.contains(pt[2]))
        {
            // 绘制网格边
            cv::Scalar black(0);
            cv::line(image, pt[0], pt[1], black, 3);
            cv::line(image, pt[1], pt[2], black, 3);
            cv::line(image, pt[2], pt[0], black, 3);

            // 填充网格单元
            int nump = 3;
            const cv::Point* pp[1] = {&pt[0]};
            cv::fillPoly(image, pp, &nump, 1, cv::Scalar(255));
        }
    }
}

补充说明 #

你之前在Matlab中得到的结果符合预期，是因为Matlab的Delaunay剖分接口默认不会返回带虚拟边界点的三角单元，也没有OpenCV这种左闭右开的矩形判定逻辑，所以不需要额外处理边界。

内容的提问来源于stack exchange，提问作者Chris