python实现维诺图_维诺图(Voronoi Diagram)分析与实现-程序员宅基地

技术标签: python实现维诺图  

一、问题描述

1.Voronoi图的定义

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

2.Voronoi图的特点

(1)每个V多边形内有一个生成元;

(2)每个V多边形内点到该生成元距离短于到其它生成元距离;

(3)多边形边界上的点到生成此边界的生成元距离相等;

(4)邻接图形的Voronoi多边形界线以原邻接界线作为子集。

3.Voronoi的应用

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

二、算法分析与设计

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

1.建立Voronoi图方法和步骤

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

183233161_1_2020021902040934

建立Voronoi图算法的关键是对离散数据点合理地连成三角网,即构建Delaunay三角网。

建立Voronoi图的步骤为:

(1)离散点自动构建三角网,即构建Delaunay三角网。对离散点和形成的三角形编号,记录每个三角形是由哪三个离散点构成的。

(2)计算每个三角形的外接圆圆心,并记录之。

(3)遍历三角形链表,寻找与当前三角形pTri三边共边的相邻三角形TriA,TriB和TriC。

(4)如果找到,则把寻找到的三角形的外心与pTri的外心连接,存入维诺边链表中。如果找不到,则求出最外边的中垂线射线存入维诺边链表中。

(5)遍历结束,所有维诺边被找到,根据边画出维诺图。

2. Delaunay三角网的生成

建立Vor

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

智能推荐

vue引入原生高德地图_前端引入原生地图-程序员宅基地

文章浏览阅读556次,点赞2次,收藏3次。由于工作上的需要,今天捣鼓了半天高德地图。如果定制化开发需求不太高的话,可以用vue-amap,这个我就不多说了,详细就看官网 https://elemefe.github.io/vue-amap/#/zh-cn/introduction/install然而我们公司需要英文版的高德,我看vue-amap中好像没有这方面的配置,而且还有一些其他的定制化开发需求,然后就只用原生的高德。其实原生的引入也不复杂,但是有几个坑要填一下。1. index.html注意,引入的高德js一定要放在头部而_前端引入原生地图

ViewGroup重写大法 (一)-程序员宅基地

文章浏览阅读104次。本文介绍ViewGroup重写,我们所熟知的LinearLayout,RelativeLayout,FrameLayout等等,所有的容器类都是ViewGroup的子类,ViewGroup又继承View。我们在熟练应用这些现成的系统布局的时候可能有时候就不能满足我们自己的需求了,这是我们就要自己重写一个容器来实现效果。ViewGroup重写可以达到各种效果,下面写一个简单的重写一个Vi..._viewgroup 重写

Stm32学习笔记,3万字超详细_stm32笔记-程序员宅基地

文章浏览阅读1.8w次,点赞279次,收藏1.5k次。本文章主要记录本人在学习stm32过程中的笔记,也插入了不少的例程代码,方便到时候CV。绝大多数内容为本人手写,小部分来自stm32官方的中文参考手册以及网上其他文章;代码部分大多来自江科大和正点原子的例程,注释是我自己添加;配图来自江科大/正点原子/中文参考手册。笔记内容都是平时自己一点点添加,不知不觉都已经这么长了。其实每一个标题其实都可以发一篇,但是这样搞太琐碎了,所以还是就这样吧。_stm32笔记

CTS(13)---CTS 测试之Media相关测试failed 小结(一)_mediacodec框架 cts-程序员宅基地

文章浏览阅读1.8k次。Android o CTS 测试之Media相关测试failed 小结(一)CTSCTS 即兼容性测试套件,CTS 在桌面设备上运行,并直接在连接的设备或模拟器上执行测试用例。CTS 是一套单元测试,旨在集成到工程师构建设备的日常工作流程(例如通过连续构建系统)中。其目的是尽早发现不兼容性,并确保软件在整个开发过程中保持兼容性。CTS 是一个自动化测试工具,其中包括两个主要软件组件:CTS tra..._mediacodec框架 cts

chosen.js插件使用,回显,动态添加选项-程序员宅基地

文章浏览阅读4.5k次。官网:https://harvesthq.github.io/chosen/实例化$(".chosen-select").chosen({disable_search_threshold: 10});赋值var optValue = $(".chosen-select").val();回显1.设置回显的值$(".chosen-select").val(“opt1”);2.触发cho..._chosen.js

C++ uint8_t数据串如何按位写入_unit8_t 集合 赋值 c++-程序员宅基地

文章浏览阅读1.9k次。撸码不易,网上找不到,索性自己写,且撸且珍惜!void bitsWrite(uint8_t* buff, int pos, int size, uint32_t value){ uint32_t index[] = { 0x80000000, 0x40000000, 0x20000000, 0x10000000, 0x8000000, 0x4000000, 0x2000000, 0x1000000, 0x800000, 0x400000, 0_unit8_t 集合 赋值 c++

随便推点

Javaweb框架 思维导图_javaweb框架图-程序员宅基地

文章浏览阅读748次。javaweb知识点_javaweb框架图

adb的升级与版本更新_adb iptabls怎么升级-程序员宅基地

文章浏览阅读1.1w次,点赞3次,收藏16次。adb是没有自动升级的命令的,如果想要更新adb的版本,我们可以在网上找到自己想要的版本进行更新给大家提供几个版本https://pan.baidu.com/s/1yd0dsmWn5CK08MlyuubR7g&shfl=shareset 提取码: 94z81、下载解压后我们可以找到下面几个文件,并复制2、找到adb安装的文件夹下的platform-tools文件夹,我这里是..._adb iptabls怎么升级

微信苹果版删除所有的聊天记录的图文教程_mac微信怎么删除聊天列表-程序员宅基地

文章浏览阅读3.8k次。很多用户可能都知道怎么在Windows系统上删除微信的聊天记录,那么苹果电脑上的微信软件怎么删除所有的聊天记录呢?下面小编就专门来给大家讲下微信mac版删除所有的聊天记录的图文教程。点击后会弹出提示窗口,点击这里的确认按钮就可以将其清理掉了。在这里选择要清理的数据,然后点击下方右边的清理按钮就行了。在mac上打开微信后,点击左下角的横线图标。然后再点击这里的管理微信聊天数据按钮。打开了设置窗口,点击上方的“通用”。在这里点击下方的前往清理按钮。点击弹出菜单里的“设置”。_mac微信怎么删除聊天列表

【报错笔记】数据类型转换时报错:Request processing failed;nested exception is java.lang.NumberFormatException:..._request processing failed; nested exception is jav-程序员宅基地

文章浏览阅读7.7k次。数据类型转换时报错:Request processing failed;nested exception is java.lang.NumberFormatException:For input String “20151512345”报错原因:数字格式异常,接着后面有 For input string: “201515612343” 提示,这就告诉我们你当前想把 “201515612343” 转换成数字类型时出错了。解决方案:使用2015151612343这个数字太大了,所以直接使用string_request processing failed; nested exception is java.lang.numberformatexcepti

qml 自定义消息框_Qt qml 自定义消息提示框-程序员宅基地

文章浏览阅读387次。版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。本文链接:https://blog.csdn.net/a844651990/article/details/78376767Qt qml 自定义消息提示框QtQuick有提供比较传统的信息提示框MessageDialog,但是实际开发过程并不太能满足我们的需求。下面是根据controls2模块中..._qml 自定义 messagedialog

Redis.conf 默认出厂内容_默认出厂的原始redis.conf文件全部内容-程序员宅基地

文章浏览阅读599次。# Redis configuration file example.## Note that in order to read the configuration file, Redis must be# started with the file path as first argument:## ./redis-server /path/to/redis.conf # Note on units: when memory size is needed, it is pos._默认出厂的原始redis.conf文件全部内容

推荐文章

热门文章

相关标签