Building tin with point cloud

One 、 Algorithm principle

1、 Principle overview

   Irregular Triangulation （TriangulatedlrregularNetwok, abbreviation TIN）, It is a triangular network model composed of discrete non-uniform points in space . The digital elevation model based on Irregular Triangulation is composed of non intersecting 、 A series of connected triangles that do not overlap to describe a toposurface , The elevation value of any point on the triangular surface can be obtained by the weighted average interpolation of the elevation values of nearby triangular vertices .
   Irregular Triangulation TIN The representation arranges all terrain points together with the representative elevation values by using a certain optimization combination algorithm , Any terrain point falls on the edge of each triangle 、 Inside a vertex or triangle , They connect with each other to form a triangle . Commonly used Delaunay Triangulation representation , As shown in the figure below . among ,Delaunay Triangulation has three basic characteristics ：①Delaunay Triangulation is the only ;② No point exists inside the circumscribed circle of a triangle ;③Delaunay The divided triangulation is the triangulation closest to the regular shape .

Delaunay Triangulation   TIN The model has the following advantages ：① For digital terrain TIN Model to represent , The size and shape of terrain triangulation can be determined by the location of sampling points 、 Density, distribution characteristics and other factors , Triangular patches of different shapes can be formed , Used to describe different types of terrain features ;② Irregular Triangulation TIN The model is good at depicting the detailed features of the terrain , Its triangulation network can automatically adjust the distribution and density of sampling points according to the characteristics and complexity of terrain , Terrain accuracy can be reduced in areas with relatively flat terrain , Reduce the density of tin , Thus reducing the burden of data management ;③ From the perspective of expressing terrain information ,TIN It can express the surface features of terrain with different levels of resolution ;④ And regular grid Grid The model compares , At a certain resolution ,TIN The model is more efficient in data volume and data storage and requires less storage space , At the same time, the description of terrain features is more accurate and detailed , That is, usually choose TIN To express more complex terrain . Of course ,TIN The model also has drawbacks ,TIN Although it can reduce the redundancy of data , But the storage method is very complicated .

2、 reference

[1] Jin Chun . 3D modeling and visualization of mountain highway tunnel [D]. Shandong University ,2018.

Two 、 Code implementation

To be updated