精华内容
下载资源
问答
  • 该项目基于代码,但我对其进行了一些重组,并扩展了Delaunay和Voronoi部分。 赫尔(Hull),德劳内(Delaunay)和沃罗诺伊(Voronoi)的3个概念或所有相关概念。 如果您有可以在任何空间尺寸上工作的凸包算法,则...
  • 并行 Delaunay Voronoi 细分密度估计 许可 Tess 是在 BSD 风格下作为开源软件。 要求 C++11 编译器 块并行库 或计算几何库 安装 以下说明假设 Qhull 是串行几何引擎。 构建依赖 一种。 git clone ...
  • 30局部与分割-三角剖分delaunay和voronoi划分 简介 Delaunay三角剖分是1934年发明的将空间点连接为三角形,使得所有三角形中最小角最大的一个技术。 如果你熟悉计算机图形学,你便会知道Delaunay三角剖分是变现...

    30局部与分割-三角剖分delaunay和voronoi划分

    简介

    Delaunay三角剖分是1934年发明的将空间点连接为三角形,使得所有三角形中最小角最大的一个技术。

    如果你熟悉计算机图形学,你便会知道Delaunay三角剖分是变现三维形状的基础。如果我们在三维空间渲染一个,我们可以通过这个物体的投影来建立二维视觉图,并用二维Delaunay三角剖分来分析识别该物体,或者将它与实物相比较。Delaunay剖分是连接计算机视觉与计算机图形学的桥梁。然而使用OpenCV实现三角剖分的不足之处就是OpenCV只实现了二维的Delaunay剖分。如果我们能够对三维点进行三角剖分,也就是说构成立体视觉,那么我们可以在三维的计算机图形和计算机视觉进行无缝的转换。然而二维三角剖分通常用于计算机视觉中标记空间目标的特征或运动场景跟踪,目标识别,或两个不同的摄像机的场景匹配(如图从立体图像中获得深度信息)。


    重要提示

    1、程序的关键是通过下面**号强调的利用CvSeqReader遍历所有的Delaunay或者Voronoi.
    2、Delaunay或者Voronoi之间的桥梁就是通过函数,cvSubdiv2DRotateEdge()实现边的旋转(切换)
    3、这个Delaunay是个有向图,还是双向的。具体怎么实现的,没有较深的数据结构为基础是很难理解的,至少现在我还不是很懂具体的实现,关于它的使用还是摸索阶段。OpenCV水很深,如果这东西只是为我们用,或者了解,而不是研究,我们没有必要纠结的太深。


    三角剖分delaunay和voronoi划分基本原理

    Bowyer-Watson算法

    目前采用逐点插入方式生成的Delaunay三角网的算法主要基于Bowyer-Watson算法,Bowyer-Watson算法的主要步骤如下:
    1)建立初始三角网格:针对给定的点集V,找到一个包含该点集的矩形R,我们称R为辅助窗口。连接R的任意一条对角线,形成两个三角形,作为初始Delaunay三角网格。
    2)逐点插入:假设目前已经有一个Delaunay三角网格T,现在在它里面再插入一个点P,需要找到该点P所在的三角形。从P所在的三角形开始,搜索该三角形的邻近三角形,并进行空外接圆检测。找到外接圆包含点P的所有的三角形并删除这些三角形,形成一个包含P的多边形空腔,我们称之为Delaunay空腔。然后连接P与Delaunay腔的每一个顶点,形成新的Delaunay三角网格。
    3)删除辅助窗口R:重复步骤2),当点集V中所有点都已经插入到三角形网格中后,将顶点包含辅助窗口R的三角形全部删除。
    在这些步骤中,快速定位点所在的三角形、确定点的影响并构建Delaunay腔的过程是每插入一个点都会进行的。随着点数的增加,三角形数目增加很快,因此缩短这两个过程的计算时间,是提高算法效率的关键。
    算法执行图示如下:
    这里写图片描述


    编程中用到的相关结构图

    1:通过 cvSubdiv2DRotateEdge函数切换delaunay和voronoi边:
    这里写图片描述
    2:通过cvSubdiv2DGetEdge函数获取下一条delaunay边(或者voronoi边):
    这里写图片描述


    相关代码

    #include <opencv2/imgproc/imgproc_c.h>
    #include <opencv2/legacy/legacy.hpp>
    #include "opencv2/highgui/highgui.hpp"
    
    #include <stdio.h>
    static void help(void)//提示函数
    {
        printf("\nThis program demostrates iterative construction of\n"
            "delaunay triangulation and voronoi tesselation.\n"
            "It draws a random set of points in an image and then delaunay triangulates them.\n"
            "Usage: \n"
            "./delaunay \n"
            "\nThis program builds the traingulation interactively, you may stop this process by\n"
            "hitting any key.\n");
    }
    //delaunay初始化函数,申请内存
    static CvSubdiv2D* init_delaunay(CvMemStorage* storage,
        CvRect rect)
    {
        CvSubdiv2D* subdiv;
    
        subdiv = cvCreateSubdiv2D(CV_SEQ_KIND_SUBDIV2D, sizeof(*subdiv),
            sizeof(CvSubdiv2DPoint),
            sizeof(CvQuadEdge2D),
            storage);
        cvInitSubdivDelaunay2D(subdiv, rect);
    
        return subdiv;
    }
    
    //绘制点,圆形3:半径
    static void draw_subdiv_point(IplImage* img, CvPoint2D32f fp, CvScalar color)
    {
        cvCircle(img, cvPoint(cvRound(fp.x), cvRound(fp.y)), 3, color, CV_FILLED, 8, 0);
    }
    
    //绘制边
    static void draw_subdiv_edge(IplImage* img, CvSubdiv2DEdge edge, CvScalar color)
    {
        CvSubdiv2DPoint* org_pt;
        CvSubdiv2DPoint* dst_pt;
        CvPoint2D32f org;
        CvPoint2D32f dst;
        CvPoint iorg, idst;
    
        org_pt = cvSubdiv2DEdgeOrg(edge);
        dst_pt = cvSubdiv2DEdgeDst(edge);
    
        if (org_pt && dst_pt)
        {
            org = org_pt->pt;
            dst = dst_pt->pt;
    
            iorg = cvPoint(cvRound(org.x), cvRound(org.y));
            idst = cvPoint(cvRound(dst.x), cvRound(dst.y));
    
            cvLine(img, iorg, idst, color, 1, CV_AA, 0);
        }
    }
    /*********************************************************
    //绘制delaunay和voronoi边
    delaunay:黑色
    voronoi:绿色
    *********************************************************/
    
    static void draw_subdiv(IplImage* img, CvSubdiv2D* subdiv,
        CvScalar delaunay_color, CvScalar voronoi_color)
    {
        CvSeqReader  reader;
        int i, total = subdiv->edges->total;
        int elem_size = subdiv->edges->elem_size;
    
        cvStartReadSeq((CvSeq*)(subdiv->edges), &reader, 0);
    
        for (i = 0; i < total; i++)
        {
            CvQuadEdge2D* edge = (CvQuadEdge2D*)(reader.ptr);
    
            if (CV_IS_SET_ELEM(edge))//4条边其中2条是反边;0:delaunay边,1:voronoi边
            {
                draw_subdiv_edge(img, (CvSubdiv2DEdge)edge + 1, voronoi_color);
                draw_subdiv_edge(img, (CvSubdiv2DEdge)edge, delaunay_color);
            }
    
            CV_NEXT_SEQ_ELEM(elem_size, reader);
        }
    }
    /******************************************************
    locate_point:参数含义
    subdiv:细分结构;
    fp:随机生成的点,距离正方形的边沿为5cm
    img:画板600x600
    active_color:颜色值,蓝色
    作用:
    1:绘制新添加的点
    2:重新绘制新增点旁边的Delaunay边为红色
    ******************************************************/
    static void locate_point(CvSubdiv2D* subdiv, CvPoint2D32f fp, IplImage* img,
        CvScalar active_color)
    {
        CvSubdiv2DEdge e;
        CvSubdiv2DEdge e0 = 0;
        CvSubdiv2DPoint* p = 0;
    
        cvSubdiv2DLocate(subdiv, fp, &e0, &p);//根据新添加的点,找到最近的Delaunay边
    
        if (e0)
        {
            e = e0;
            do
            {
                draw_subdiv_edge(img, e, active_color);//绘制Delaunay三角剖分的边为红色
                e = cvSubdiv2DGetEdge(e, CV_NEXT_AROUND_LEFT);//遍历Delaunay三角剖分的边
            } while (e != e0);//逆时针遍历新添加点所在区域的Delaunay
        }
    
        draw_subdiv_point(img, fp, active_color);//在画板上绘制点
    }
    
    //填充Voronoi四边形,并绘制黑色轮廓
    static void draw_subdiv_facet(IplImage* img, CvSubdiv2DEdge edge)
    {
        CvSubdiv2DEdge t = edge;
        int i, count = 0;
        CvPoint* buf = 0;
    
        // count number of edges in facet
        do
        {
            count++;
            t = cvSubdiv2DGetEdge(t, CV_NEXT_AROUND_LEFT);
        } while (t != edge);//逆时针遍历一圈Voronoi边
    
        buf = (CvPoint*)malloc(count * sizeof(buf[0]));
    
        // gather points
        t = edge;
        for (i = 0; i < count; i++)//获取Voronoi四边形的四个点
        {
            CvSubdiv2DPoint* pt = cvSubdiv2DEdgeOrg(t);
            if (!pt) break;
            buf[i] = cvPoint(cvRound(pt->pt.x), cvRound(pt->pt.y));//将4个点放入buf中
            t = cvSubdiv2DGetEdge(t, CV_NEXT_AROUND_LEFT);//指向下一条边
        }
    
        if (i == count)//所有的边都收集完了之后
        {
            CvSubdiv2DPoint* pt = cvSubdiv2DEdgeDst(cvSubdiv2DRotateEdge(edge, 1));//从Voronoi转到Delaunay获取到之前添加的点
            cvFillConvexPoly(img, buf, count, CV_RGB(rand() & 255, rand() & 255, rand() & 255), CV_AA, 0);//将Voronoi四边形填充为随机的颜色
            cvPolyLine(img, &buf, &count, 1, 1, CV_RGB(0, 0, 0), 1, CV_AA, 0);//绘制Voronoi四边形轮廓为黑色
            draw_subdiv_point(img, pt->pt, CV_RGB(0, 0, 0));//将点绘制为白色
        }
        free(buf);//释放内存
    }
    
    static void paint_voronoi(CvSubdiv2D* subdiv, IplImage* img)
    {
        CvSeqReader  reader;
        int i, total = subdiv->edges->total;
        int elem_size = subdiv->edges->elem_size;
    
        cvCalcSubdivVoronoi2D(subdiv);//重新计算Voronoi
    
        cvStartReadSeq((CvSeq*)(subdiv->edges), &reader, 0);
    
        for (i = 0; i < total; i++)
        {
            CvQuadEdge2D* edge = (CvQuadEdge2D*)(reader.ptr);//遍历delaunay
    
            if (CV_IS_SET_ELEM(edge))//填充每一块Voronoi四边形
            {
                CvSubdiv2DEdge e = (CvSubdiv2DEdge)edge;
                // left
                draw_subdiv_facet(img, cvSubdiv2DRotateEdge(e, 1));//eRot边
    
                // right
                draw_subdiv_facet(img, cvSubdiv2DRotateEdge(e, 3));//eRot reverse边
            }
    
            CV_NEXT_SEQ_ELEM(elem_size, reader);//获取下一个delaunay边
        }
    }
    
    
    static void run(void)
    {
        char win[] = "source";
        int i;
        CvRect rect = { 0, 0, 600, 600 };//创建一个正方形
        CvMemStorage* storage;
        CvSubdiv2D* subdiv;//声明细分结果
        IplImage* img;
        CvScalar active_facet_color, delaunay_color, voronoi_color, bkgnd_color;//声明各种颜色
    
        active_facet_color = CV_RGB(255, 0, 0);//红色
        delaunay_color = CV_RGB(0, 0, 0);//黑色delaunay边
        voronoi_color = CV_RGB(0, 180, 0);//绿色voronoi边
        bkgnd_color = CV_RGB(255, 255, 255);//白色
    
        img = cvCreateImage(cvSize(rect.width, rect.height), 8, 3);//创建一幅图像
        cvSet(img, bkgnd_color, 0);//设置图像背景为白色
    
        cvNamedWindow(win, 1);//创建一个窗口
    
        storage = cvCreateMemStorage(0);//声明一个存储器
        subdiv = init_delaunay(storage, rect);//初始化delaunay,主要申请一些内存
    
        printf("Delaunay triangulation will be build now interactively.\n"
            "To stop the process, press any key\n\n");
    
        for (i = 0; i < 200; i++)//200个随机点
        {
            CvPoint2D32f fp = cvPoint2D32f((float)(rand() % (rect.width - 10) + 5),
                (float)(rand() % (rect.height - 10) + 5));//生成随机点,距离正方形的边沿为5cm
    
            locate_point(subdiv, fp, img, active_facet_color);//重新绘制新增点旁边的Delaunay边为红色
            cvShowImage(win, img);//刷新画板
    
            if (cvWaitKey(100) >= 0)
                break;
    
            //while (1) {//用于调试
            //  if (cvWaitKey(100) == 'n') {
            //      break;
            //  }
            //}
            cvSubdivDelaunay2DInsert(subdiv, fp);//插入新增加的点
            cvCalcSubdivVoronoi2D(subdiv);//计算Voronoi细分
            cvSet(img, bkgnd_color, 0);//将画板清零
            draw_subdiv(img, subdiv, delaunay_color, voronoi_color);//重新绘制Delaunay和Voronoi边
            cvShowImage(win, img);//显示画板
            if (cvWaitKey(100) >= 0)
                break;
        }
    
        cvSet(img, bkgnd_color, 0);//将画板清零
        paint_voronoi(subdiv, img);//绘制voronoi
        cvShowImage(win, img);
    
        cvWaitKey(0);
    
        cvReleaseMemStorage(&storage);
        cvReleaseImage(&img);
        cvDestroyWindow(win);
    }
    
    int main(int argc, char** argv)
    {
        (void)argc; (void)argv;
        help();
        run();
        return 0;
    }
    
    #ifdef _EiC
    main(1, "delaunay.c");
    #endif
    

    最终结果图片如下:

    这里写图片描述

    展开全文
  • 本文主要介绍使用cv2模块实现Delaunay三角剖分和Voronoi图。 测试图片: 示例代码: # 导入模块 import cv2 import numpy as np import random # 检查点是否在长方形区域内 def rect_contains(rect, point): ...

    本文主要介绍使用cv2模块实现Delaunay三角剖分和Voronoi图。

    测试图片:

    示例代码:

    # 导入模块
    import cv2
    import numpy as np
    import random
    
    # 检查点是否在长方形区域内
    def rect_contains(rect, point):
        if point[0] < rect[0]:
            return False
        elif point[1] < rect[1]:
            return False
        elif point[0] > rect[2]:
            return False
        elif point[1] > rect[3]:
            return False
        return True
    
    # 绘制点
    def draw_point(img, p, color):
        cv2.circle(img, p, 2, color, 0)
    
    # 绘制delaunay triangles
    def draw_delaunay(img, subdiv, delaunary_color):
        triangleList = subdiv.getTriangleList()
        size = img.shape
        r = (0, 0, size[1], size[0])
        
        for t in triangleList:
            pt1 = (t[0], t[1])
            pt2 = (t[2], t[3])
            pt3 = (t[4], t[5])
        
            if rect_contains(r, pt1) and rect_contains(r, pt2) and rect_contains(r, pt3):
                cv2.line(img, pt1, pt2, delaunary_color, 1)
                cv2.line(img, pt2, pt3, delaunary_color, 1)
                cv2.line(img, pt3, pt1, delaunary_color, 1)
    
    # 绘制 voroni diagram
    def draw_voroni(img, subdiv):
        (facets, centers) = subdiv.getVoronoiFacetList([])
        
        for i in range(0, len(facets)):
            ifacet_arr = []
            for f in facets[i]:
                ifacet_arr.append(f)
            
            ifacet = np.array(ifacet_arr, np.int)
            color = (random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))
            
            cv2.fillConvexPoly(img, ifacet, color, 0)
            ifacets = np.array([ifacet])
            cv2.polylines(img, ifacets, True, (0, 0, 0), 1)
            cv2.circle(img, (centers[i][0], centers[i][1]), 3, (0, 0, 0), 0)
    
    # 定义窗口名称
    win_delaunay = "Delaunay Triangulation"
    win_voronoi = "Voronoi Diagram"
    
    # 绘制三角形时打开动画
    animats = True
    
    # 定义绘制的颜色
    delaunay_color = (255, 255, 255)
    points_color = (0, 0, 255)
    
    # 读取图片
    img = cv2.imread('./obama.jpg')
    
    # 复制图片
    img_orig = img.copy()
    
    # 与Subdiv2D一起使用的矩形
    size = img.shape
    rect = (0, 0, size[1], size[0])
    
    # 创建Subdic2D的一个实例
    subdiv = cv2.Subdiv2D(rect)
    
    # 创建一个数组用于保存点
    points = []
    
    
    # 从文本文件读取点
    with open('./obama.txt') as file:
        for line in file:
            x, y = line.split()
            points.append((int(x), int(y)))
        
        # 将点插入到subdiv
        for p in points:
            subdiv.insert(p)
            
            # 显示animation 
            if animats:
                img_copy = img_orig.copy()
                # 绘制delaunay triangle
                draw_delaunay(img_copy, subdiv, (255, 255, 255))
                
                # 显示结果
                # cv2.imshow(win_delaunay, img_copy)
                # cv2.waitKey(100)
    
    
    # 绘制delaunay triangles
    draw_delaunay( img, subdiv, (255, 255, 255) );
    
    # 绘制点
    for p in points :
        draw_point(img, p, (0,0,255))
    
    # 为voronoi Diagram分配空间
    img_voronoi = np.zeros(img.shape, dtype = img.dtype)
    
    # 绘制voronoi diagram
    draw_voroni(img_voronoi,subdiv)
    
    # 保存结果
    #保存结果
    cv2.imwrite(win_delaunay + '.jpg', img)
    cv2.imwrite(win_voronoi + '.jpg', img_voronoi)
    # 显示结果
    # cv2.imshow(win_delaunay,img)
    # cv2.imshow(win_voronoi,img_voronoi)
    # cv2.waitKey(0)    

    结果:

    Delaunay Triangulation:

     

    Voronoi Diagram

     

     

    展开全文
  • Delaunay三角形和Voronoi划分的迭代式构造#include "cv.h" #include "highgui.h" #include #include <opencv2/legacy/legacy.hpp>//opencv2添加此头文件 CvSubdiv2D* init_delaunay(CvMemStorage* storage, CvRect...

    Delaunay三角形和Voronoi划分的迭代式构造

    #include "cv.h"
    #include "highgui.h"
    #include <stdio.h>
    #include <opencv2/legacy/legacy.hpp>//opencv2添加此头文件
    CvSubdiv2D* init_delaunay(CvMemStorage* storage,
        CvRect rect)
    {
        CvSubdiv2D* subdiv;
        subdiv = cvCreateSubdiv2D(CV_SEQ_KIND_SUBDIV2D, 
            sizeof(*subdiv),
            sizeof(CvSubdiv2DPoint),
            sizeof(CvQuadEdge2D),
            storage);
        cvInitSubdivDelaunay2D(subdiv, rect);
        return subdiv;
    }
    
    void draw_subdiv_point(IplImage* img, CvPoint2D32f fp, CvScalar color)
    {
        cvCircle(img, cvPoint(cvRound(fp.x), cvRound(fp.y)), 3, color, CV_FILLED, 8, 0);
    }
    
    void draw_subdiv_edge(IplImage* img, CvSubdiv2DEdge edge, CvScalar color)
    {
        CvSubdiv2DPoint* org_pt;
        CvSubdiv2DPoint* dst_pt;
        CvPoint2D32f org;
        CvPoint2D32f dst;
        CvPoint iorg, idst;
        org_pt = cvSubdiv2DEdgeOrg(edge);
        dst_pt = cvSubdiv2DEdgeDst(edge);
        if (org_pt && dst_pt)
        {
            org = org_pt->pt;
            dst = dst_pt->pt;
            iorg = cvPoint(cvRound(org.x), cvRound(org.y));
            idst = cvPoint(cvRound(dst.x), cvRound(dst.y));
            cvLine(img, iorg, idst, color, 1, CV_AA, 0);
        }
    }
    
    void draw_subdiv(IplImage* img, CvSubdiv2D* subdiv,
        CvScalar delaunay_color, CvScalar voronoi_color)
    {
        CvSeqReader reader;
        int i, total = subdiv->edges->total;
        int elem_size = subdiv->edges->elem_size;
        cvStartReadSeq((CvSeq*)(subdiv->edges), &reader, 0);
        for (i = 0; i < total; i++)
        {
            CvQuadEdge2D* edge = (CvQuadEdge2D*)(reader.ptr);
            if (CV_IS_SET_ELEM(edge))
            {
                draw_subdiv_edge(img, (CvSubdiv2DEdge)edge + 1, voronoi_color);
                draw_subdiv_edge(img, (CvSubdiv2DEdge)edge, delaunay_color);
            }
            CV_NEXT_SEQ_ELEM(elem_size, reader);
        }
    }
    
    void locate_point(CvSubdiv2D* subdiv, CvPoint2D32f fp, IplImage* img,
        CvScalar active_color)
    {
        CvSubdiv2DEdge e;
        CvSubdiv2DEdge e0 = 0;
        CvSubdiv2DPoint* p = 0;
        cvSubdiv2DLocate(subdiv, fp, &e0, &p);
        if (e0)
        {
            e = e0;
            do
            {
                draw_subdiv_edge(img, e, active_color);
                e = cvSubdiv2DGetEdge(e, CV_NEXT_AROUND_LEFT);
            } while (e != e0);
        }
        draw_subdiv_point(img, fp, active_color);
    }
    
    void draw_subdiv_facet(IplImage* img, CvSubdiv2DEdge edge)
    {
        CvSubdiv2DEdge t = edge;
        int i, count = 0;
        CvPoint* buf = 0;
        // count number of edges in facet
        do
        {
            count++;
            t = cvSubdiv2DGetEdge(t, CV_NEXT_AROUND_LEFT);
        } while (t != edge);
        buf = (CvPoint*)malloc(count * sizeof(buf[0]));
        // gather points
        t = edge;
        for (i = 0; i < count; i++)
        {
            CvSubdiv2DPoint* pt = cvSubdiv2DEdgeOrg(t);
            if (!pt) break;
            buf[i] = cvPoint(cvRound(pt->pt.x), cvRound(pt->pt.y));
            t = cvSubdiv2DGetEdge(t, CV_NEXT_AROUND_LEFT);
        }
        if (i == count)
        {
            CvSubdiv2DPoint* pt = cvSubdiv2DEdgeDst(cvSubdiv2DRotateEdge(edge, 1));
            cvFillConvexPoly(img, buf, count, CV_RGB(rand() & 255, rand() & 255, rand() & 255), CV_AA, 0);
            cvPolyLine(img, &buf, &count, 1, 1, CV_RGB(0, 0, 0), 1, CV_AA, 0);
            draw_subdiv_point(img, pt->pt, CV_RGB(0, 0, 0));
        }
        free(buf);
    }
    void paint_voronoi(CvSubdiv2D* subdiv, IplImage* img)
    {
        CvSeqReader reader;
        int i, total = subdiv->edges->total;
        int elem_size = subdiv->edges->elem_size;
        cvCalcSubdivVoronoi2D(subdiv);
        cvStartReadSeq((CvSeq*)(subdiv->edges), &reader, 0);
        for (i = 0; i < total; i++)
        {
            CvQuadEdge2D* edge = (CvQuadEdge2D*)(reader.ptr);
            if (CV_IS_SET_ELEM(edge))
            {
                CvSubdiv2DEdge e = (CvSubdiv2DEdge)edge;
                // left
                draw_subdiv_facet(img, cvSubdiv2DRotateEdge(e, 1));
                // right
                draw_subdiv_facet(img, cvSubdiv2DRotateEdge(e, 3));
            }
            CV_NEXT_SEQ_ELEM(elem_size, reader);
        }
    }
    
    void run(void)
    {
        char win[] = "source";
        int i;
        CvRect rect = { 0, 0, 600, 600 };
        CvMemStorage* storage;
        CvSubdiv2D* subdiv;
        IplImage* img;
        CvScalar active_facet_color, delaunay_color, voronoi_color, bkgnd_color;
        active_facet_color = CV_RGB(255, 0, 0);
        delaunay_color = CV_RGB(0, 0, 0);
        voronoi_color = CV_RGB(0, 180, 0);
        bkgnd_color = CV_RGB(255, 255, 255);
        img = cvCreateImage(cvSize(rect.width, rect.height), 8, 3);
        cvSet(img, bkgnd_color, 0);
        cvNamedWindow(win, 1);
        storage = cvCreateMemStorage(0);
        subdiv = init_delaunay(storage, rect);
        printf("Delaunay triangulation will be build now interactively.\n"
            "To stop the process, press any key\n\n");
        for (i = 0; i < 200; i++)
        {
            CvPoint2D32f fp = cvPoint2D32f((float)(rand() % (rect.width - 10) + 5),
                (float)(rand() % (rect.height - 10) + 5));
            locate_point(subdiv, fp, img, active_facet_color);
            cvShowImage(win, img);
            if (cvWaitKey(100) >= 0)
                break;
            cvSubdivDelaunay2DInsert(subdiv, fp);
            cvCalcSubdivVoronoi2D(subdiv);
            cvSet(img, bkgnd_color, 0);
            draw_subdiv(img, subdiv, delaunay_color, voronoi_color);
            cvShowImage(win, img);
            if (cvWaitKey(100) >= 0)
                break;
        }
        cvSet(img, bkgnd_color, 0);
        paint_voronoi(subdiv, img);
        cvShowImage(win, img);
        cvWaitKey(0);
        cvReleaseMemStorage(&storage);
        cvReleaseImage(&img);
        cvDestroyWindow(win);
    }
    int main(int argc, char** argv)
    {
        run();
        return 0;
    }

    这里写图片描述

    展开全文
  • 有一个“ Normalizer”对象,可以帮助您进行标准化非标准化。 并非总是需要这样做,但是如果您发现算法不起作用,请尝试对输入坐标进行规范化。 其中一些算法可通过以下教程形式获得: : 此处: : 该代码...
  • 实现内容:设置一副图像大小为600*600,图像像素值全为0,为黑色。在图像中Rect(100,100,400,400)的区域随机产生20个点,并...产生这些点集的Delaunay剖分和Voronoi图,并画出。程序#include #include #include <iost

    实现内容:

    设置一副图像大小为600*600,图像像素值全为0,为黑色。

    在图像中Rect(100,100,400,400)的区域随机产生20个点,并画出。

    产生这些点集的Delaunay剖分和Voronoi图,并画出。

    程序

    #include <opencv2/imgproc/imgproc.hpp>
    #include <opencv2/highgui/highgui.hpp>
    #include <iostream>
    
    using namespace cv;
    using namespace std;
    
    //随机产生一个点集
    vector<Point2f> generatePointSet(int n,Rect rect)
    {
        vector<Point2f> pointSet;
        for (int i = 0; i < n;i++)
        {
            Point2f fp((float)(rand() % (rect.width - 2*rect.x) + rect.x),
                (float)(rand() % (rect.height - 2*rect.y) + rect.y));
            pointSet.push_back(fp);
        }
        return pointSet;
    }
    
    //标记出点
    static void drawPoint(Mat& img, Point2f fp, Scalar color)
    {
        circle(img, fp, 3, color, CV_FILLED, 8, 0);
    }
    
    
    //画出点集
    static void drawPointSet(Mat& img, vector<Point2f> pointSet, Scalar color)
    {
        for (int i = 0; i < pointSet.size();i++)
        {
            drawPoint(img, pointSet[i], color);
        }
    }
    
    //画出剖分
    static void drawSubdiv(Mat& img, Subdiv2D& subdiv, Scalar delaunay_color)
    {
        vector<Vec6f> triangleList;
        subdiv.getTriangleList(triangleList);
        vector<Point> pt(3);
    
        for (size_t i = 0; i < triangleList.size(); i++)
        {
            Vec6f t = triangleList[i];
            pt[0] = Point(cvRound(t[0]), cvRound(t[1]));
            pt[1] = Point(cvRound(t[2]), cvRound(t[3]));
            pt[2] = Point(cvRound(t[4]), cvRound(t[5]));
            line(img, pt[0], pt[1], delaunay_color, 1, CV_AA, 0);
            line(img, pt[1], pt[2], delaunay_color, 1, CV_AA, 0);
            line(img, pt[2], pt[0], delaunay_color, 1, CV_AA, 0);
        }
    }
    
    //画出Voronoi图
    static void paintVoronoi(Mat& img, Subdiv2D& subdiv)
    {
        vector<vector<Point2f> > facets;
        vector<Point2f> centers;
        subdiv.getVoronoiFacetList(vector<int>(), facets, centers);
    
        vector<Point> ifacet;
        vector<vector<Point> > ifacets(1);
    
        for (size_t i = 0; i < facets.size(); i++)
        {
            ifacet.resize(facets[i].size());
            for (size_t j = 0; j < facets[i].size(); j++)
                ifacet[j] = facets[i][j];
    
            Scalar color;
            color[0] = rand() & 255;
            color[1] = rand() & 255;
            color[2] = rand() & 255;
            fillConvexPoly(img, ifacet, color, 8, 0);
    
            ifacets[0] = ifacet;
            polylines(img, ifacets, true, Scalar(), 1, CV_AA, 0);
            circle(img, centers[i], 3, Scalar(), CV_FILLED, CV_AA, 0);
        }
    }
    
    
    int main()
    {
        //创建点集
        Rect rect(100,100,400,400);
    
        Mat img(rect.size(), CV_8UC3);
        img = Scalar::all(0);
    
        vector<Point2f> pointset = generatePointSet(20,rect);
        Mat img_ptst = img.clone();
        drawPointSet(img_ptst,pointset,Scalar(0,255,0));
        imshow("Point set",img_ptst);
        imwrite("pointSet.jpg",img_ptst);
    
        //创建Delaunay剖分
        Subdiv2D subdiv(rect);
        for (int i = 0; i < pointset.size();i++)
        {
            subdiv.insert(pointset[i]);
        }
    
        //画出Delaunay剖分三角形
        Mat img_delaunay = img.clone();
        drawSubdiv(img_delaunay, subdiv, Scalar(255,255,255));
        imshow("Delaunay", img_delaunay);
        imwrite("delaunay.jpg", img_delaunay);
    
        //画出Voronoi图
        Mat img_voronoi = img.clone();
        paintVoronoi(img_voronoi, subdiv);
        imshow("Voronoi", img_voronoi);
        imwrite("voronoi.jpg", img_voronoi);
    
        waitKey(0);
        return 0;
    }

    结果

    这里写图片描述

    这里写图片描述

    这里写图片描述

    展开全文
  • 本博客前面讨论的Delaunay三角和Voronoi图都是针对平面上的情形,而球面上也可定义相应的概念。这些几何结构常常是很有用的,因为我们就住在地“球”上。 考虑这样一个问题:在中国,哪里是离国境最远的地方?经过...
  • 可以直接运行,实现自己添加点,生成delaunay和voronoi
  • OpenCV delaunay三角剖分和voronoi镶嵌的实例OpenCV delaunay三角剖分和voronoi镶嵌的实例 OpenCV delaunay三角剖分和voronoi镶嵌的实例 #include <opencv2/imgproc.hpp> #include <opencv2/highgui.hpp>...
  • 这些代码创建了初始的剖分,一个三角形包含一个特定的矩形框。 接下来,我们需要知道怎么插入点。这些点必须是32位float类型的,或者是带有整数坐标值的点(cv::Point)。在后面的案例中,它们会自动转换为float...
  • 学GIS的可以看看,手工添加点自动建立delaunay三角网和voronoi
  •  这篇文章将帮助我们了解Delaunay三角剖分和Voronoi图。 什么是Delaunay 三角剖分? 给定平面中的一组点,三角测量指的是将平面细分为三角形,将点作为顶点。在图1中,我们在左图像上看到一组界标...
  • 该程序包将Voronoi图构造实现为Delaunay三角剖分的对偶集。 它还受启发,实现了Delaunay三角剖分的质心镶嵌的构造。 例子 extern crate voronator; extern crate rand; use voronator :: VoronoiDiagram; use rand ...
  • 俄国数学家鲍里斯·尼古拉耶维奇·德劳内(Boris Nikolaevich Delaunay)用两种不同的方式拼写了他的姓氏-法劳德出版社的德劳内其他地方的德隆。很少有人拥有以他们命名的算法或概念。但是Delaunay有一个数学概念...
  • //使用CGAL编程实现点集的Delaunay三角剖分,voronoi图 //如果对Delaunay算法本身关注,请参考CGAL对Delaunay三角剖分的实现,CGAL对Delaunay三角剖分的实现是增量算法(Incremental) //本程序的重点在于
  • 在通用点类型上快速,强大地构造2D Delaunay和Voronoi镶嵌。 实现遵循描述的算法,并在(例如) 。 许可证:麻省理工学院。 错误报告,欢迎您! 它是如何工作的? 逐步插入指向有效Delaunay镶嵌的点,同时通过翻转...
  • 首先看一下 Delaunay 三角剖分。 在计算机几何图像显示上,为了追求效率,GPU只会绘制三角形。opengl 在绘制凸多边形的时候,也 是简单的将多边形化成三角形在渲染。当你给的是一个凹多边形的时候,问题就出现了...
  • Delaunay三角剖分和Voronoi图是对偶的,这意味着计算出了Delaunay剖分,Voronoi图也就确定了。直观感受一下: 重点来了,下面是OpenCV有关函数接口的理解和使用方法说明。 创建Delaunay 或者 Voronoi ...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 138
精华内容 55
关键字:

delaunay和voronoi