狄洛尼三角网(TIN).ppt

Bowyer-Watson Algorithm： Description of the algorithm Step 1 Define a bounding box that contains all the points. This step is needed to initialise the algorithm by defining an initial triangulation and associated topology. Step 2 Introduce a new point anywhere within the bounding box which, by construction, contains all the points. Step 3 Find the first triangle that fails the Delaunay test (Definition. 1 section 2.5.2 , Definition 3 section 2.5.4). * * 三角网（Triangulations） （TIN, triangulated irregular network） 通过从不规则分布的数据点生成的连续三角面来逼近地形表面 建立DEM的重要手段 优点：在某一分辨率下能用更少的空间和时间更精确的表示复杂的面，特别是当包含一些不连续特征，如断层或陡崖时，三角网能更好地顾及这些特征，更合理地表达表面形态。 reasons to try to describe a geo-model using a three dimensional triangulation : 1.the generation algorithm is fully automatic and therefore objective 2.space is uniquely defined and cells are spatially indexed 3.size of elements can be adjusted locally as a function of the complexity of the model 4.the model can be easily edited manually 5.topology is derived from neighbourhood relationships 6.constrained triangulation means we can use vectors or surface constraints (i.e. to represent trends) reasons to try to describe a geo-model using a three dimensional triangulation : 7.use of triangular elements is the perfect choice for visualisation since this is the basis for rendering techniques 8.good accuracy and approximation compared to block models 9.integral properties are efficient and easy to calculate 10.we can easily extract from the 3D solid representation of an object the 3D triangulated surface which is its boundary 11.spatial searches and relational queries are easy to implement 12.good performance of Boolean operations 生成三角网的基本要求： 1 三角网是唯一的； 2 力求最佳的三角形几何形状，每个三角形尽量接近等边三角形； 3 保证最邻近的点构成三角形，即三角形的边长之和最小 狄洛尼三角网（Delaunay Triangulation） 为相互邻接且互不重叠的三角形的集合，每一三角形的外接圆内不包含其它的点。 连接方式 Dirichlet (Dirichlet, 1850)提出一个方法，系统地将一个区域分解为一系列封闭的凸多边形。 对于平面的点集，Dirichlet棋盘格局赋予每个点一个区域，最接近于这个点。整个区域由