23 An Improved Simple Sweep Line Algorithm for Delaunay …
265
23.1.3 Simple Sweep Line Algorithm
Simple sweep line algorithm is applying Lawson’s legalizations where it often gives
rise to wrong triangulation especially when developing a large dataset. This is because
many skinny triangles may exist within the collinear vertices produced by collinear
points from Lawson’s local optimization procedure (LOP). Moreover, there also can
exist four circular points which require a multiple refinement process to solve the
problems. The skinny triangles effect the solution where it can cause an issue to the
elements of the triangle. The small angle of skinny triangles can produce other angles
to be too large and cause poor conditioning. Hence, for those reasons, the simple
sweep line is slower than Zalik’s algorithm but faster compared to the sweep circle
algorithm [12] in terms of processing time in order to obtain the triangulation.
Therefore, this study proposed a new algorithm and it is compared mainly with the
simple sweep line algorithm to make an improvement for constructing the triangulation. The main idea of the improved simple sweep line algorithm is to add circumcircle
properties into the simple sweep line technique. By introducing a few properties in
creating the initial triangulation, the quality of the triangles in the triangulation is
improved by reducing the number of bad triangles and maximizing the minimum
angle in all triangles. At the end of the process, this project looks forward to the less
percentage of bad angles and high quality of the triangles in the triangulation.
23.2 Methodology
23.2.1 Creating Initial Triangulation
Once the initial triangle of the polygon is obtained, the next step is finding the
initial triangulation by expanding the triangles where all vertices in the points set are
connected before applying the sweep line algorithm. This is the improvement step
from the current simple sweep line where three main properties have been proposed
by this study to avoid poor quality in order to obtain the initial triangulation. Starting
from the initial triangle, the new vertices need to go through these three properties
respectively as below in order to create the next triangles.
i. Checking the intersection between two segments of triangles.
ii. Choose an angle θ
◦
≥ 60
◦ .
iii. Choose the maximum angle θ
◦ .
23.2.1.1 Checking the Intersection Between Two Segments of Triangles
This study is using the Barycentric interpolation to find the intersection between two
points in order to compute the next triangle. The Barycentric interpolation is best
265
23.1.3 Simple Sweep Line Algorithm
Simple sweep line algorithm is applying Lawson’s legalizations where it often gives
rise to wrong triangulation especially when developing a large dataset. This is because
many skinny triangles may exist within the collinear vertices produced by collinear
points from Lawson’s local optimization procedure (LOP). Moreover, there also can
exist four circular points which require a multiple refinement process to solve the
problems. The skinny triangles effect the solution where it can cause an issue to the
elements of the triangle. The small angle of skinny triangles can produce other angles
to be too large and cause poor conditioning. Hence, for those reasons, the simple
sweep line is slower than Zalik’s algorithm but faster compared to the sweep circle
algorithm [12] in terms of processing time in order to obtain the triangulation.
Therefore, this study proposed a new algorithm and it is compared mainly with the
simple sweep line algorithm to make an improvement for constructing the triangulation. The main idea of the improved simple sweep line algorithm is to add circumcircle
properties into the simple sweep line technique. By introducing a few properties in
creating the initial triangulation, the quality of the triangles in the triangulation is
improved by reducing the number of bad triangles and maximizing the minimum
angle in all triangles. At the end of the process, this project looks forward to the less
percentage of bad angles and high quality of the triangles in the triangulation.
23.2 Methodology
23.2.1 Creating Initial Triangulation
Once the initial triangle of the polygon is obtained, the next step is finding the
initial triangulation by expanding the triangles where all vertices in the points set are
connected before applying the sweep line algorithm. This is the improvement step
from the current simple sweep line where three main properties have been proposed
by this study to avoid poor quality in order to obtain the initial triangulation. Starting
from the initial triangle, the new vertices need to go through these three properties
respectively as below in order to create the next triangles.
i. Checking the intersection between two segments of triangles.
ii. Choose an angle θ
◦
≥ 60
◦ .
iii. Choose the maximum angle θ
◦ .
23.2.1.1 Checking the Intersection Between Two Segments of Triangles
This study is using the Barycentric interpolation to find the intersection between two
points in order to compute the next triangle. The Barycentric interpolation is best