维诺图(Voronoi Diagram)分析与实现_voronoi图怎么分析 arcgis-程序员宅基地

技术标签: 图形学  维诺图  计算几何  voronoi图  

ref: https://blog.csdn.net/k346k346/article/details/52244123 

一、问题描述

1.Voronoi图的定义

又叫泰森多边形或Dirichlet图,它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。

2.Voronoi图的特点

(1)每个V多边形内有一个生成元; 
(2)每个V多边形内点到该生成元距离短于到其它生成元距离; 
(3)多边形边界上的点到生成此边界的生成元距离相等; 
(4)邻接图形的Voronoi多边形界线以原邻接界线作为子集。

3.Voronoi的应用

在计算几何学科中的重要地位,由于其根据点集划分的区域到点的距离最近的特点,其在地理学、气象学、结晶学、航天、核物理学、机器人等领域具有广泛的应用。如在障碍物点集中,规避障碍寻找最佳路径。

二、算法分析与设计

Voronoi图有着按距离划分邻近区域的普遍特性,应用范围广。生成V图的方法很多,常见的有分治法、扫描线算法和Delaunay三角剖分算法。

1.建立Voronoi图方法和步骤

本次实验采用的是Delaunay三角剖分算法。主要是指生成Voronoi图时先生成其对偶元Delaunay三角网,再找出三角网每一三角形的外接圆圆心,最后连接相邻三角形的外接圆圆心,形成以每一三角形顶点为生成元的多边形网。如下图所示。

这里写图片描述

建立Voronoi图算法的关键是对离散数据点合理地连成三角网,即构建Delaunay三角网。 
建立Voronoi图的步骤为: 
(1)离散点自动构建三角网,即构建Delaunay三角网。对离散点和形成的三角形编号,记录每个三角形是由哪三个离散点构成的。 
(2)计算每个三角形的外接圆圆心,并记录之。 
(3)遍历三角形链表,寻找与当前三角形pTri三边共边的相邻三角形TriA,TriB和TriC。 
(4)如果找到,则把寻找到的三角形的外心与pTri的外心连接,存入维诺边链表中。如果找不到,则求出最外边的中垂线射线存入维诺边链表中。 
(5)遍历结束,所有维诺边被找到,根据边画出维诺图。

2. Delaunay三角网的生成

建立Voronoi图的关键是Delaunay三角网的生成。Delaunay三角网的特性: 
(1)空圆性,任一三角形外接圆内部不包含其他点。 
(2)最接近:以最近临的三点形成三角形,且各线段(三角形的边)皆不相交。 
(3)唯一性:不论从区域何处开始构建,最终都将得到一致的结果。 
(4)最优性:任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话,那么两个三角形六个内角中最小的角度不会变大。 
(5)最规则:如果将三角网中的每个三角形的最小角进行升序排列,则Delaunay三角网的排列得到的数值最大。 
(6)区域性:新增、删除、移动某一个顶点时只会影响临近的三角形。 
(7)具有凸多边形的外壳:三角网最外层的边界形成一个凸多边形的外壳。 
Delaunay剖分是一种三角剖分的标准,实现它有多种算法。本次采用Bowyer-Watson算法,算法的基本步骤是: 
(1)构造一个超级三角形,包含所有散点,放入三角形链表。 
(2)将点集中的散点依次插入,在三角形链表中找出其外接圆包含 
插入点的三角形(称为该点的影响三角形),删除影响三角形的公共边,将插入点同影响三角形的全部顶点连接起来,从而完成一个点在Delaunay三角形链表中的插入。 
(3)根据优化准则对局部新形成的三角形进行优化。将形成的三角形放入Delaunay三角形链表。 
(4)循环执行上述第2步,直到所有散点插入完毕。

关键步骤2如下图所示: 
这里写图片描述

步骤3的局部优化的准则指的是: 
1.对新形成的三角形进行优化,将两个具有共同边的三角形合成一个多边形。 
2.以最大空圆准则作检查,看其第四个顶点是否在三角形的外接圆之内。 
3.如果在,修正对角线即将对角线对调,即完成局部优化过程的处理。

LOP (Local Optimization Procedure)处理过程如下图所示: 
这里写图片描述

3.数据结构的设计

本程序的实现采用C#面向对象语言实现,故数据结构的设计采用类的形式,具体有:

// 点:
    public class Site
    {
        public double x, y;
        public Site()
        { }
        public Site(double x, double y)
        {
            this.x = x;
            this.y = y;
        }
    }

// 边:
    public class Edge
    {
        public Site a, b;
        public Edge(Site a, Site b)
        {
            this.a = a;
            this.b = b;
        }
    }

// 三角形:
    public class DelaunayTriangle
    {
        Voronoi voronoi = new Voronoi();
        public Site site1, site2, site3;//三角形三点
        public Site centerPoint;//外界圆圆心
        public double radius;//外接圆半径
        public List<DelaunayTriangle> adjoinTriangle;//邻接三角形 
 
        public DelaunayTriangle(Site site1,Site site2,Site site3)
        {
            centerPoint = new Site();
            this.site1 = site1;
            this.site2 = site2;
            this.site3 = site3;
            //构造外接圆圆心以及半径
            voronoi.circle_center(centerPoint, site1, site2,site3,ref radius);
        }
    }
4. 算法复杂度分析

时间复杂度: 
Delaunay三角网的生成的时间复杂度: 
步骤一:构造一个超级三角形,O(1); 
步骤二:产找影响的三角形,构造新的三角形,O(1+2+…+n)=O(n2)O(1+2+…+n)=O(n2) 
步骤三:对新形成的三角形进行优化局部优化:O(n)。 
因此,整体时间复杂度是:O(1)+O(n2)+O(n)=O(n2)O(1)+O(n2)+O(n)=O(n2)。

从Delaunay三角网生成Voronoi图的时间复杂度: 
步骤一:构造构建Delaunay三角网,O(n2)O(n2); 
步骤二:计算三角形外接圆圆心,O(n); 
步骤三:寻找三角形三边相邻三角形:3O(n); 
步骤四:找到的维诺边存入链表中,画出维诺图:O(n)。 
因此,整体时间复杂度是O(n2)+O(n)+3O(n)+O(n)=O(n2)O(n2)+O(n)+3O(n)+O(n)=O(n2)。

三、实验结果

随机生成点:

这里写图片描述 

生成Delaunay三角形网:

这里写图片描述 

生成Voronoi图:

这里写图片描述

生成Voronoi图的可执行程序和源码工程文件见here

下面附上相关函数申明(详细代码见源码工程文件)。

//根据点集构造Delaunay三角形网
public void setDelaunayTriangle(List<DelaunayTriangle> allTriangle, List<Site> sites);
 
//根据Delaunay三角形网构造Voronoi图的边
public List<Edge> returnVoronoiEdgesFromDelaunayTriangles(List<DelaunayTriangle> allTriangle, List<Edge> voronoiRayEdgeList);
 
//根据三角形链表返回三角形所有的边
public List<Edge> returnEdgesofTriangleList(List<DelaunayTriangle> allTriangle);
 
//对新形成的三角形进行局部优化
public List<DelaunayTriangle> LOP(List<DelaunayTriangle> newTriList);
 
//判断边是否属于三角形
public bool isEdgeOnTriangle(DelaunayTriangle triangel,Edge edge);
 
//判断点是否属于三角形
public bool isPointOnTriangle(DelaunayTriangle triangle, Site site);
 
//将点与受影响的三角形三点连接,形成新的三个三角形添加到三角形链中
public void addNewDelaunayTriangle(List<DelaunayTriangle> allTriangles,DelaunayTriangle influenedTri,Site point);
 
//找出受影响的三角形的公共边
public List<Edge> findCommonEdges(List<DelaunayTriangle> influenedTriangles);
 
//找出两个三角形的公共边
public Edge findCommonEdge(DelaunayTriangle chgTri1, DelaunayTriangle chgTri2);
 
//判断插入点是否在三角形边上
public Site[] isOnEdges(DelaunayTriangle triangle,Site site);  
 
//判断点是否在三角形外接圆的内部
public bool isInCircle(DelaunayTriangle triangle, Site site) ;
 
//求三角形的外接圆心
public void circle_center(Site center, Site sites0, Site sites1, Site sites2, ref double radius) ;
 
//求两点之间距离
public double distance2Point(Site p,Site p2);
  1.  

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lihaidong1991/article/details/104014478

智能推荐

绘制贝塞尔曲线_如何在HTML5画布上绘制贝塞尔曲线-程序员宅基地

文章浏览阅读121次。绘制贝塞尔曲线 在上一篇文章中,我们使用几行代码在HTML5 canvas元素上创建了二次曲线 。 如果您在二次曲线演示页面上检查了JavaScript,您可能会注意到béziers的一些引用-贝塞尔曲线的近亲。 贝塞尔曲线是什么? 您可能已经看到在桌面发布和图形包中使用的贝塞尔曲线。 因此,让我们再次去WolframMathWorld看看方程。 我确定您了解这一点,但我感到有些恶心。..._路径采用basis曲线插值用html

js匀速动画&缓动动画_js动画不匀速-程序员宅基地

文章浏览阅读383次。文章目录匀速动画:效果展示代码部分html+cssjs 已封装 可直接调用缓动动画:动画效果代码部分html+cssjsf (已封装 可直接调用)匀速动画:在浏览器中,某一个盒子元素以稳定不变的速度向某个方向移动直到停止效果展示代码部分html+css<style> #box{ width: 100px; height: 100p..._js动画不匀速

马云:创业成功者没有固定模式_阿里三种模式都不是最早的,但确实成功的为什么-程序员宅基地

文章浏览阅读672次。 3月21日,在阿里巴巴网商论坛广州站的主题演讲上,阿里巴巴CEO马云的激情感染了在场的800名网商和网上同步直播的数百网友:你骄傲因为你很独特我记得前面几年都是我在讲,现在我终于可以不讲了,因为是我们的客户在讲这些经验。前段时间我去了两天日本,三天美国,前天刚回来。我想一开始我并不要说太多的东西,只是想和大家进行互动。我今天在这里,我不是什么电子商务专家,我只是很普通。我觉得很惭愧。一般人说你建_阿里三种模式都不是最早的,但确实成功的为什么

素数线性筛优化-程序员宅基地

文章浏览阅读145次。大致思路:  初始时,令2是素数,假设2之后奇数全部数都是素数(偶数不考虑会快一点点),从3开始每当找到一个素数时,显然这个素数乘上另外一个数之后都是合数,把这些合数都筛掉,直到最后一个奇数超出范围,剩下的都是奇数都是素数。  注:以下代码只为得到n以内的素数,所以执行后标记数组中的标记是不完整的,如函数1和2中的isPrime[4]=1显然是错的,不过这对prime数组没有影响..._线性筛空间优化

胶囊网络(Capsule Network)在文本分类中的探索-程序员宅基地

文章浏览阅读7.1k次,点赞2次,收藏16次。作者丨杨敏单位丨中国科学院深圳先进技术研究院助理研究员研究方向丨自然语言处理文本建模方法大致可以分为两类:(1)忽略词序、对文本进行浅层语义建模(代表模型包括 LDA,EarthMover’s distance等); (2)考虑词序、对文本进行深层语义建模(深度学习算法,代表模型包括 LSTM,CNN 等)。在深度学习模型中,空间模式(spatial patterns)汇总在较低层,有助于表示更高_capsnet在自然语言处理

solr客户端程序开发_solr solrinputdocument 设置field的类型-程序员宅基地

文章浏览阅读895次。使用solrj开发solr的java客户端程序注意:每个document中必须有一个id的field,id为string类型的。id一样时,后面加入的document会覆盖前面的document。id是document的唯一主键,当多次添加的时候,最后添加的相同id的域会覆盖前面的域document中的各个field可以在solr的schema.xml(%SOLR_HOME%/conf/s_solr solrinputdocument 设置field的类型

随便推点

maven搭建ssm框架(struts2、spring、mybatis )_spring,struts2,mybatis框架和ssm框架-程序员宅基地

文章浏览阅读650次。1:maven依赖 javax.annotation jsr250-api 1.0

jquery使用json_使用jQuery和JSON制作自己的网站徽章-程序员宅基地

文章浏览阅读81次。jquery使用json Flickr , Delicious和Twitter之类的服务都提供了可以添加到网站JavaScript徽章或小部件。 但是,如果您已经在自己的网站上使用了JavaScript框架(如jQuery),为什么还要添加更多JavaScript? 此外,制作自己的东西更有趣。 所有这些服务还提供JSON格式的Feed API,并且滚动自己的小部件很容易。 这是我立即使用jQu..._json徽章显示

jquery天气_带有jQuery的10个很棒的天气小部件-程序员宅基地

文章浏览阅读100次。jquery天气 今天,我们将向您分享我们认为很棒的jQuery Weather Widget插件的集合。 通过将这些插件集成到我们的网站中,我们可以轻松地向我们的网站访问者提供任何位置的天气信息。 这些插件使用天气信息提供商的API,例如Google和Yahoo!。 相关文章: jQuery Twitter小部件 1. WeatherSlider – jQuery动画天气小部件 ..._jq 天气插件

stm32实用篇3: 字符显示字库生成_stm32一键生成字库-程序员宅基地

文章浏览阅读5.6k次,点赞3次,收藏20次。字符显示字库生成_stm32一键生成字库

【linux安装下载安装JDK1.8】_linux jdk1.8下载-程序员宅基地

文章浏览阅读1.5k次。linux下载安装jdk_linux jdk1.8下载

apache-jmeter-2.12免安装版+jdk1.6.0_02配置_apache jemeter 免安装 jdk-程序员宅基地

文章浏览阅读3.2k次。1、配置jdk1.6.0_02先安装jdk到D:\Program Files\Java然后配置 右键计算机-》属性-》高级系统设置-》环境变量-》新建系统变量:(1)新建变量名:JAVA_HOME 变量值:D:\Program Files\Java\jdk1.6.0_02(2)新建变量名:classpath 变量值:D:\Program Files\Java\jdk1...._apache jemeter 免安装 jdk

推荐文章

热门文章

相关标签