264
N. b. A. Hadi et al.
circumcircle is a circle with all the vertices of the triangle lie on the boundary of the
circle [3].
23.1.1 2D Delaunay Triangulation
Delaunay triangulation is a triangulation method where it works as an automatic
generation algorithm to solve simplex meshing problems where it maximizes the
minimum angles of triangles. Proposed by Boris Nikolaevich Delaunay in 1934, the
2D Delaunay triangulation was the most well-known triangulation due to its property
and also it optimized several other geometric criteria related to interpolation accuracy
[4]. The basic aim for this technique is to maximize the minimum angle among each
triangle in the triangulation and it tends to avoid the skinny triangles in order to
obtain the results.
There are many types of algorithm which have been introduced for creating
Delaunay triangulation such as incremental algorithms [5, 6], divide and conquer
algorithms [7, 8], gift wrapping algorithms [9] and sweep line algorithms [10]. Introduced by Fortune (1987), the sweep line algorithm takes the shortest time compared
to incremental, divide and conquer, sweep line, gift wrapping, advancing front and
convex hull algorithms [11]. Hence, this study focuses only on the sweep line algorithm for constructing the Delaunay triangulations. There are many versions of the
sweep line algorithm that have been introduced by a few researchers such as Zalik’s
sweep line, sweep circle and simple sweep line algorithms [12, 13]. This research
presented a new type of algorithm by improving the simple sweep line algorithm.
23.1.2 2D Delaunay Refinement
A Delaunay refinement is best defined as a meshing algorithm that refined and maintained the Delaunay triangulation by inserting vertices until the mesh meets element
quality and size [14]. The main idea is to remove the bad triangles by satisfying
bound of angles, edge of lengths and the number of triangles from small to large
sizes. This is due to the fact that the Delaunay triangulation still does not solve the
problem of triangular mesh generation although it maximizes the minimum angle.
There are two reasons why this problem arises. First, skinny triangles may appear
anyway and second, the Delaunay triangulation of domain’s vertices might not satisfy
the domain’s boundary. However, the Delaunay refinement can solve both problems
by introducing Steiner points as new vertices [15].
N. b. A. Hadi et al.
circumcircle is a circle with all the vertices of the triangle lie on the boundary of the
circle [3].
23.1.1 2D Delaunay Triangulation
Delaunay triangulation is a triangulation method where it works as an automatic
generation algorithm to solve simplex meshing problems where it maximizes the
minimum angles of triangles. Proposed by Boris Nikolaevich Delaunay in 1934, the
2D Delaunay triangulation was the most well-known triangulation due to its property
and also it optimized several other geometric criteria related to interpolation accuracy
[4]. The basic aim for this technique is to maximize the minimum angle among each
triangle in the triangulation and it tends to avoid the skinny triangles in order to
obtain the results.
There are many types of algorithm which have been introduced for creating
Delaunay triangulation such as incremental algorithms [5, 6], divide and conquer
algorithms [7, 8], gift wrapping algorithms [9] and sweep line algorithms [10]. Introduced by Fortune (1987), the sweep line algorithm takes the shortest time compared
to incremental, divide and conquer, sweep line, gift wrapping, advancing front and
convex hull algorithms [11]. Hence, this study focuses only on the sweep line algorithm for constructing the Delaunay triangulations. There are many versions of the
sweep line algorithm that have been introduced by a few researchers such as Zalik’s
sweep line, sweep circle and simple sweep line algorithms [12, 13]. This research
presented a new type of algorithm by improving the simple sweep line algorithm.
23.1.2 2D Delaunay Refinement
A Delaunay refinement is best defined as a meshing algorithm that refined and maintained the Delaunay triangulation by inserting vertices until the mesh meets element
quality and size [14]. The main idea is to remove the bad triangles by satisfying
bound of angles, edge of lengths and the number of triangles from small to large
sizes. This is due to the fact that the Delaunay triangulation still does not solve the
problem of triangular mesh generation although it maximizes the minimum angle.
There are two reasons why this problem arises. First, skinny triangles may appear
anyway and second, the Delaunay triangulation of domain’s vertices might not satisfy
the domain’s boundary. However, the Delaunay refinement can solve both problems
by introducing Steiner points as new vertices [15].