Chapter 23
An Improved Simple Sweep Line
Algorithm for Delaunay Refinement
Triangulation
Normi binti Abdul Hadi, Anis Farhani, and Wardiah Mohd Dahalan
Abstract This paper is focused on simple sweep line algorithms with Delaunay
refinement triangulation to create 2D triangulation. A new algorithm is proposed
where the main idea is to add circumcircle properties into the simple sweep line
algorithm. Since the Delaunay triangulation itself still generates poor quality of
triangles, this paper applies the Delaunay refinement to enhance the triangulation.
Next, this paper observes the percentage of bad angles to analyze the quality of the
triangles and the flipping number required for each set of points to analyze the efficiency of the algorithm. At the end of this research, all objectives are achieved where
an improved simple sweep line algorithm with Delaunay refinement triangulation is
obtained.
Keywords Sweep line algorithm · 2D Delaunay triangulation · Delaunay
refinement
23.1 Introduction
A triangulation is defined as a technique to calculate the distance between any two
points, or the relative position of two or more points [1]. The aim is to produce a
mesh where the points act as vertices of a triangle. Voronoi diagram or also known
as Dirichlet tessellation can be obtained from a triangulation since it is a partition
of a plane into regions of each polygon [2]. It contains exactly one generating point
for each polygon and this point is close to other points of a given set of objects. A
N. b. A. Hadi · A. Farhani
Universiti Teknologi Mara, Shah Alam, Malaysia
e-mail: normi@tmsk.uitm.edu.my
A. Farhani
e-mail: anisfarhani96@gmail.com
W. M. Dahalan (B)
Universiti Kuala Lumpur Malaysian Institute of Marine Engineering Technology, Lumut,
Malaysia
e-mail: wardiah@unikl.edu.my
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2021
A. Ismail et al. (eds.), Advanced Engineering for Processes and Technologies II,
Advanced Structured Materials 147,
https://doi.org/10.1007/978-3-030-67307-9_23
263
An Improved Simple Sweep Line
Algorithm for Delaunay Refinement
Triangulation
Normi binti Abdul Hadi, Anis Farhani, and Wardiah Mohd Dahalan
Abstract This paper is focused on simple sweep line algorithms with Delaunay
refinement triangulation to create 2D triangulation. A new algorithm is proposed
where the main idea is to add circumcircle properties into the simple sweep line
algorithm. Since the Delaunay triangulation itself still generates poor quality of
triangles, this paper applies the Delaunay refinement to enhance the triangulation.
Next, this paper observes the percentage of bad angles to analyze the quality of the
triangles and the flipping number required for each set of points to analyze the efficiency of the algorithm. At the end of this research, all objectives are achieved where
an improved simple sweep line algorithm with Delaunay refinement triangulation is
obtained.
Keywords Sweep line algorithm · 2D Delaunay triangulation · Delaunay
refinement
23.1 Introduction
A triangulation is defined as a technique to calculate the distance between any two
points, or the relative position of two or more points [1]. The aim is to produce a
mesh where the points act as vertices of a triangle. Voronoi diagram or also known
as Dirichlet tessellation can be obtained from a triangulation since it is a partition
of a plane into regions of each polygon [2]. It contains exactly one generating point
for each polygon and this point is close to other points of a given set of objects. A
N. b. A. Hadi · A. Farhani
Universiti Teknologi Mara, Shah Alam, Malaysia
e-mail: normi@tmsk.uitm.edu.my
A. Farhani
e-mail: anisfarhani96@gmail.com
W. M. Dahalan (B)
Universiti Kuala Lumpur Malaysian Institute of Marine Engineering Technology, Lumut,
Malaysia
e-mail: wardiah@unikl.edu.my
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2021
A. Ismail et al. (eds.), Advanced Engineering for Processes and Technologies II,
Advanced Structured Materials 147,
https://doi.org/10.1007/978-3-030-67307-9_23
263