Explore chapters and articles related to this topic
Image-Based Triangular and Tetrahedral Meshing
Published in Yongjie Jessica Zhang, Geometric Modeling and Mesh Generation from Scanned Images, 2018
Delaunay triangulation has many applications. In modeling terrain and many other objects starting from a points cloud, Delaunay triangulation produces good quality triangles with the minimum angle maximized. Due to its angle guarantee and efficient mesh generation procedure, Delaunay-based methods have been used broadly to generate finite element meshes for many finite element simulations. There are a lot of advances based on the basic Delaunay triangulation, aiming at generating quality triangular and tetrahedral meshes. Delaunay refinement aims to refine the triangles or tetrahedra locally by inserting new nodes in order to maintain the Delaunay criterion. Different approaches were studied to introduce and define new nodes [87, 92, 344]. Sliver exudation [88] was developed to eliminate those slivers. A deterministic algorithm [87] was developed to generate a weighted Delaunay mesh with no poorly shaped tetrahedra including slivers. Shewchuk [345] used the constrained Delaunay triangulation (CDT) to resolve the problem of enforcing boundary conformity. Delaunay refinement [344], edge removal and multiface removal optimization algorithms [346] were utilized to improve the tetrahedral quality. Shewchuk [347] drew some valuable conclusions on quality measures for finite element analysis. In recent years, Chrisochoides and Chernikov performed many studies on parallel 2D and 3D Delaunay meshing with guaranteed quality [90, 91, 142] and also applied their techniques to medical image applications.
Fast estimation of skeleton points on 3D deformable meshes
Published in João Manuel, R. S. Tavares, R. M. Natal Jorge, Computational Modelling of Objects Represented in Images, 2018
Julien Mille, Romuald Boné, Pascal Makris, Hubert Cardot
Given the mesh data, we consider the skeleton, a compact representation of geometry and topology, which makes it suitable for structural pattern recognition (Loncaric 1998). Skeletonization methods are divided into two groups, whether they are based on pixels or not. Pixel-based methods use the whole set of pixels inside the shape in the skeletonization process, starting from the assumption that the shape is fully discretized. These approaches generally use thinning algorithms, based for example on distance transforms or mathematical morphology (Lam, Lee, and Suen 1992). Significant work in this area include veinerization (Deseilligny, Stamon, and Suen 1998) and distance maps combined with level-sets (Kimmel, Shaked, Kiryati, and Bruckstein 1995). Conversely, non-pixel-based methods only consider the shape boundary and are more suitable to polygonal representations. In this context, the Voronoi diagram is the usual basis for the computation of a geometric skeleton (Brandt and Algazi 1992). The Voronoi graph (see figure 1) is the topological dual equivalent of the Delaunay triangulation, which can be computed on any set of unorganized points. The polygon-specific Delaunay triangulation, in which polygon edges are fixed, is known as Constrained Delaunay Triangulation (CDT) (Chew 1989). An efficient implementation of the CDT in n-dimension was presented in (Shewchuk 2002). Given the Voronoi graph, the geometric skeleton is computed as the set of Voronoi edges which are totally inside the shape. In (Amenta, Sunghee, and Kolluri 2001), one may find an algorithm for computing 3D Voronoi graphs.
Service Deployment
Published in Krzysztof W. Kolodziej, Johan Hjelm, Local Positioning Systems, 2017
Krzysztof W. Kolodziej, Johan Hjelm
Accessible paths need to support navigation applications. For this reason, floor plans are divided into two types of spaces: (1) valid, an area that can be occupied by a person, and (2) invalid, an area occupied by a physical obstacle (e.g., wall). Hence, the desired path should not intersect any invalid space and should lie approximate in the center of valid space. Extracting accessible paths is done using the constrained Delaunay triangulation (CDT) to subdivide the floor plan into triangles. The CDT algorithm can be applied to a general set of input segments known as the constraining segments. The result is a triangulated planar graph (defines the boundary between valid and invalid spaces). One issue that might come up is the gaps/leakages between segments (need for a minimum tolerance level). Another potential issue is the gaps/leakages from ground floors of buildings (need to define a bounding box encompassing the outline of the building). Also, the acad2μg tool sometimes discards wall segments due to incorrect recognition (need for manual intervention). This results in a need for CAD tools that will embed standardized semantics information.
Spatial simulation using abstraction of virtual geographic environments
Published in International Journal of Digital Earth, 2018
Spatial decomposition: The second step consists of obtaining an exact spatial decomposition of the input data into cells. First, an elevation map is computed using the constrained Delaunay triangulation (CDT) technique. All the elevation points of the layers are injected into a 2D triangulation, the elevation being considered as an attribute of each node. Second, a merged semantics map is computed, corresponding to a constrained triangulation of the semantic layers. Indeed, each segment of a semantic layer is injected as a constraint which keeps track of the original semantic data by using an additional attribute for each semantic layer. The obtained map is then a constrained triangulation merging all input semantics where each constraint represents as many semantics as the number of input layers containing it (Figures 3 and 4).
Nonlinear thermal simulation of laser metal deposition
Published in Australian Journal of Mechanical Engineering, 2021
Diego Montoya-Zapata, Juan M. Rodríguez, Aitor Moreno, Oscar Ruiz-Salguero, Jorge Posada
4. Mesh generation: A mesh is generated using constrained Delaunay triangulation (Carbonell, Rodríguez, and Oñate 2020; Rodriguez et al. 2016). The constraints of the triangulation are given by the edges of the bead boundary . The triangulation may contain spurious triangles that do not belong to the bead (see Figure 6(c)). These spurious triangles are removed to produce the bead mesh for time step : , , as shown in Figure 6(d).
A progressive method for the collapse of river representation considering geographical characteristics
Published in International Journal of Digital Earth, 2020
Yilang Shen, Tinghua Ai, Jingzhong Li, Lina Huang, Wende Li
The methods used for the collapse of geometric features based on vector data mainly include straight skeleton methods (Aichholzer et al. 1996; Das et al. 2010; Eppstein and Erickson 1999; Haunert and Sester 2004, 2008) and Delaunay triangulation methods (Chithambaram, Beard, and Barrera 1991; Poorten and Jones 2002; McAllister and Snoeyink 2000; Regnauld and Mackaness 2006; DeLucia and Black 1987; Li 2006; Zou and Yan 2001; Morrison and Zou 2007; Penninga et al. 2005; Uitermark, Vogels, and van Oosterom 1999; Jones, Bundy, and Ware 1995; Gao and Minami 1993). Aichholzer et al. (1996) first proposed the straight skeleton method for geometric collapse. However, the initial straight skeleton method proposed by Aichholzer et al. has trouble handling the polygons with complicated structures. To solve this problem, other scholars such as Eppstein and Erickson (1999) and Das et al. (2010) modified the original straight skeleton method, enabling it to be used for complicated polygons. The Delaunay triangulation method, which is used to extract skeletons of polygons, was first proposed by DeLucia and Black (1987). Subsequently, this constrained Delaunay triangulation has been widely used for extracting line branches. In these studies, branches with different shapes and structures in complicated polygons were investigated by Zou and Yan (2001), Morrison and Zou (2007), Jones, Bundy, and Ware (1995), Penninga et al. (2005), and Gao and Minami (1993). For certain special map elements, such as rivers, Regnauld and Mackaness (2006) and McAllister and Snoeyink (2000) proposed approaches for the extraction of skeleton lines using Delaunay triangulation. In addition, Ai and Van Oosterom (2002) considered the semantic differences of objects during skeleton line extraction.