Creation of Full Topological D-TIN Based on Multi-core Parallel

To take full advantage of the multi-core CPU to quickly create the vector terrain based on a large number of disperse points, this paper proposed a multi-core parallel algorithm to create the full topological D-TIN. Firstly, the quad-edge structure was chose to design the D-TIN data structure, and a series of function interfaces were developed to manipulate it; and given consideration to the data load balancing within threads and well-distributed in spatial, the method of coordinate sorting was used to divide the discrete points set into equal parts in logical; then, the serial construction algorithm of D-TIN was developed based on the periodicity of "creation-melting-creation" of the convex hull of the disperse point set and the divide-and-conquer algorithm; lastly, it was taken as the kernel of D-TIN parallel construction algorithm and Open MP as the model of multi-core parallel programming, then the parallel construction of D-TIN was achieved based on the stand-alone multi-core CPU. The experimental results show that the efficiency of this algorithm is significantly higher than that of the serial algorithm when the data is lager, and the D-TINs cre-ated by them are completely consistent; and there is negative correlation between the number of threads used and the total elapsed time.