边界为简单多边形的离散点Delaunay三角剖分及可视化研究

简单多边形的Delaunay三角剖分,在计算机图形学及地学问题三维建模领域有着广泛地应用。本文提出了一种不需要判断多边形的凹凸性,直接对多边形建立最大凸包,在建立凸包的基础上建立Delaunay三角剖分的方法,设计了一个有效的数据结构。在剖分的基础上,去除三角形的内切圆圆心在多边形内的三角形即可得到满足需要的三角剖分。为了提高处理大规模数据的速度,实验中对数据进行了分块处理,提高了建网的速度。最后利用OpenGL技术实现了剖分后的地形三维显示。

The delaunay triangulation and visualization of discrete points forming simple polygon

The Delaunay triangulation of Simple Polygon,being basic methods of calculate geometry,has been widely applied to computer graphics,3D geographic modeling.This paper presents a method of establishing the biggest bulgy box direct from polygon without judging the polygon's concavo-convex,and designs an efficient data structure.By this way,we can obtain perfect triangulation by eliminating the triangulations that the centers of inscribed circles are within the polygon.To quickly deal with data,we utilize the method of data block processing in experimentation.Finally,we realize the 3D terrain representation using OpenGL.