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 ...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.展开更多
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 pr...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.展开更多
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 co...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.展开更多
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 spati...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.展开更多
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 ...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.展开更多
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 t...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.展开更多
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...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.展开更多
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 discove...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.展开更多
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 ...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.展开更多
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...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.展开更多
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 ...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.展开更多
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...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.展开更多
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 pa...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 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 epipo...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.展开更多
基金supported by the National Natural Science Foundation of China (10972006 and 11172005)the National Basic Research Program of China (2010CB832701)
文摘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.
基金Supported by National Natural Science Foundation of China(NSFC)(61572288,61373078)the Fundamental Research Funds of Shandong University(2015JC009)the Program for New Century Excellent Talents in University(NCET-13-0529)
文摘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.
文摘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.
基金funded by National Natural Science Foundation of China(31570627)Hunan Forestry Science and Technology Project(XLK201740)+1 种基金Hunan Science and Technology Innovation Platform and Talent Plan(2017TP1022)Hunan Science and Technology Plan Project(2015WK3017)。
文摘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.
基金Project (No. 60225009) supported by the National Natural ScienceFoundation of China through the National Science Fund for Distin-guished Young Scholars
文摘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.
文摘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.
文摘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.
文摘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.
文摘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.
文摘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.
文摘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.
文摘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.
基金This project is supported by National Natural Science Foundation of China(No.59990470).
文摘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 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.
