Application of the Delaunay triangulation interpolation in distortion XRII image

To alleviate the distortion of XRII X-ray image intensifier images in the C-arm CT computer tomography imaging system an algorithm based on the Delaunay triangulation interpolation is proposed.First the causes of the phenomenon the classical correction algorithms and the Delaunay triangulation interpolation are analyzed.Then the algorithm procedure is explained using flow charts and illustrations. Finally experiments are described to demonstrate its effectiveness and feasibility. Experimental results demonstrate that the Delaunay triangulation interpolation can have the following effects.In the case of the same center the root mean square distances RMSD and standard deviation STD between the corrected image with Delaunay triangulation interpolation and the ideal image are 5.760 4 ×10 -14 and 5.354 2 ×10 -14 respectively.They increase to 1.790 3 2.388 8 2.338 8 and 1.262 0 1.268 1 1.202 6 after applying the quartic polynomial model L1 and model L2 to the distorted images respectively.The RMSDs and STDs between the corrected image with the Delaunay triangulation interpolation and the ideal image are 2.489 × 10 -13 and 2.449 8 ×10 -13 when their centers do not coincide. When the quartic polynomial model L1 and model L2 are applied to the distorted images they are 1.770 3 2.388 8 2.338 8 and 1.269 9 1.268 1 1.202 6 respectively.

Redesign of a conformal boundary recovery algorithm for 3D Delaunay triangulation

Boundary recovery is one of the main obstacles in applying the Delaunay criterion to mesh generation. A stan- dard resolution is to add Steiner points directly at the intersection positions between missing boundaries and triangulations. We redesign the algorithm with the aid of some new concepts, data structures and operations, which make its implementation routine. Furthermore, all possible intersection cases and their solutions are presented, some of which are seldom discussed in the litera- ture. Finally, numerical results are presented to evaluate the performance of the new algorithm.

COMBINED DELAUNAY TRIANGULATION AND ADAPTIVE FINITE ELEMENT METHOD FOR CRACK GROWTH ANALYSIS

The paper presents the utilization of the adaptive Delaunay triangulation in the finite element modeling of two dimensional crack propagation problems, including detailed description of the proposed procedure which consists of the Delaunay triangulation algorithm and an adaptive remeshing technique. The adaptive remeshing technique generates small elements around crack tips and large elements in the other regions. The resulting stress intensity factors and simulated crack propagation behavior are used to evaluate the effectiveness of the procedure. Three sample problems of a center cracked plate, a single edge cracked plate and a compact tension specimen, are simulated and their results assessed.

Introducing tree neighbouring relationship factors in forest pattern spatial analysis:weighted Delaunay triangulation method

It is important to quantify and analyze forest spatial patterns for studying biological characteristics,population interaction and the relationship between the population and environment.In this study,the forest spatial structure unit was generated based on the Delaunay triangulation model(DTM),and the weights were generated using the comprehensive values of the tree diameter at breast height,total height and crown width.The distance between neighbors determined by the DTM was weighted to transform the original coordinates of trees into logical coordinates.Then,a weighted spatial pattern(WSP)was developed.After weighting,the neighboring trees were replaced,the replacement ratio was 38.3%,and there was 57.4%of the central tree.Correlation analysis showed that the uniform angle index of the WSP was significantly correlated with the tree size standard deviation under uniformity(r=0.932)and randomness(r=0.711).The DTM method not only considers the spatial distance between trees,but also considers the non-spatial attributes of trees.By changing the spatial topological relation between trees,this method further improves the spatial structure measurement of forest.

DELAUNAY TRIANGULATION METHOD OF CURVED SURFACES BASED ON RIEMANNIAN METRIC

A method for quality mesh generation of parametric curved surfaces isproposed. It is shown that the main difference between the proposed method and previous ones is thatour meshing process is done completely in the parametric domains with the guarantee of meshquality. To obtain this aim, the Delaunay method is extended to anisotropic context of 2D domains,and a Riemannian metric map is introduced to remedy the mapping distortion from object space toparametric domain. Compared with previous algorithms, the approach is much simpler, more robust andspeedy. The algorithm is implemented and examples for several geometries are presented todemonstrate the efficiency and validity of the method.

A new insertion sequence for incremental Delaunay triangulation

Incremental algorithm is one of the most popular procedures for constructing Delaunay triangulations （DTs）. However, the point insertion sequence has a great impact on the amount of work needed for the construction of DTs. It affects the time for both point location and structure update, and hence the overall computational time of the triangulation algorithm. In this paper, a simple deterministic insertion sequence is proposed based on the breadth-first-search on a Kd-tree with some minor modifications for better performance. Using parent nodes as search-hints, the proposed insertion sequence proves to be faster and more stable than the Hilbert curve order and biased randomized insertion order （BRIO）, especially for non-uniform point distributions over a wide range of benchmark examples.

ADAPTIVE DELAUNAY TRIANGULATION WITH MULTIDIMENSIONAL DISSIPATION SCHEME FOR HIGH-SPEED COMPRESSIBLE FLOW ANALYSIS

Adaptive Delaunay triangulation is combined with the cell-centered upwinding algorithm to analyze inviscid high-speed compressible flow problems. The multidimensional dissipation scheme was developed and included in the upwinding algorithm for unstructured triangular meshes to improve the computed shock wave resolution. The solution accuracy is further improved by coupling an error estimation procedure to a remeshing algorithm that generates small elements in regions with large change of solution gradients, and at the same time, larger elements in other regions. The proposed scheme is further extended to achieve higher-order spatial and temporal solution accuracy. Efficiency of the combined procedure is evaluated by analyzing supersonic shocks and shock propagation behaviors for both the steady and unsteady high-speed compressible flows.

DELAUNAY TRIANGULATION AND IMAGE DENSE MATCHING IN VIEW SYNTHESIS

A new method of view synthesis is proposed based on Delaunay triangulation. The first step of this method is making the Delaunay triangulation of 2 reference images. Secondly, matching the image points using the epipolar geometry constraint. Finally, constructing the third view according to pixel transferring under the trilinear constraint. The method gets rid of the classic time consuming dense matching technique and takes advantage of Delaunay triangulation. So it can not only save the computation time but also enhance the quality of the synthesized view. The significance of this method is that it can be used directly in the fields of video coding, image compressing and virtual reality.

IMPROVED DELAUNAY TRIANGULATION FOR TRIMMED NURBS SURFACE

An improved algorithm of Delaunay triangulation is proposed by expanding the scope from a convex polygon to an arbitrary polygon area in which holes can be contained in the subdivision procedure. The data structure of generated triangles and the exuviationslike method play a key role, and a single connectivity domain (SCD) without holes is constructed as the initial part of the algorithm. Meanwhile, some examples show that the method can be applied to the triangulation of the trimmed NURBS surface. The result of surface tessellation can be used in many applications such as NC machining, finite element analysis, rendering and mechanism interference detection.

Constrained Delaunay Triangulation for Grouping Functional Areas by Land Use

Functional land use maps are used for land evaluation, environmental analysis, and resource conservation. Spatial data clustering identifies the sparse and crowded places, thus discovering the overall distribution pattern of the dataset. Some clustering methods represent an attribute-oriented approach to knowledge discovery. Other methods rely on natural notions of similarities （e.g., Euclidean distances）. These are not appropriate for constructing functional areas. We propose a similarity value to evaluate the closeness between a pair of points based on the total functional area and the proportion of the main land use type for the entire functional area. We develop constrained attributes employing this similarity value and a DT （Delaunay triangulation） criterion function when merging clusters. Four thresholds are set to ensure that functional areas have acceptable proportions, regular shapes, and no overlap. An experimental study was conducted with cadastral data for Chengdu, China, from 2009. The results show the advantages for objectivity and efficiency in using the proposed algorithm to define functional areas. The areas are created dynamically at any convenient time.

Density-controlled Delaunay triangulation for 2D sea area

Triangulation is widely used in scientific research, such as finite element mesh generation, surface reconstruction and the reconstruction of the density field data. This paper proposes a new method combining image processing and density-controlled Centroidal Voronoi tessellations to quickly generate a density-controlled constrained Delaunay triangulation lbr 2D sea area. Firstly, preprocess digital images of the sea area and extract the boundary of seawater region by eight-neighbor searching algorithm. Then, 1 use Odd-Even Testing＂ method to check if one random vertex is inside the boundary and insert random vertices into the boundary. Finally, we get the CDT of random vertices by density-controlled CVT-Lloyd method. We also give some comparisons with existing methods, and our method performs better in final restllt of triangulation.

A combined contour lines iteration algorithm and Delaunay triangulation for terrain modeling enhancement

Digital Elevation Models(DEMs)play a crucial role in civil and environmental applications,such as hydrologic and geologic analyses,hazard monitoring,natural resources exploration,etc.Generally,DEMs can be generated from various data sources,such as ground surveys,photogrammetric stereo methods,satellite images,laser scanning,and digitized contour lines.Compared with other data sources,contour lines are still the cheapest and more common data source becausethey cover all areas,at different scales,in most countries.Although there are different algorithms and technologies for interpolation in between contour lines,DEMs extracted solely from contours still suffer from poor terrain quality representation,which in turn negatively affects the quality of analytical applications results.In this paper,an approach for improving the digital terrain modeling based on contour line densification and Delaunay triangulation is presented to acquire a more suitable DEM for hydrographic modeling and its applications.The proposed methodology was tested using a variety of terrain patterns in terms of intensity:hilly,undulated,and plain(1:25,000 topographic map,5 m contour interval).The precision of the extracted GRID model increases as the number of added contours increases.Adding four contour lines,the Root Mean Square Error(RMSE)of examining points were 0.26 m,0.29 m,and 0.05 m for hilly,undulated,and plain samples,respectively,and the Mean Absolute Error(MAE)were 0.50 m,0.48 m,and 0.17 m.The convergence probabilities between extracted and original flow lines for the same regions were 96.91%,94.93%,and 84.03%.Applying the methodology,experimental results indicate that the developed approach provides a significant advantage in terrain modeling enhancement,generates DEMs smoothly and effectively from contours,mitigates problems and reduces uncertainties.

DELAUNAY-BASED SURFACE RECONSTRUCTION ALGORITHM IN REVERSE ENGINEERING

Triangulation of scattered points is the first important section duringreverse engineering. New concepts of dynamic circle and closed point are put forward based oncurrent basic method. These new concepts can narrow the extent which triangulation process shouldseek through and optimize the triangles during producing them. Updating the searching edgesdynamically controls progress of triangulation. Intersection judgment between new triangle andproduced triangles is changed into intersection judgment between new triangle and searching edges.Examples illustrate superiorities of this new algorithm.

Optimized Triangulation Algorithm in Terrain Modeling

3D reconstruction of terrain model based on digital line graphics (DLG) is discussed. An auto-coupling triangles algo-rithm based on triangle topological relationship is put forward, and the topological data model of complicated terrain is developed. Based on this data model, automatic 3D topological reconstruction of terrain is realized.

THREE-DIMENSIONAL FINITE ELEMENT DELAUNAY MESH GENERATION BY A PERFECTED NODE CONNECTION METHOD

How to automatically generate three-dimensional finite element Delaunay mesh by a peifected node connection method is introduced, where nodes are generated based on existing elements, instead of independence of node creation and elements generation in traditional node connection method. Therefore, Ihe the difficulty about how to automatically create nodes in the traditional method is overcome.

Accurate surface normal representation to facilitate gradient coil optimization on curved surface

The design methods for gradient coils are mostly based on discrete extrinsic methods(e.g.,the BioteSavart integration calculation),for which the surface normal vector strongly influences any numerical calculation of the discretized surface.Previous studies are mostly based on regular or analytical surfaces,which allow normal vectors to be expressed analytically.For certain applications,design methods for extending currentcarrying surfaces from developable or analytic geometries to arbitrary surfaces generated from a scanned point cloud are required.The key task is to correctly express the discretized normal vectors to ensure geometrical accuracy of the designed coils.Mathematically,it has been proven that applying a Delaunay triangulation to approximate a smooth surface can result in the discrete elemental normal vectors converging to those of the original surface.Accordingly,this article uses Delaunay triangulation to expand upon previous design methods so that they encompass arbitrary piecewise continuous surfaces.Two design methods,the stream function and the so-called solid isotropic material with penalization(SIMP)method,are used to design circumvolute and noncircumvolute gradient coils on general surfaces.

Mesh Generation for Finite Element Analysis of Electric Machines

This paper describes two modified methods for triangular and quadrilateral meshing for finite element analysis of 2D electric machines. One is coupling the classic Delaunay method and advancing front method to generate optimal triangulation; the other is coupling the classic paving and Delaunay triangulation for optimal quadrilateral meshing. Various electric machine models are meshed successfully to demonstrate the robustness and effectiveness of the methods.

Three-Dimensional TIN Algorithm for Digital Terrain Modeling

The problem of taking an unorganized point cloud in 3D space and fitting a polyhedral surface to those points is both important and difficult. Aiming at increasing applications of full three dimensional digital terrain surface modeling, a new algorithm for the automatic generation of three dimensional triangulated irregular network from a point cloud is pro- posed. Based on the local topological consistency test, a combined algorithm of constrained 3D Delaunay triangulation and region-growing is extended to ensure topologically correct reconstruction. This paper also introduced an efficient neighbor- ing triangle location method by making full use of the surface normal information. Experimental results prove that this algo- rithm can efficiently obtain the most reasonable reconstructed mesh surface with arbitrary topology, wherein the automati- cally reconstructed surface has only small topological difference from the true surface. This algorithm has potential applica- tions to virtual environments, computer vision, and so on.

An accelerated scheme with high quality mesh based on Lloyd iteration

High quality mesh plays an important role for finite element methods in science computation and numerical simulation.Whether the mesh quality is good or not,to some extent,it determines the calculation results of the accuracy and efficiency.Different from classic Lloyd iteration algorithm which is convergent slowly,a novel accelerated scheme was presented,which consists of two core parts:mesh points replacement and local edges Delaunay swapping.By using it,almost all the equilateral triangular meshes can be generated based on centroidal Voronoi tessellation(CVT).Numerical tests show that it is significantly effective with time consuming decreasing by 40%.Compared with other two types of regular mesh generation methods,CVT mesh demonstrates that higher geometric average quality increases over 0.99.

Multi-scale Representation of Building Feature in Urban GIS

This paper aims at multi_scale representation of urban GIS,presenting a model to dynamically generalize the building on the basis of Delaunay triangulation model.Considering the constraints of position accuracy,statistical area balance and orthogonal characteristics in building cluster generalization,this paper gives a progressive algorithm of building cluster aggregation,including conflict detection (where),object (who) displacement,and geometrical combination operation (how).The algorithm has been realized in an interactive generalization system and some experiment illustrations are provided.