泰森多边形(Voronoi图)生成算法

对于给定点集的泰森多边形的算法实现百度百科泰森多边形又叫冯洛诺伊图（Voronoi diagram），得名于Georgy Voronoi，是由一组由连接两邻点线段的垂直平分线组成的连续多边形组成。

泰森多边形是对空间平面的一种剖分，其特点是多边形内的任何位置离该多边形的样点（如居民点）的距离最近，离相邻多边形内样点的距离远，且每个多边形内含且仅包含一个样点。

由于泰森多边形在空间剖分上的等分性特征，因此可用于解决最近点、最小封闭圆等问题，以及许多空间分析问题，如邻接、接近度和可达性分析等。

特征：1.每个泰森多边形内仅含有一个离散点数据；2.泰森多边形内的点到相应离散点的距离最近；3.位于泰森多边形边上的点到其两边的离散点的距离相等。

泰森多边形图例：详细介绍见百度百科泰森多边形算法实现算法一：算法二：算法二是基于算法一的优化。

本文将着重介绍算法二。

1）算法二同样采用特征点以均匀的速度向外扩张的方式进行。

既然我们速度一定，那我们不妨设置为1，那么诸多特征点同时同步地向外扩张，说明在相遇时，相遇的特征点是本着相同的速度，以相同的时间到达的相遇地点（在这里是相遇的单元格），那么根据大众熟知的速度路程公式s=v*t，我们知道这两个相遇的特征点距离该相遇点的路程是相等的，也就是距离一样，说明该相遇点是这两个特征点两线的中点。

这就符合了泰森多边形的定义（是由一组由连接两邻点线段的垂直平分线组成的连续多边形组成）2）扩张的速度我们假定为1，基准的核心点，我们设定为特征点所在像素单元的几何中心。

我们规定，在以该特征点为圆心的辐射区域内的其他像素单元格的几何中心距离该特征点所在的几何中心的直线距离（根据勾股定理计算即可）小于或者等于某时间点该特征点以速度为1外扩的半径长度（即路程）时（也就是该像素单元格的大部分面积都包含在该时间点特征点辐射半径所划的圆中的时候），将该像素单元格赋值为特征点外扩运动中此时的时间点信息。

计算中心点：（其中红色点为核心特征点，黑色点为其外扩过程中的一个示例点）模拟泰森多边形由核心特征点外扩：（单元格中数值代表外扩到该单元格所用的时间）3）以步骤2）中介绍的方式，我们对所有特征点进行相应外扩，假设每个特征点都辐射满整张矩形区域，共辐射出与特征点数量等量的矩形表数量。

VORONOI（泰森多边形）功能制作BSC、TAC等边界图层方法
1、利用基站工参制作打点拓扑图，注意不要使用SEESTIE等插件生成的扇区图。

2、备份该图层，因为用excel直接做的拓扑图层，很多时候无法进行修改编辑，只是可读
模式，无法进行后面的操作。

3、打开复制的基站图层，使用MAPINFO/TABLEA/VORONOI功能（部分低版本和不完全版本
的MAPINFO无此功能）
无需特别选择，逐步执行下图
得到这种图层
4、利用mapinfo/table/combine objects using column选项，将多边形图层根据我们需要的内容进行合并，如TAC、TAL、BSC、MSC等，可以得到这些信息的分布图层。

逐步执行，注意到这一步，需要将method项都改为VALUE,否则默认SUM的话，生成的TAL 的图层的标识将会是TAL下所有小区的TAL值之和。

三维泰森多边形算法-回复什么是三维泰森多边形算法？三维泰森多边形算法是一种用于计算三维空间中一组点集的最小外包凸壳的算法。

泰森多边形是一个多边形，它将一组点集分割成一组不相交的三角形，使得这些三角形的外接圆包围了所有点集。

三维泰森多边形算法通过计算这些外接圆的半径和中心点，确定最小外包凸壳的形状。

三维泰森多边形算法的基本原理是使用一个递归的分而治之方法。

它通过将点集分为两个较小的子集，并分别计算它们的最小外包凸壳，然后将子集合并为一个更大的外包凸壳。

通过不断重复这个过程，最终得到整个点集的最小外包凸壳。

该算法的步骤如下：1. 输入一组三维空间中的点集P。

2. 如果P中的点数小于等于3个，则返回这些点作为最小外包凸壳的顶点。

3. 找到点集P中的一个点pivot，它的选择可能影响算法的性能。

一种常用的选择方法是选择z值最小的点。

4. 根据pivot将点集P分成两个子集P1和P2。

将P1中所有点的z值小于等于pivot的点放入P1，将其他点放入P2。

5. 递归地计算子集P1和P2的最小外包凸壳。

6. 合并子集P1和P2的最小外包凸壳，得到整个点集P的最小外包凸壳。

7. 返回最小外包凸壳作为算法的输出。

为了计算子集的最小外包凸壳，可以使用相同的算法步骤。

递归实现的关键在于确定pivot点和将点集分割为两个子集。

三维泰森多边形算法的时间复杂度为O(n log n)，其中n是点集P的大小。

这是因为每次递归都将点集分割为两个子集，每个子集的大小约为原点集的一半。

因此，算法的递归深度为O(log n)。

在每一层递归中，需要计算子集的最小外包凸壳，这需要O(n)的时间。

因此，总的时间复杂度为O(n log n)。

三维泰森多边形算法在计算机图形学、地理信息系统和计算几何等领域中有广泛的应用。

它可以用于计算三维物体的几何结构，并支持一些常见的操作，如点位置检测、线段相交以及点对之间的最近距离计算。

总结起来，三维泰森多边形算法是一种用于计算三维空间中一组点集的最小外包凸壳的算法。

voronoi多边形的生成原理
Voronoi多边形是由一组离散点生成的多边形。

它们的生成基于一个称为Voronoi图的基于点的分割方法。

这个方法的基本思想是将平面分割成一些相互不重叠的区域，每个区域都以一个离散点为中心，并且包含离该点最近的所有其他点。

生成Voronoi图的方法有很多种。

其中一种常用的方法是基于Fortune算法。

这个算法首先将点按照x坐标排序，然后将它们一一插入一个扫描线数据结构中。

在扫描线向右移动的过程中，每当遇到一个点时，就会在扫描线上创建一个新的边。

这个边会将扫描线上的点分成两个部分，并且将它们所属的区域分割开来。

当扫描线遇到两个点之间的空白区域时，它会在这里创建一个新的顶点。

这个顶点将作为边的交点，并且被添加到一个数据结构中。

这个数据结构，也就是Delaunay三角网，是由Voronoi图的双重图
组成的。

最后，Voronoi图可以通过将Delaunay三角网的三角形外接圆
相互连接形成。

这些连接形成了Voronoi多边形的顶点。

总之，Voronoi图是一种非常有用的工具，可以在各种应用中使用，包括地理信息系统、图形学、计算机视觉等。

了解其生成原理，可以帮助我们更好地理解其应用和工作原理。

- 1 -。

维诺图（VoronoiDiagram）分析与实现一、问题描述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）遍历结束，所有维诺边被找到，根据边画出维诺图。

泰森多边形及其特性
GIS和地理分析中经常采用泰森多边形进行快速插值，和分析地理实体的影响区域，是解决邻接度问题的又一常用工具。

荷兰气候学家A·H·Thiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法，即将所有相邻气象站连成三角形，作这些三角形各边的
垂直平分线，于是每个气象站周围的若干垂直平分线便围成一个多边形。

用这个多
边形内所包含的一个唯一气象站的降雨强度来表示这个多边形区域内的降雨强度，
并称这个多边形为泰森多边形。

如图，其中虚线构成的多边形就是泰森多边形。

泰
森多边形每个顶点是每个三角形的外接圆圆心。

泰森多边形也称为Voronoi图，或
dirichlet图。

泰森多边形
泰森多边形的特性是：
1、每个泰森多边形内仅含有一个离散点数据；
2、泰森多边形内的点到相应离散点的距离最近；
3、位于泰森多边形边上的点到其两边的离散点的距离相等。

泰森多边形可用于定性分析、统计分析、邻近分析等。

例如，可以用离散点的性质来描述泰森多边形区域的性质；可用离散点的数据来计算泰森多边形区域的数据；判断一个离散点与其它哪些离散点相邻时，可根据泰森多边形直接得出，且若泰森多边形是n边形，则就与n个离散点相邻；当某一数据点落入某一泰森多边形中时，它与相应的离散点最邻近，无需计算距离。

在泰森多边形的构建中，首先要将离散点构成三角网。

这种三角网称为Delaunay 三角网。

泰森多边形法公式
泰森多边形法（Tessellation Polygon Algorithm）是一种用于计算多边形面积的方法。

它基于将多边形划分为多个三角形，并计算每个三角形的面积，再将所有三角形的面积相加得到多边形的总面积。

计算泰森多边形的步骤如下：
1. 确定多边形的顶点坐标。

2. 找到多边形的一个顶点作为基准顶点。

3. 以基准顶点为中心，将多边形的其他顶点按逆时针排序。

4. 连接基准顶点与相邻的两个顶点，形成若干个三角形。

5. 计算每个三角形的面积，可以使用海伦公式或叉乘法计算面积。

6. 将所有三角形的面积相加，得到多边形的总面积。

需要注意的是，在计算三角形面积时，可以使用海伦公式：
面积= √(s * (s - a) * (s - b) * (s - c))
其中，s为三角形的半周长，a、b、c为三角形的三边长。

或者使用叉乘法：
面积 = 0.5 * |(x1*y2 - x2*y1) + (x2*y3 - x3*y2) + ... + (xn-1*yn - xn*yn-1) + (xn*y1 - x1*yn)|
其中，(x1, y1)、(x2, y2)、...、(xn, yn)为三角形的顶点坐标。

以上就是泰森多边形法的公式。

收稿日期：2011-05-31；定稿日期：2011-07-15基金项目：中国测绘科学研究院基本科研业务费基金资助项目（7771113）作者简介：张 娟（1988-），女，甘肃兰州人，硕士，主要研究方向为数字摄影测量与三维建模。

E-mail ：zhangjuanabcd@1 V oronoi 图的基础1.1 Voronoi 图的概念[1]如图1，L 是P 1P 2的垂直平分线，并将平面分成L 左和L 右两部分，位于L 左内的点P 左 具有特性：d (P 左, P 1)<d (P 左, P 2)，即L 左内的点是比平面上其他点更接近于P 1的点的集合，记做V (P 1): V (P 1) = H (P 1, P 2)，同理V (P 2) = H (P 2, P 1)。

增删点后的V oronoi 图生成算法张 娟1， 杜全叶2（1. 兰州交通大学，甘肃 兰州 730070；2. 中国测绘科学研究院，北京 100380）摘 要： V oronoi 图可广泛应用于模式识别、计算机图形学、计算机辅助设计、地理信息系统等领域。

利用V oronoi 图及其对偶图Delaunay 三角网构建的不规则三角网TIN 能充分地反映地形地貌特征，对TIN 的统一管理和动态调用可较好地应用到数字高程模型的建立中。

通过联机增量和减量算法来来实现增删点后的V oronoi 图的生成，具有能够动态修改点集、速度快、效率高等优势。

关 键 词：V oronoi 图；联机增量算法；减量算法；不规则三角网；数字地面模型 中图分类号：TP 391文献标识码：A 文 章 编 号：2095-302X (2013)01-0046-04The generating algorithm of Voronoi after adding and deleting pointsZhang Juan 1, Du Quanye 2( 1. Lanzhou Jiaotong University, Lanzhou Gansu 730070, China; 2. Chinese Academy of Surveying and Mapping, Beijing 100380, China )Abstract: V oronoi is also called Thiessen polygon, which is a continuous polygon made ofperpendicular bisectors by joining the two adjacent points. It is widely used in pattern recognition, computer graphics, computer aided design, geography information system and many other fields. A new approach of constructing TIN that represented terrain well was given based on V oronoi diagrams and Delaunay triangulation networks. It is easily to make full use of the management and loading of TIN in the establishment of DEM. The method of online incremental and reducing algorithm to realize the generation of V oronoi after adding and deleting points can change points actively, and it holds the superiorities of fast speed and high efficiency.Key words: V oronoi; Online adding algorithm; Deleting algorithm; TIN; DTM2013年 1月图 学 学 报 January 2013第34卷 第1期 JOURNAL OF GRAPHICS V ol.34 No.1LL左L右P左P右P1P2图1 V(P1)，V(P2)图示图2 n=6时的一种V oronoi图给定平面上n个点的点集S={P1，P2，…，P n}，定义V(P i)= H(P i，P j)，即V(P i)表示比其他点更接近P i的点的轨迹是n-1个半平面的交，它是一个不多于n-1条边的凸多边形域，称为关联于P i的V oronoi多边形或关联于P i的V oronoi域。