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

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

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

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

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

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

本文将着重介绍算法二。

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

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

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

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

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

第3期
冯仲科等 :Voronoi 图 — 泰森多边形法在角规测树中的应用
45
1 Voronoi 图及泰森多边形概念 Voronoi 图又称为 Dirichlet 镶嵌 ( tessellation ) ,
广泛应用 。
2 Voronoi 图 — 泰森多边形在角规测树中的实现
其概念由 Dirichlet 于 1850 年首先提出 ; 1907 后俄 国数学家 Voronoi 对此作了进一步阐述 , 并提出高 次方程化简 ; 1911 年荷兰气候学家 A1 H1 Thiessen 为提高大面积气象预报的准确度 , 应用 Voronoi 图 对气象观测站进行了有效区域划分
[3]
。角规在所有的测树工具中属于较优秀
的一种 ,在现代森林调查中 ,特别是在森林资源二类 清查中 ,发挥了积极作用 。 以往角规测树时 , 往往在林分内设置若干个角 规点 ,以所有角规点每公倾蓄积量算术平均值代替 整个林分平均蓄积量 , 从而估算出整个林分蓄积总
。Voronoi 图 - 泰森
多边形法 ,考虑了林分蓄积的空间分布不均匀特点 , 以各角规点的控制面积为权重 , 比算术平均法更合 理 ,蓄积总量估测精度更高 。
[4]
方法 以往人们大多采用求积仪求取各角规点的控制 面积 ,但是在考虑的林分较大 ,角规点也很多的情况 下 ,所组成的多边形面积小 、 个数多 , 用求积仪求面 积操作起来不方便
[7]
。因此在二维
空间中 ,Voronoi 图也称为泰森 ( Thiessen) 多边形 。 简单地说 ,Voronoi 图是平面的一个划分 , 其控 制点集 P = {p1 ,p2 , …,p n}中任意两点都不共位 ,且 任意四点不共圆
角规测树原理与技术方法 , 自奥地利林学家比 特里希 ( W ・ Bitterich ) 1947 年发明以来得到了广泛 的应用

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)。

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

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

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

泰森多边形法可以用于各种地理空间分析和计算，例如地理信息系统（GIS）中的空间插 值、地表水文模拟和地理统计分析等。
泰森多边形法公式
泰森多边形法（Thiessen Polygon Method），也称为Voronoi Diagram，是一种用于 将地理空间划分为不重叠的区域的方法。每个区域都由一个中心点和与该中心点最近的其他 点组成。
泰森多边形法的计算公式如下：
1. 给定一组点集P={p1, p2, ..., pn}，其中pi表示地理空间中的一个点。
2. 对于每个点pi，计算其与其他所有点pj之间的距离d(pi, pj)。
泰森多边形法公式
3. 对于每个点pi，找到与其距离最近的点pj，即min(d(pi, pj))。
4. 将地理空间划分为不重叠的区域，每个区域Байду номын сангаас由一个中心点pi和与该中心点最近的其他 点组成。这个区域就是泰森多边形。
5. 重复步骤3和4，直到所有点都被分配到一个泰森多边形中。

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域。

分别求出它们各自的维诺图，再将若干个维诺图合 起来。
维诺图的分治法
分别画出两部分 的维诺图
将平面中的点 分成两部分
将两个部分合起来
生成两个部分相交的边
相交的边的生成方法
取两边最顶上的点， 做垂直平分线
与某个多边形相交， 替换同一边的原来的 点，做垂直平分线。
重复以上步骤，最 终得到相交的边
相交的边的生成方法
Hale Waihona Puke 点插入法逐点插入法的基本思想就是：在现有的维诺 图的基础上插入一个新的点，根据新点与周围点的 关系，更新维诺图。
逐点插入法
确定新加入点所在 多边形。
做加入点与所在多边 垂直平分线会与其他多边形的边 相交，再做相交多边形点与新加 形点的垂直平分线 点的垂直平分线
重复上述步骤，直到没有与新的多边形的边相交为止。
维诺图生成算法
算法第八组
维诺图

Voronoi图，又叫泰森多边形或Dirichlet图。 N个在平面上有区别的点，将平面划分为N个区域， 每个点对应一个区域，区域内的每个点到该点的距 离是最近的。
维诺图生成算法
分治法 逐点插入法
三角形生长法
分治法
分治法的思想，就是将平面中的点分成若干部分，
（3）对三角形的三 个边分别搜索，到 边两个顶点距离和 最近的第三个点。 形成新的三角形。
谢谢！
逐点插入法
新插入的点 与其 周边的点重新划分了平 面，满足维诺图的定义， 而周围点外围的平面划 分没有改变，不受到影 响。
三角形生长法
（2）根据平面 中的散点，生 成Delaunay三 角网
（3）将相邻的 三角形的外接圆 圆心相连就是维 诺图
Delaunay三角网

泰森多边形的算法原理
泰森多边形算法（Tesselation Polygon algorithm）是一种计算机图形学中常用的算法，用于生成给定点集的凸多边形。

该算法的原理如下：
1. 输入：给定一个点集P，假设其共有n个点。

2. 随机选择一个点p0，作为初始点。

3. 计算点集P中所有点与p0的距离，并选择距离最远的点p1作为下一个点。

4. 构造线段(p0, p1)，并以该线段作为边界，将点集P分割成两个子集：S1（在线段左侧）和S2（在线段右侧）。

5. 对子集S1和S2递归地应用泰森多边形算法，分别得到S1和S2的分割多边形。

6. 将S1和S2的分割多边形合并成泰森多边形。

7. 输出：得到泰森多边形。

该算法的核心思想是不断选择距离最远的点，将点集划分成更小的子集，然后递归地应用算法，直到点集的规模缩小到只有3个点时，即得到三角形。

最后将所
有的三角形合并成一个凸多边形，即为泰森多边形。

该算法的时间复杂度为O(nlogn)，其中n为点集的大小。

由于泰森多边形算法是基于递归的，因此在实际应用中可能存在递归层数过多的问题，需要进行优化处理，例如使用快速排序等方法来减少递归层数。

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值之和。

泰森多边形
一、泰森多边形介绍
从几何角度来看，两基站的分界线是两点之间连线的铅直等分线，将全平面分为两个半平面，各半平面中任何一点与本半平面内基站的间隔都要比到另一基站间隔小。

当基站数量在二个以上时，全平面会划分为多个包罗一个基站的区域，区域中任何一点都与本区域内基站间隔最近，是以这些个区域可以看作是基站的覆盖区域，我们将这种由多个点将平面划分成的图称为泰森多边形，又称为Voronoi 图。

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

二、实现方法：
前提条件：安装7.5以上版本mapinfo
步骤：
1．生成基站图层
2．选择需要生成泰森多边形的基站
3．然后选择mapinfo的table菜单的Voronoi…
4．选择next
5．Create
6．Create
7．保存
8．Ok,生成泰森多边形，每个区域代表一个基站的覆盖范围
9．双击其中一个区域，可以统计此区域的面积，见total area字段。

泰森多边形原理泰森多边形原理，也称为Voronoi图或Dirichlet tessellation，是一种用于离散点集合的空间分割技术。

该原理可以用于识别关键的空间特征，例如网格状模式和地形分析。

下面我们来详细分步骤阐述泰森多边形原理。

第一步：构建二维离散点集泰森多边形原理需要构建一个离散点集。

这通常是通过采样空间来实现的，可以是二维图像中的像素网格，也可以是LIDAR传感器从点云数据中生成的几何点集。

第二步：用离散点集构建Voronoi图接下来，需要使用离散点集来构建Voronoi图。

Voronoi图以离散点的位置为中心，在离散空间内（通常是二维平面）形成一系列多边形，这些多边形的边缘是由离散点之间的等距线段形成的。

在二维平面内，可以使用Delaunay三角剖分算法，将每个离散点与其最近邻的点相连成三角形。

通过这种方式，可以构建出按距离分割空间的形态各异的Voronoi图。

第三步：构建泰森多边形通过Voronoi图的边缘，可以创建泰森多边形。

泰森多边形是每个Voronoi多边形的外接圆的闭合环。

这些多边形由离散点之间的等距线段形成，并且每个泰森多边形都是由两个或更多离散点共享的。

第四步：解决边界问题在具有边界的空间中，需要解决泰森多边形的边缘问题。

当点集合包含网格或模糊的边缘时，需要处理泰森多边形的边缘，以确保它们正确地限制了空间。

另外，在处理非点集边界时，需要使用预处理和/或后处理算法来确保边缘条包括在内，并且生成的泰森多边形具有正确的形状。

总结泰森多边形原理是一个十分重要的空间分析技术，可以用于地形分析、网格图形生成等很多领域。

通过四步骤的分解，我们可以大致了解使用泰森多边形原理所需要的基本流程。

当然，在实际应用中，还需要面对许多技术难题，需要不断进行改进和优化才能得到更好的结果。

r语言泰森多边形泰森多边形是一种常用于地理信息系统和空间分析的算法，用于将连续的点数据转换为连续的线数据。

它的名称来自于美国著名地理学家埃尔文·泰森。

泰森多边形的主要应用是在地理信息系统中，用于确定点数据的区域范围。

它可以帮助我们理解地理现象的分布规律，比如气象数据的空间分布、交通流量的分布等。

泰森多边形的原理是通过计算每个点到其他点的距离，然后根据距离确定每个点的邻近点，最终形成一系列多边形。

泰森多边形的计算过程并不复杂，但是它可以提供有关点数据的丰富信息。

首先，我们需要在地理信息系统中导入点数据，这些点可以是城市、气象站、交通节点等。

然后，通过计算点与其他点之间的距离，确定每个点的邻近点。

最后，根据邻近点的连接关系，将点数据转换为线数据，并生成泰森多边形。

泰森多边形的生成过程中，有几个关键的概念需要了解。

首先是邻近点，它是指与某个点距离最近的点。

其次是边界点，它是指在生成的多边形中，与其他多边形相邻的点。

最后是外围多边形，它是指包围所有多边形的最外层多边形。

泰森多边形的应用非常广泛。

在气象学中，我们可以利用泰森多边形来分析气象站观测数据的空间分布特征，从而推测未观测点的气象情况。

在交通规划中，我们可以利用泰森多边形来确定交通节点的服务范围，从而优化交通路线的设计。

在城市规划中，我们可以利用泰森多边形来分析人口分布的空间特征，从而合理规划城市的基础设施和公共服务。

值得注意的是，泰森多边形算法在应用过程中也存在一些限制。

首先，它假设点数据分布是均匀的，但实际上点数据往往呈现出聚集和离散的特点。

其次，泰森多边形算法只考虑了距离因素，没有考虑其他因素的影响。

因此，在实际应用中，我们需要结合其他数据和方法来进行综合分析。

总的来说，泰森多边形是一种常用的地理信息系统算法，可以将点数据转换为线数据，用于分析空间分布特征和优化规划设计。

它具有简单易用、信息丰富等特点，被广泛应用于气象学、交通规划、城市规划等领域。

2010年第7期福建电脑泰森多边形并行生成算法研究与实现申永源，曹布阳（同济大学软件学院上海201804）【摘要】：为了加快大规模二维平面点集的泰森多边形生成速度，本文设计并实现了一种并行优化算法。

该算法在保证与串行算法具有相同的精准度的条件下，利用串行算法的分治特征对其有效的进行了并行化优化。

经过实验证实，该算法在并行计算的环境下有效地提高了计算速度，减少了执行时间，并且获得了较高的计算加速比。

【关键词】：泰森多边形,Delaunay三角形,并行计算,三角剖分1、引言在城镇化与村镇建设动态监测的过程中，常常需要借助于泰森多边形[1](Thiessen Polygon，又被称为Dirichlet图、Voronoi 图)进行地理信息分析。

对于大规模的数据点，串行的泰森多边形的生成算法速度较慢，因而需要一种并行算法提高生成速度。

生成Delaunay三角形是Thiessen多边形生成的基础，二者可以通过一定规则互相转换[2]。

而生成Delaunay三角形具有多种算法，依照参考文献[3]的研究，在串行计算的条件下，Dwyer算法[4]无论对于均匀分布或者非均匀分布点集，在输入点数小于一定数量(216)的情况下，都相对于其它的算法具有较佳的性能。

并且其本身的分治特征也比较容易进行并行化，所以本文在此的基础上设计与改进并行化的泰森多边形生成算法。

2、算法流程一个较为实用的泰森多边形生成程序的算法流程如下所示：1.输入点集读取，并且去除点集中的重复点，计算MBR(最小外包矩形)2.在远离点集MBR的四角加入四个额外点3.Delaunay三角剖分4.将Delaunay三角形转换为泰森多边形5.将生成的泰森多边形裁切到合适的范围内6.输出最终结果由于输入点集存储于ESRI Shape文件中，其采取了四叉树的存储形式，因而MBR可以直接获得。

而去除重复点时如果采取数组作为查找存储结构，则不得不多次线性扫描数组找出重复点，数据量大时性能十分低下。