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.展开更多
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.展开更多
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.展开更多
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 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 t...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.展开更多
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.展开更多
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.展开更多
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 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 t...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.展开更多
In order to provide a guidance to specify the element size dynamically during adaptive finite element mesh generation, adaptive criteria are firstly defined according to the relationships between the geometrical featu...In order to provide a guidance to specify the element size dynamically during adaptive finite element mesh generation, adaptive criteria are firstly defined according to the relationships between the geometrical features and the elements of 3D solid. Various modes based on different datum geometrical elements, such as vertex, curve, surface, and so on, are then designed for generating local refined mesh. With the guidance of the defmed criteria, different modes are automatically selected to apply on the appropriate datum objects to program the element size in the local special areas. As a result, the control information of element size is successfully programmed covering the entire domain based on the geometrical features of 3D solid. A new algorithm based on Delatmay triangulation is then developed for generating 3D adaptive finite element mesh, in which the element size is dynamically specified to catch the geometrical features and suitable tetrahedron facets are selected to locate interior nodes continuously. As a result, adaptive mesh with good-quality elements is generated. Examples show that the proposed method can be successfully applied to adaptive finite element mesh automatic generation based on the geometrical features of 3D solid.展开更多
We present a mixed reality-based assistive system for shading paper sketches.Given a paper sketch made by an artist,our interface helps inexperienced users to shade it appropriately.Initially,using a simple Delaunaytr...We present a mixed reality-based assistive system for shading paper sketches.Given a paper sketch made by an artist,our interface helps inexperienced users to shade it appropriately.Initially,using a simple Delaunaytriangulation based inflation algorithm,an approximate depth map is computed.The system then highlights areas(to assist shading)based on a rendering of the 2.5-dimensional inflated model of the input contour.With the help of a mixed reality system,we project the highlighted areas back to aid users.The hints given by the system are used for shading and are smudged appropriately to apply an artistic shading to the sketch.The user is given flexibility at various levels to simulate conditions such as height and light position.Experiments show that the proposed system aids novice users in creating sketches with impressive shading.展开更多
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 c...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.展开更多
A Delaunay-type mesh condition is developed for a linear finite element approximation of two-dimensional anisotropic diffusion problems to satisfy a discrete maximum principle.The condition is weaker than the existi...A Delaunay-type mesh condition is developed for a linear finite element approximation of two-dimensional anisotropic diffusion problems to satisfy a discrete maximum principle.The condition is weaker than the existing anisotropic non-obtuse angle condition and reduces to the well known Delaunay condition for the special case with the identity diffusion matrix.Numerical results are presented to verify the theoretical findings.展开更多
Three-dimensional reconstructions based on serial fault data can be divided into boundary contour splicing and end contour closure. In boundary contour splicing, the Delaunay triangulation algorithm can generate long,...Three-dimensional reconstructions based on serial fault data can be divided into boundary contour splicing and end contour closure. In boundary contour splicing, the Delaunay triangulation algorithm can generate long, narrow triangles or radial shapes and with end contour closure, the Delaunay triangulation based on the determination of the convex-concave vertices tends to generate long, narrow triangles and triangles whose sizes differ greatly, and in some cases failure. This paper presents a Delaunay triangulation algorithm based on the shortest distance first principle for boundary contour splicing and an improved algorithm which combines Delaunay triangulation based on the determination of convex-concave vertices with interpolation for end contour closure. The results show that the algorithms retain the original advantages of the algorithms while increasing the triangulation effectiveness and enhancing the universality of the algorithms.展开更多
We show the rigidity of the hexagonal Delaunay triangulated plane under Luo’s PL conformality.As a consequence,we obtain a rigidity theorem for a particular type of locally finite convex ideal hyperbolic polyhedra.
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 fr...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.展开更多
When a sensor network is deployed to detect objects penetrating a protected region, it is not necessary to have every point in the deployment region covered by a sensor. It is enough if the penetrating objects are det...When a sensor network is deployed to detect objects penetrating a protected region, it is not necessary to have every point in the deployment region covered by a sensor. It is enough if the penetrating objects are detected at some point in their trajectory. If a sensor network guarantees that every penetrating object will be detected by two distinct sensors at the same time somewhere in this area, we say that the network provides double barrier coverage (DBC). In this paper, we propose a new planar structure of Sparse Delaunay Triangulation (SparseDT), and prove some elaborate attributes of it. We develop theoretical foundations for double barrier coverage, and propose efficient algorithms with NS2 simulator using which one can activate the necessary sensors to guarantee double barrier coverage while the other sensors go to sleep. The upper and lower bounds of number of active nodes are determined, and we show that high-speed target will be detected efficiently with this configuration.展开更多
The bubble packing method can generate high-quality node sets in simple and complex domains.However,its efficiency remains to be improved.This study is a part of an ongoing effort to introduce several acceleration sch...The bubble packing method can generate high-quality node sets in simple and complex domains.However,its efficiency remains to be improved.This study is a part of an ongoing effort to introduce several acceleration schemes to reduce the cost of simulation.Firstly,allow the viscosity coefficient c in the bubble governing equations to change according the coordinate of the bubble which are defined separately as odd and normal bubbles,and meanwhile with the saw-shape relationship with time or iterations.Then,in order to relieve the over crowded initial bubble placement,two coefficients w1 and w2 are introduced to modify the insertion criterion.The range of those two coefficients are discussed to be w1=1,w2∈[0.5,0.8].Finally,a self-adaptive termination condition is logically set when the stable system equilibrium is achieved.Numerical examples illustrate that the computing cost can significantly decrease by roughly 80%via adopting various combination of proper schemes(except the uniform placement example),and the average qualities of corresponding Delaunay triangulation substantially exceed 0.9.It shows that those strategies are efficient and can generate a node set with high quality.展开更多
The coverability of Wireless Sensor Networks (WSNs) is essentially a Quality of Service (QoS) problem that measures how well the monitored area is covered by one or more sensor nodes. The coverability of WSNs was ...The coverability of Wireless Sensor Networks (WSNs) is essentially a Quality of Service (QoS) problem that measures how well the monitored area is covered by one or more sensor nodes. The coverability of WSNs was examined by combining existing computational geometry techniques such as the Voronoi diagram and Delaunay triangulation with graph theoretical algorithmic techniques. Three new evaluation algorithms, known as CRM (Comprehensive Risk Minimization), TWS (Threshold Weight Shortest path) and CSM (Comprehensive Support Maximization), were introduced to better measure the coverability. The experimental results show that the CRM and CSM algorithms perform better than the MAM (MAximize Minimum weight) and MIM (Minimize Maximum weight) algorithms, respectively. In addition, the TWS algorithm can provide a lower bound detection possibility that accurately reflects the coverability of the wireless sensor nodes. Both theoretical and experimental analyses show that the proposed CRM, TWS, and CSM algorithms have O(n2) complexity.展开更多
文摘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.
基金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.
基金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.
基金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.
文摘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.
文摘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.
文摘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 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 National Natural Science Foundation of China under grant No.51675506.JGK acknowledges support from an EU2020 FET grant(737043 TiSuMR)the Deutsche Forschungsgesellschaft(DFG)(grant KO 1883/20-1 Metacoils)funding within the framework of the German Excellence Initiative under grant EXC 2082“3D Matter Made to Order”,from the VirtMat initiative“Virtual Materials Design”,and from an ERC Synergy Grant(951459,HiSCORE),European Union.
文摘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.
基金This project is supported by Provincial Project Foundation of Science and Technology of Guangdong, China(No.2002104040101).
文摘In order to provide a guidance to specify the element size dynamically during adaptive finite element mesh generation, adaptive criteria are firstly defined according to the relationships between the geometrical features and the elements of 3D solid. Various modes based on different datum geometrical elements, such as vertex, curve, surface, and so on, are then designed for generating local refined mesh. With the guidance of the defmed criteria, different modes are automatically selected to apply on the appropriate datum objects to program the element size in the local special areas. As a result, the control information of element size is successfully programmed covering the entire domain based on the geometrical features of 3D solid. A new algorithm based on Delatmay triangulation is then developed for generating 3D adaptive finite element mesh, in which the element size is dynamically specified to catch the geometrical features and suitable tetrahedron facets are selected to locate interior nodes continuously. As a result, adaptive mesh with good-quality elements is generated. Examples show that the proposed method can be successfully applied to adaptive finite element mesh automatic generation based on the geometrical features of 3D solid.
文摘We present a mixed reality-based assistive system for shading paper sketches.Given a paper sketch made by an artist,our interface helps inexperienced users to shade it appropriately.Initially,using a simple Delaunaytriangulation based inflation algorithm,an approximate depth map is computed.The system then highlights areas(to assist shading)based on a rendering of the 2.5-dimensional inflated model of the input contour.With the help of a mixed reality system,we project the highlighted areas back to aid users.The hints given by the system are used for shading and are smudged appropriately to apply an artistic shading to the sketch.The user is given flexibility at various levels to simulate conditions such as height and light position.Experiments show that the proposed system aids novice users in creating sketches with impressive shading.
基金This project is supported by Provincial Natural Science foundation of Guangdong!(970516)
文摘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.
基金the National Science Foundation(USA)under Grant DMS-0712935.
文摘A Delaunay-type mesh condition is developed for a linear finite element approximation of two-dimensional anisotropic diffusion problems to satisfy a discrete maximum principle.The condition is weaker than the existing anisotropic non-obtuse angle condition and reduces to the well known Delaunay condition for the special case with the identity diffusion matrix.Numerical results are presented to verify the theoretical findings.
基金Supported by the Science and Technology Foundation of Heilong-jiang Province (No.WC05C02)the Science Research Foundation of Harbin Institute of Technology (No. HIT.2003.22)
文摘Three-dimensional reconstructions based on serial fault data can be divided into boundary contour splicing and end contour closure. In boundary contour splicing, the Delaunay triangulation algorithm can generate long, narrow triangles or radial shapes and with end contour closure, the Delaunay triangulation based on the determination of the convex-concave vertices tends to generate long, narrow triangles and triangles whose sizes differ greatly, and in some cases failure. This paper presents a Delaunay triangulation algorithm based on the shortest distance first principle for boundary contour splicing and an improved algorithm which combines Delaunay triangulation based on the determination of convex-concave vertices with interpolation for end contour closure. The results show that the algorithms retain the original advantages of the algorithms while increasing the triangulation effectiveness and enhancing the universality of the algorithms.
基金supported by NSF of China(No.11871283,No.11971244,and No.12071338)supported by NSF of China(No.11871094)+3 种基金the hospitality of Chern Institute of Mathematics during his visit in Spring 2018 when he initiated this collaborationsupported by NSF of China(No.11571185 and No.11871283)China Scholarship Council(No.201706135016)the Fundamental Research Funds for the Central Universities,Nankai University(No.63191506).
文摘We show the rigidity of the hexagonal Delaunay triangulated plane under Luo’s PL conformality.As a consequence,we obtain a rigidity theorem for a particular type of locally finite convex ideal hyperbolic polyhedra.
基金funded by the Deanship of Scientific Research(DSR),King Abdulaziz University,Jeddah[Grant No.D 1441-298-137].
文摘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.
基金This paper is supported by the National Grand Fundamental Research 973 Program of China under Grant No.2006CB303006.
文摘When a sensor network is deployed to detect objects penetrating a protected region, it is not necessary to have every point in the deployment region covered by a sensor. It is enough if the penetrating objects are detected at some point in their trajectory. If a sensor network guarantees that every penetrating object will be detected by two distinct sensors at the same time somewhere in this area, we say that the network provides double barrier coverage (DBC). In this paper, we propose a new planar structure of Sparse Delaunay Triangulation (SparseDT), and prove some elaborate attributes of it. We develop theoretical foundations for double barrier coverage, and propose efficient algorithms with NS2 simulator using which one can activate the necessary sensors to guarantee double barrier coverage while the other sensors go to sleep. The upper and lower bounds of number of active nodes are determined, and we show that high-speed target will be detected efficiently with this configuration.
基金National Natural Science Foundation of China(No.11071196,90916027).
文摘The bubble packing method can generate high-quality node sets in simple and complex domains.However,its efficiency remains to be improved.This study is a part of an ongoing effort to introduce several acceleration schemes to reduce the cost of simulation.Firstly,allow the viscosity coefficient c in the bubble governing equations to change according the coordinate of the bubble which are defined separately as odd and normal bubbles,and meanwhile with the saw-shape relationship with time or iterations.Then,in order to relieve the over crowded initial bubble placement,two coefficients w1 and w2 are introduced to modify the insertion criterion.The range of those two coefficients are discussed to be w1=1,w2∈[0.5,0.8].Finally,a self-adaptive termination condition is logically set when the stable system equilibrium is achieved.Numerical examples illustrate that the computing cost can significantly decrease by roughly 80%via adopting various combination of proper schemes(except the uniform placement example),and the average qualities of corresponding Delaunay triangulation substantially exceed 0.9.It shows that those strategies are efficient and can generate a node set with high quality.
文摘The coverability of Wireless Sensor Networks (WSNs) is essentially a Quality of Service (QoS) problem that measures how well the monitored area is covered by one or more sensor nodes. The coverability of WSNs was examined by combining existing computational geometry techniques such as the Voronoi diagram and Delaunay triangulation with graph theoretical algorithmic techniques. Three new evaluation algorithms, known as CRM (Comprehensive Risk Minimization), TWS (Threshold Weight Shortest path) and CSM (Comprehensive Support Maximization), were introduced to better measure the coverability. The experimental results show that the CRM and CSM algorithms perform better than the MAM (MAximize Minimum weight) and MIM (Minimize Maximum weight) algorithms, respectively. In addition, the TWS algorithm can provide a lower bound detection possibility that accurately reflects the coverability of the wireless sensor nodes. Both theoretical and experimental analyses show that the proposed CRM, TWS, and CSM algorithms have O(n2) complexity.