计算几何课程设计报告 基于Voronoi图的简单多边形骨架提取
引言 骨架（Skeleton）又称中轴（Medial Axis），通常使用烧草模型和最大球（圆）模型来描述。骨架有着与原物体相同的拓扑和形状信息，是一种性能优良的几何特征，能够有效的描述物体，因此，在物体识别、路径规划、医学工程等领域多有应用。在物体识别等应用领域里，骨架提取的输入可以看作是空间内的点构成的多边形，对于多边形的骨架提取也成为了这些应用的基本技术，具有重要的应用意义。在此次课程设计中，我们实现了基于Voronoi 图的任意多边形的骨架提取，并提供了多边形骨架提取的演示界面。 多边形骨架 一个多边形的骨架，如上图所示，可以看作是由无数点对之间的骨架点组成的。两点间的骨架（skeleton）（等同于对中轴(medial axis)的求取）是到两点距离相等的点的轨迹，它是两点连线的垂直平分线，每一点所邻接的半平面是到其距离最小的点集相应地可扩展为离散点集的中轴定义。它是下列性质点的轨迹：其上任一点到最近两离散点距离相等，相应地也产生各点到其距离最小的点集；两线间的中轴是到两线距离相等的点的轨迹，它在两线相交时为角平分线——两线平行时为到两线距离——的平行线，每一线所邻接并以中轴为界的区域是到其距离最小的点集。一线和一点间的中轴是到该点(线距离相等的点的轨迹,它是以该点为焦点、该线为准线的抛物线。该点或线所邻接并以中轴为界的区域是到其距离最小的点集。 多边形骨架的几何算法 多边形骨架（中轴）的几何算法，是由多边形的某一点开始，找出参与中轴线计算的相应的线段与线段、点与线段、点与点，实质都转化为求某个特定点（中轴转折点）的问题，
一般图形Voronoi图的离散生成
————————————————————————————————作者：————————————————————————————————日期：
一般图形Voronoi图的离散生成-工程论文 一般图形Voronoi图的离散生成 刘欣LIU Xin （承德石油高等专科学校社科与数理部，承德067000）（Department of Social Science and Mathematics，Chengde Petroleum College，Chengde 067000，China） 摘要：由于一般图形形状和位置的任意性，一般图形Voronoi图往往比较复杂，难以将传统的构造法直接应用到一般图形Voronoi图的构造中。本文介绍了一般图形Voronoi图的离散构造法，并给出算法步骤及优势分析。Abstract：Because of the random graph shape and position，the general Voronoi graph is often more complex，it is difficult to construct the traditional method of direct application to the general structure of Voronoi graph. This paper introduces the construction method of general discrete Voronoi graph，and puts forword the algorithm steps and its advantages. 关键词：一般图形；Voronoi图；离散生成 Key words：general graphs；Voronoi diagram；discrete generation 中图分类号：TP391 文献标识码：A 文章编号：1006-4311（2015）19-0162-02 基金项目：河北省高等学校科学技术研究项，编号为QN20131159；承德市软科学研究计划项目（承德市公交线路的发展现状与优化分析）：201422123。作者简介：刘欣（1977－），女，河北承德人，承德石油高等专科学校社科数
泰森多边形(Voronoi图)生成算法
一、文档目的 本文描述了在geomodel模块中，生成泰森多边形所使用的算法。 二、概述 GIS和地理分析中经常采用泰森多边形进行快速插值，和分析地理实体的影响区域，是解决邻接度问题的又一常用工具。 荷兰气候学家A·H·Thiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法，即将所有相邻气象站连成三角形，作这些三角形各边的垂直平分线，于是每个气象站周围的若干垂直平分线便围成一个多边形。用这个多边形内所包含的一个唯一气象站的降雨强度来表示这个多边形区域内的降雨强度，并称这个多边形为泰森多边形。如图1，其中虚线构成的多边形就是泰森多边形。泰森多边形每个顶点是每个三角形的外接圆圆心。泰森多边形也称为Voronoi图，或dirichlet图。 图1 泰森多边形 泰森多边形的特性是： ●每个泰森多边形内仅含有一个离散点数据 ●泰森多边形内的点到相应离散点的距离最近 ●位于泰森多边形边上的点到其两边的离散点的距离相等 泰森多边形可用于定性分析、统计分析、邻近分析等。例如，可以用离散点的性质来描述泰森多边形区域的性质；可用离散点的数据来计算泰森多边形区域的数据；判断一个离散点与其它哪些离散点相邻时，可根据泰森多边形直接得出，且若泰森多边形是n边形，则就与n个离散点相邻；当某一数据点落入某一泰森多边形中时，它与相应的离散点最邻近，无需计算距离。 在泰森多边形的构建中，首先要将离散点构成三角网。这种三角网称为Delaunay三角网。 三、Delaulay三角形的构建 Delaunay三角网的构建也称为不规则三角网的构建，就是由离散数据点构建三角网，如图2，即确定哪三个数据点构成一个三角形，也称为自动联接三角网。即对于平面上n个离散点，其平面坐标为(x i，y i)，i＝1，2，…，n，将其中相近的三点构成最佳三角形，使每个离散点都成为三角形的顶点。 图2 Delaunay三角网
多边形的Voronoi图及其研究应用 Voronoi图是计算几何的重要几何结构之一，也是计算几何的重要研究内容之一。它按照对象集合中元素的最近属性将空间划分成许多单元区域。由于Voronoi图具有最近性、邻接性等众多性质和较完善的理论体系，如今已经在图形学、机械工程、虚拟现实、地理信息系统、机器人、图像处理、CAD等领域得到广泛应用，也是解决距离计算、碰撞检测、路径规划、Delaunay三角化、骨架计算、凸包计算以及可见性计算等计算几何其它问题的有效工具，因而受到人们的广泛关注。 目前，对Voronoi图的研究工作，从所在空间上来说，更多的集中在2维上；从生成对象上来说，更多的集中在离散点集上；在研究内容上来说，主要集中在其构造算法和相关应用研究上。对于多边形的Voronoi 图来说，则主要集中在多边形的内部Voronoi图的构造和相关应用上。 本论文对多边形的内部和外部Voronoi图的相关性质进行了较为深入的研究，并以此为基础研究解决在图形图像、虚拟现实等方面的研究工作中遇到的可见性计算、距离计算以及骨架计算等问题。 本论文的贡献主要有： 1、分析了M.Held给出的关于多边形内部Voronoi图顶点和边数的上界所存在的局限性：只适用于单边界多边形，对多边界多边形则不适用；给出了新的可适用于单边界和多边界多边形的内部Voronoi图顶点和边数上界估计；同时给出了多边形的外部Voronoi图顶点和边数上界估计；并对多边形的内部和外部Voronoi图的每一个Voronoi区域所包含的顶点和边数的平均值进行了估计。 2、提出了一种基于Voronoi图的计算多边形可见性的算法。我们用多边形的Voronoi图建立多边形的骨架，利用Voronoi图的邻近属性和最近特性等性质，沿着骨架在局部范围内确定可能产生遮挡的对象，从而确定多边形内任意一点的可见边。在预先建立一个多边形的骨架后，可在时间内确定多边形内任一观察点的可见边，其中为搜索过程中涉及到的Voronoi图中的骨架元素的数目。大部分情况和可见边数接近。本算法时间复杂度低，适用于任意多边形，且易于理解和编程实现。 3、给出了基于Voronoi图快速计算两个分离凸多边形距离的算法。算法利用两个分离凸多边形P和Q的外部Voronoi图的性质及其相互间的位置关系，采用二分法逐渐缩小搜索范围来快速查找最短距离对象对。算法首先根据多边形外部Voronoi图的性质确定最短距离对象对所在的初始搜索范围P(和Q(；然后取P(和Q(的中间顶点对象pm1和qm2，它们分别将P(，Q(平分成和，和四个子搜索范围，并根据pm1和qm2及其所在Voronoi 区域的位置关系，确定可删除的一个或两个子搜索范围；然后在剩余的子搜索范围继续用二分法查找最短距离
Voronoi图的构建和应用 侯玉昭 (南京航空航天大学机电学院，南京市，210016) 摘要：Voronoi图是计算几何中常用而又重要的几何结构，它有很强的实用价值。本文介绍了平面点集上的Voronoi图的一些生成方法，主要是矢量法和栅格法的原理与生成过程。其次就是V图在各个领域中的应用和分析了V图的一些优势特点。以此希望我国科研人员关注V图的研发工作。 关键词：V oronoi图；矢量法；栅格法；V图应用 Construction and application of V oronoi diagram Hou Yuzhao (College of Aerospace Engineering, Nanjing University of Aeronautics＆Astronautics, Nanjing, 210016, China;) Abstract：V oronoi graph is a common and important computational geometry in diagram geometry,it has a strong practical value.This paper introduces some generation method for planar point set on the V oronoi graph,it is mainly the principle and formation process of the vector method and the grid method.The second is the application of V graphs in various fields and analyzes some advantages of V graphs. We hope our researchers focus on R&D of V graph. Key words：V oronoi graph;Vector method;Grid method;Application of V oronoi graph 引言 Voronoi图的历史是相当古老的。许多不同的自然结构都与Voronoi图十分接近，并且这些结构曾经被很多早期的科学家甚至普通人注意过。早在1908年，俄国数学家G.Voronoi 在对二次型的研究中首先使用了这种图，后被计算机研究者称之为Voronoi图。1944年，笛卡尔使用了一种图来显示太阳系内部和外部物质的性质。尽管没有特殊的注解来解释那些图的结构，但实际上这些图已经十分接近今天我们所说的加权Voronoi图。Voronoi图在许多领域都在尝试它的应用，并取得了成功。如天文学家用来研究宇宙结构；考古学家用来识别新石器时代不同部落影响下的地区；气象学家在仪器分布不足时估算降雨（雪）量；城市规划者在城市中用来进行设施定位；生物学家用来研究毛细血管供应肌肉组织情况。这些研究表面上涉及完全不同的现象，但实际上都可以用Voronoi图的概念来解释。 近年来，Voronoi图已被纳入计算几何的范畴，成为计算几何的一个重要分支。随着计算机科学与技术的飞速发展，尤其是计算机在图像处理方面的广泛应用，使得计算几何的研究，越来越受重视并日益蓬勃发展起来。计算几何在计算机辅助设计、计算机图形学、数字图像处理、地理信息处理、机器人等许多领域都有重要应用。它已成功解决了找最近点，求最大空圆，求n个点的凸包，求最小树等问题。另外，Voronoi图在模式识别、生态研究、城市规划、最优化配置、物理学等许多领域也有广泛的应用[1]。 Voronoi图构建 V图有着按距离划分邻近区域的普遍特性，应用范围广。生成V图的方法很多，一般分为两种：矢量方法；栅格方法。 1.1矢量方法（基于GIS软件） 矢量方法生成V图大多是对点实体。方法分为：对偶生成法；增添法；部件合成法等。