Voronoi多边形和Delaunay三角剖分

骑猪看日落 2022-08-09 14:41 192阅读 0赞

今天对计算几何中的Voronoi多边形（即泰森多边形）和Delaunay三角剖分进行了学习，整理资料如下（摘自百度百科）。

泰森多边形法，美国气候学家A·H·Thiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法，即将所有相邻气象站连成三角形，作这些三角形各边的垂直平分线，于是每个气象站周围的若干垂直平分线便围成一个多边形。用这个多边形内所包含的一个唯一气象站的降雨强度来表示这个多边形区域内的降雨强度，并称这个多边形为泰森多边形。如图，其中虚线构成的多边形就是泰森多边形。泰森多边形每个顶点是每个三角形的外接圆圆心。泰森多边形也称为Voronoi图。

泰森多边形的特性：

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

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

定义 Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。

定义 Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。

要满足Delaunay三角剖分的定义，必须符合两个重要的准则：  
1、空圆特性：Delaunay三角网是唯一的（任意四点不能共圆），在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在。如下图所示：  
2、最大化最小角特性：在散点集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。从这个意义上讲，Delaunay三角网是“最接近于规则化的“的三角网。具体的说是指在两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。

下面是利用scipy中对Delaunay的实现的一个示例：

import numpy as np
    from scipy.spatial import Delaunay
    import matplotlib.pyplot as plt
    
    points = np.random.rand(10, 2) # 随机生成10个2维点
    tri = Delaunay(points)
    
    plt.triplot(points[:, 0], points[:, 1], tri.simplices.copy()) # 绘制三角格网
    plt.plot(points[:,0], points[:,1], 'o') # 绘制10这十个离散点
    
    plt.xlim(-0.05, 1.05)
    plt.ylim(-0.05, 1.05)
    
    plt.show()

运行结果：

![Delaunay三角剖分][Delaunay]

[Delaunay]: /images/20220731/640e5854f6f04990a34c6dec9f72b251.png