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.

Research on Algorithm of the Point Set in the Plane Based on Delaunay Triangulation

In the paper, an improved algorithm is presented for Delaunay triangulation of the point-set in the plain. Based on the original algorithm, we propose the notion of removing circle. During the process of triangulation, and the circle dynamically moves, the algorithm which is simple and practical, therefore evidently accelerates the process of searching a new point, while generating a new triangle. Then it shows the effect of the algorithm in the finite element mesh.

A Novel Spatial Clustering Algorithm Based on Delaunay Triangulation

Exploratory data analysis is increasingly more necessary as larger spatial data is managed in electro-magnetic media. Spatial clustering is one of the very important spatial data mining techniques which is the discovery of interesting rela-tionships and characteristics that may exist implicitly in spatial databases. So far, a lot of spatial clustering algorithms have been proposed in many applications such as pattern recognition, data analysis, and image processing and so forth. However most of the well-known clustering algorithms have some drawbacks which will be presented later when ap-plied in large spatial databases. To overcome these limitations, in this paper we propose a robust spatial clustering algorithm named NSCABDT (Novel Spatial Clustering Algorithm Based on Delaunay Triangulation). Delaunay dia-gram is used for determining neighborhoods based on the neighborhood notion, spatial association rules and colloca-tions being defined. NSCABDT demonstrates several important advantages over the previous works. Firstly, it even discovers arbitrary shape of cluster distribution. Secondly, in order to execute NSCABDT, we do not need to know any priori nature of distribution. Third, like DBSCAN, Experiments show that NSCABDT does not require so much CPU processing time. Finally it handles efficiently outliers.

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.

Quality Improvement Algorithm for Tetrahedral Mesh Based on Optimal Delaunay Triangulation

The concept of optimal Delaunay triangulation (ODT) and the corresponding error-based quality metric are first introduced. Then one kind of mesh smoothing algorithm for tetrahedral mesh based on the concept of ODT is examined. With regard to its problem of possible producing illegal elements, this paper proposes a modified smoothing scheme with a constrained optimization model for tetrahedral mesh quality improvement. The constrained optimization model is converted to an unconstrained one and then solved by integrating chaos search and BFGS (Broyden-Fletcher-Goldfarb-Shanno) algorithm efficiently. Quality improvement for tetrahedral mesh is finally achieved by alternately applying the presented smoothing scheme and re-triangulation. Some testing examples are given to demonstrate the effectiveness of the proposed approach.

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.

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.

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.

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.

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.

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 Novel Method for Transforming XML Documents to Time Series and Clustering Them Based on Delaunay Triangulation

Nowadays exchanging data in XML format become more popular and have widespread application because of simple maintenance and transferring nature of XML documents. So, accelerating search within such a document ensures search engine’s efficiency. In this paper, we propose a technique for detecting the similarity in the structure of XML documents;in the following, we would cluster this document with Delaunay Triangulation method. The technique is based on the idea of representing the structure of an XML document as a time series in which each occurrence of a tag corresponds to a given impulse. So we could use Discrete Fourier Transform as a simple method to analyze these signals in frequency domain and make similarity matrices through a kind of distance measurement, in order to group them into clusters. We exploited Delaunay Triangulation as a clustering method to cluster the d-dimension points of XML documents. The results show a significant efficiency and accuracy in front of common methods.

Study on Delaunay Triangulation with the Islets Constraints

Aiming at Delaunay triangulation with islets constrains in terrain simulation. A general Delaunay triangulation algorithm for constrained data set with islets is proposed. The algorithm firstly constructs Constrained Delaunay Triangulation with constraint polygons which are inner boundary of islets, then according to topological relations within edge, surface, arc segment, applies bidirectional search to find the triangle in islet, lastly it carries on certain corresponding processing to complete the Delaunay triangulation algorithm with islets. The analyses show the algorithm simple, fast speed. The algorithm can be used in 3-D terrain vision.

SMOOTH SURFACE INTERPOLATION OVER ARBITRARY TRIANGULATIONS BY SUBDIVISION ALGORITHMS

A smooth interpolatory subdivision algorithm for the generation of surfaces over arbi-trary triangulations is introduced and its convergence properties over nonuniform triangulationsstudied. For uniform data, this method is a generalization of the analysis for univariatesubdivision algorithms and for nonuniform data, an extraordinary point analysis is introducedand the local subdivision matrix anaiysis presented. It is proved that the algorithm producessmooth surfaces over arbitrary triangular networks provided the shape parameters are kept with-in an appropriate range. Finally, two graphical examples of surface interpolation overnonuniform data are given to show the smoothing process of the algorithm.AMS (MOS): 65D05, 65D15,65D17.

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.