精华内容
下载资源
问答
  • Voronoi划分

    千次阅读 2017-06-05 13:55:04
    泰森多边形(Voronoi diagram)  荷兰气候学家A•H•Thiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法,即将所有相邻气象站连成三角形,作这些三角形各边的垂直平分线(如图a),于是每个...
    泰森多边形(Voronoi diagram)
    

           荷兰气候学家A•H•Thiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法,即将所有相邻气象站连成三角形,作这些三角形各边的垂直平分线(如图a),于是每个气象站周围的若干垂直平分线便围成一个多边形。用这个多边形内所包含的一个唯一气象站的降雨强度来表示这个多边形区域内的降雨强度,并称这个多边形为泰森多边形(如图b)。

    从几何角度来看,两基站的分界线是两点之间连线的垂直等分线,将全平面分为两个半平面,各半平面中任何一点与本半平面内基站的间隔都要比到另一基站间隔小。当基站数量在二个以上时,全平面会划分为多个包罗一个基站的区域,区域中任何一点都与本区域内基站间隔最近,是以这些个区域可以看作是基站的覆盖区域,我们将这种由多个点将平面划分成的图称为泰森多边形,又称为Voronoi 图。

    泰森多边形的特性是:
    1、每个泰森多边形内仅含有一个基站;
    2、泰森多边形区域内的点到相应基站的距离最近;
    3、位于泰森多边形边上的点到其两边的基站的距离相等。

    Voronoi图 定义:

    Voronoi图 ,又叫泰森多边形或Dirichlet图,它是由一组由连接两邻点直线的 垂直平分线组成的连续多边形组成。N个在平面上有区别的点,按照最邻近原则划分平面;每个点与它的最近邻区域相关联。Delaunay三角形是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形。Delaunay三角形的外接圆圆心是与三角形相关的Voronoi多边形的一个顶点。

    构造方法:

    Voronoi图是Delaunay三角剖分的对偶图,生成它的方法有很多 ,比较有名的有分治算法,扫描线算法,增量法等。但利用Delaunay三角剖分生成Voronoi图的算法是最快的。
    但最快的方法则是构造Delaunay三角剖分,再连接相邻三角形的外接圆圆心,即可以到Voronoi图。


    展开全文
  • 减量构造Voronoi划分(DCVT)是利用已有的Voronoi划分,局部重构删除节点后的Voronoi划分。详细分析删除一个节点对其他节点的Voronoi区域的影响,将DCVT的主要工作简化为求解一个简单的有界Voronoi划分;最后,提出...
  • 基于Voronoi划分的区域化模糊聚类遥感影像分割.pdf
  • 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;
    }

    这里写图片描述

    展开全文
  • 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
    

    最终结果图片如下:

    这里写图片描述

    展开全文
  • 将基于像素MRF分割方法拓展到基于地物目标几何约束的区域MRF分割,提出了一种基于区域和统计的纹理影像分割方法,其基本思想是利用Voronoi划分技术将影像域划分为若干子区域。在此基础上,采用二值高斯马尔科夫随机...
  • 基于Voronoi图预划分的LBS位置隐私保护方法
  • 算法首先根据已知AP(access point)位置对网络拓扑图进行Voronoi划分,使得每个终端与其最邻近的AP属于同一区域;然后提取每个Voronoi区域与相邻区域的交点作为备选网关位置,依次计算以每个备选网关作为根节点的网络...
  • 质心Voronoi镶嵌的非钝性网格划分
  • #资源达人分享计划#
  • 算法首先根据已知AP( access point)位置对网络拓扑图进行Voronoi划分,使得每个终端与其最邻近的AP属于同一区域;然后提取每个Voronoi区域与相邻区域的交点作为备选网关位置,依次计算以每个备选网关作为根节点的网络...
  • [voroimage,sub_image]=voronoizone(x,y,img) 对于图像平面上定义数量的点,voronoizone 计算图像空间上的 voronoi 图,并根据区域将图像划分为子图像。
  • Voronoi Noise

    千次阅读 2017-11-14 21:40:35
    一、Voronoi Noise  沃罗诺伊图(Voronoi Diagram,也称作Dirichlet tessellation,狄利克雷镶嵌)是由俄国数学家Georgy Fedoseevich Voronoi建立的空间分割算法,其空间划分思想来源于笛卡尔用凸域分割空间理论,...

    一、Voronoi Noise

      沃罗诺伊图(Voronoi Diagram,也称作Dirichlet tessellation,狄利克雷镶嵌)是由俄国数学家Georgy Fedoseevich Voronoi建立的空间分割算法,其空间划分思想来源于笛卡尔用凸域分割空间理论,也就是说,Voronoi图实际是一种空间划分方法,这种划分方法解决了这样一个问题:如何根据已知点划分空间,使得晶胞与点一一对应,并使晶胞内任取一点都与最近的已知点围在一起,或者换一种说法就是沃罗诺伊图基于一组特征点将空间分割成不同区域,而每一区域又仅包含唯一的特征点,并且该区域内任意位置到该特征点的距离比到其它的特征点都要更近。所以Voronoi图有以下特性(以二维平面为例):
    (1)每个V多边形内有一个特征点;
    (2)每个V多边形内点到该特征点距离短于到其它特征点的距离;
    (3)多边形边界上的点到生成此边界的特征点距离相等;
    (4)邻接图形的Voronoi多边形界线以原邻接界线作为子集。

    这里写图片描述

      Voronoi图作一种空间划分算法,由于其特性,在很多领域都有应用,例如用来规划电信信号塔选址以达到更好的覆盖和经济性;用来规划航线达到充分利用空间但又防范避免空中撞击风险;用来规划路线达到避开障碍物的目的。另外其在地理学、气象学、结晶学、航天、核物理学、机器人等领域具有广泛的应用。
    这里写图片描述

      对图形学来讲,Voronoi图的空间划分特性可以用来模拟物体破碎效果:
    这里写图片描述
      
      Voronoi图能形成独特的图案纹理,也常用在程序纹理生成中。

    二、Delaunay Triangulation

      Voronoi图定义简单,我们甚至可以使用手工做铅垂线的方式来作出给定特征点的Voronoi图,但理论上解决这个问题却比较难,直到Voronoi图提出来后25年,Delaunay才提出了解决该剖分完整而实用的方法,这就是著名的德劳内三角剖分(Delaunay Triangulation)。

    这里写图片描述

      Delaunay三角剖分具有以下特性:

    1、在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在并与其通视,即空圆特性;
    2、在构网时,总是选择最邻近的点形成三角形并且不与约束线段相交;
    3、形成的三角形网总是具有最优的形状特征,任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话,那么两个三角形6个内角中最小的角度不会变大;
    4、不论从区域何处开始构网,最终都将得到一致的结果,即构网具有唯一性。

      Delaunay三角剖分也有很多算法,网上相关资料很多,不再详述,本文参考文献部分也列出了部分Delaunay三角剖分方面的文章。
      Delaunay三角剖分是Voronoi图的对偶图,因此得到Delaunay三角剖分后就可以得到Voronoi图。

    三、算法步骤

      通过上述论述,我们将生成Voronoi图的算法概要步骤描述如下:

    1、正方形平面区域中有若干个特征点

    这里写图片描述

    2、基于特征点进行德劳内三角剖分
    这里写图片描述

    3、求取德劳内三角形处接圆圆心(蓝色点)
    这里写图片描述

    4、连接相邻外心(边界处则是发射一条射线)
    这里写图片描述

    5、得到Voronoi图
    这里写图片描述

    四、算法实现

      根据第三小节中的算法步骤,我们第一步生成了若干特征点:

    这里写图片描述

      第二步进行了德劳内三角剖分:
    这里写图片描述

      第三步,求取德劳内三角形外心,并连接外心得到Voronoi图:
    这里写图片描述

    这里写图片描述

      Voronoi是一种空间划分算法,因其划分后特殊的图案,我们也可以将其作为噪声来使用,其实上,Voronoi算法是可以生成噪声图形的,下图是我们使用cg实现的voronoi噪声图形。
    这里写图片描述

    这里写图片描述

    五、代码下载

      在算法实现中,C#代码参考了参考文献1的实现,Cg代码参考了参考文献7的实现。

      1、VS2015平台用C#实现的2D_VoronoiNoise Voronoi noise

      2、Unity2017.1.1f1平台用Cg实现的2D,3D Voronoise  Voronoise

    参考文献

    1、维诺图(Voronoi Diagram)分析与实现 维诺图(Voronoi Diagram)分析与实现
    2、三角剖分详解 三角剖分详解
    3、Delaunay三角剖分算法 Delaunay三角剖分算法
    4、三角剖分算法(delaunay) 三角剖分算法(delaunay)
    5、To Voronoi and Beyond To Voronoi and Beyond
    6、沃罗诺伊图 沃罗诺伊图
    7、voronoise voronoise

    展开全文
  • 结果可能是一张地图,就像这里显示的那样,其中地形被划分为最接近不同泉水的位置区域。 这样的地图经常出现在各种应用程序中,并冠以许多名称。对于数学家来说,它们被称为Voronoi图。 Constructing Voro
  • 原文额http://www.ams.org/samplings/feature-column/fcarc-voronoi
  • Voronoi Diagram

    2017-08-11 21:47:00
    N个在平面上有区别的点,按照最邻近原则划分平面;每个点与它的最近邻区域相关联。Delaunay三角形是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形。Delaunay三角形的外接圆圆心是与三角形相关的Voronoi...
  • Voronoi

    千次阅读 2018-11-21 23:01:08
    1.Voronoi图的定义 又叫泰森多边形或Dirichlet图,它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。 2.Voronoi图的特点 (1)每个V多边形内有一个生成元; (2)每个V多边形内点到该生成元距离短于到...
  • 这些通常用于划分为称为Voronoi细胞的区域。 参数 范围 类型 描述 points FeatureCollection。 输入点 例子 // generate some random point data var points = turf . random ( 'points' , 30 , { bbox : [ 50 ,...
  • voronoi

    千次阅读 2009-07-01 00:49:00
    N个在平面上有区别的点,按照最邻近原则划分平面;每个点与它的最近邻区域相关联。Delaunay三角形是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形。Delaunay三角形的外接圆圆心是与三角形相关的Voronoi...
  • CG-Voronoi Diagrams

    2019-03-13 21:28:37
    文章目录Voronoi Diagrams定义7.1 Definition and Basic Propertiestheorem 7.2证明Voronoi 图的复杂度theorem 7.3证明空圆theorem 7.47.2 Computing the Voronoi Diagram**海岸线**Observation 7.5lemma 7.6lemma ...
  • Voronoi图 摘要

    千次阅读 2018-05-27 22:53:43
    N个在平面上有区别的点,按照最邻近原则划分平面;每个点与它的最近邻区域相关联。Delaunay三角形是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形。Delaunay三角形的外接圆圆心是与三角形相关的Voronoi...
  • Voronoi图介绍

    万次阅读 2018-11-04 18:39:20
    1.Voronoi图的定义 又叫泰森多边形或Dirichlet图,它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。 2.Voronoi图的特点 (1)每个V多边形内有一个生成元;  (2)每个V多边形内点到该生成元距离短于...
  • voronoi多边形面积求算

    2017-05-06 16:38:38
    基于matlab的voronoi多边形顶点坐标及面积求算
  • 这里是维诺图的解释,因为我之前用的是egret写的一个三国游戏,对地图进行维诺图划分势力,所以用的文中最后一个Js的库。在游戏中引入了维诺图。 http://baike.baidu.com/view/6090879.htm ... ...
  • Voronoi图 | 泰森多边形

    2020-12-09 15:15:30
    Voronoi图,又叫泰森多边形、沃罗诺伊图或Dirichlet图,是一个关于空间划分的基础数据结构。 它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。 N个在平面上有区别的点,按照最邻近原则划分平面;每个...
  • 基于Unity实现的Voronoi

    千次阅读 2019-04-30 11:08:38
    也称作Dirichlet tessellation,狄利克雷镶嵌)是由俄国数学家Georgy Fedoseevich Voronoi建立的空间分割算法,其空间划分思想来源于笛卡尔用凸域分割空间理论,也就是说,Voronoi图实际是一种空间划分方法,...
  • Voronoi图及matlab实现

    千次阅读 2019-10-05 01:47:00
    [题外话:想一想真是...美赛时我预测求爱尔兰的充电站位置...N个在平面上有区别的点,按照最邻近原则划分平面;每个点与它的最近邻区域相关联。Delaunay三角形是由与相邻Voronoi多边形共享一条边的相关点连接而成...
  • 维诺图(Voronoi Diagram)分析与实现

    万次阅读 多人点赞 2016-08-18 19:50:19
    一、问题描述1.Voronoi图的定义又叫泰森多边形或Dirichlet图,它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。2.Voronoi图的特点(1)每个V多边形内有一个生成元; (2)每个V多边形内点到该生成元...
  • 然后基于分割后的各个区域,根据兴趣点的数量划分其为不同权重部分,并初步设计传感器位置。根据初步部署位置和权重,对不同权重位置构造Voronoi图填补覆盖空洞,直至所有空洞被填补完毕,并为了延长运行寿命设计了...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,147
精华内容 458
关键字:

voronoi划分