Delaunay三角网生成算法

时间:2024-03-20 16:49:32

实验要求

  1. 完成角度判别法生成Delaunay三角网的算法。在给定矩形范围(客户区大小的80%)内随机生成一系列随机点(不少于100个),根据角度判别法生成Delaunay三角网,并在屏幕上绘制。
  2. 根据所生成的点,生成对应的Voronoi图并绘制。
  3. 对生成的Voronoi图进行四色填充。(选做)

算法简介

  1. Delaunay三角网和Voronoi图
    1. Voronoi图与Delaunay三角网
      不规则三角网(Triangulated Irregular Network,简称TIN)。数学上的定义,假设S={p1,p2,...,pn},n3表示欧式平面R2上的一个点集,并且任意三点不共线,四点不共圆,d(pi,pj)表示点pipj间的欧式距离,则区域V={xR2|d(x,pi)d(x,pj),i,j=1,2,...,nij}称为平面点集S的Voronoi多边形,又称为Voronoi图。平面上的Voronoi图也可以看做是点集S中的每个点作为生长核,以相同的速率向外扩张,直到彼此相遇为止在平面上所形成的图形。除最外层的点形成开放的区域外,其余每个点都形成一个凸多边形。
    2. Delaunay三角网的两个重要性质
      空外接圆性质:在由点集S构成的Delaunay三角网中,每个三角形的外接圆均不包含点集S中的其他任意点,即任何一个Delaunay三角形的外接圆不包含其他任何点。
      最大的最小角性质:在由点集S所构成的三角网中,Delaunay三角网中三角形的最小角度是最大的,一个简明的解释:2个相邻三角形构成的凸四边形的对角线在相互交换后,6个内角的最小角不再增大。
  2. 角度判别法生成Delaunay三角网
    输入:点集S
    输出:Delaunay三角网
    算法过程:
    1. 任取一点,求与之相连的最短边。从点集S中任选一点作为起点p1,寻找与其距离最近的点作为第二点p2
    2. 初始化队列数据。置一空队列Q,存储扩展边。在连线p1p2右侧进行扩展,得到扩展点p3,在连线p2p1右侧进行扩展,得到扩展点p4,记录扩展得到的两个三角形(扩展失败则不记录)。将p1p3p3p2p2p4p4p1加入队列Q(扩展失败的边不加入队列)。(扩展方法为,在连线的右侧寻找与其构成最大夹角的第三点,若其右侧没有满足条件的点,则这条边扩展失败)。
    3. 进行循环,直至队列Q为空。每次循环从队列中取出一条边pipj,在其右侧进行扩展,得到扩展点pk,记录扩展得到的三角形,并将新生成的两条边pipkpkpj加入队列Q。
    4. 算法结束。
  3. 由Delaunay三角网生成Voronoi图
    根据已生成的Delaunay三角网,可以生成对应的Voronoi图。
    输入:点集S构成的Delaunay三角网
    输出:点集S构成的Voronoi图
    算法过程:

    1. 对三角形集合进行遍历,记录每个三角形是由哪三个点构成的。
    2. 计算每个三角形的外接圆圆心,并记录。
    3. 遍历三角形集合,寻找与当前三角形t三边共边的相邻三角形tAtbtc
    4. 如果找到对应边的邻接三角形,则把寻找到的三角形的外心与t的外心连接,存入Voronoi边集合中。如果找不到,则求出该边所对应的中垂线射线与边缘的交点,将外心与其连线存入Voronoi边集合中。
    5. 遍历结束。
  4. 四色填充参考
    http://www.cnblogs.com/moondark/p/3594188.html

实验结果参考图

Delaunay三角网生成算法
图中绿色点线为Delaunay三角网,红色实线为Voronoi图。