23 An Improved Simple Sweep Line Algorithm for Delaunay …
267
|A| ∗ |B| =
(x 2 − x 1 )
2
+ (y 2 − y 1 )
2
(23.6)
Equations (23.5) and (23.6) explain how to apply the formula by expanding the
equation of the dot product between two points. If there is no such angle θ
◦
≥ 60
◦ ,
then only the third property is required.
23.2.1.3 Choose the Maximum Angle θ
◦
This stage is only qualified if and only if there is no such angle θ
◦
≥ 60
◦ among all
triangles. Thus, the maximum angle of the new vertices will be chosen to compute
the next triangle. However, this will lead the triangulation to produce poor quality of
triangles. Hence, it is proven that bad triangles may exist in the Delaunay triangulation although it maximizes the minimum triangle. This step requires each point to
fulfill these three properties before to create the next triangle for the triangulation.
The process of expanding the triangles is continued until the initial triangulation is
obtained and continued with the checking process in the next step.
23.3 Analysis of the Results
23.3.1 The Efficiency of the Improved Simple Sweep Line
Algorithm
The efficiency of the algorithm for this project is based on the flipping number
required for each algorithm in creating the triangulation. The lower the flipping
number applied, the higher the efficiency of the algorithm to create the Delaunay
triangulation.
Figure 23.1 observes the two types of algorithm which are SSL and ISSL with DR
triangulation that exhibit the increasing pattern for the number of flipping process.
Based on the increasing pattern, the SSL produces the lower number of flipping
process compared to the ISSL with DR triangulation for each data set in creating the
triangulation. The number of flipping process between SSL and ISSL algorithm is
decreasing without applying the DR triangulation. However, the amount is increasing
right after the proposed method applying the DR triangulation into the ISSL algorithm. This is because of the improvement that has been made on the SSL algorithm
which required new points by DR triangulation into the triangulation which are the
Steiner points and caused the increasing total number of triangles. Hence, the number
of triangles that require Lawson’s technique is increased since more triangles that
are not locally Delaunay appear in the triangulation. To sum up, the SSL algorithm
is more efficient compared to the ISSL algorithm with DR triangulation.
267
|A| ∗ |B| =
(x 2 − x 1 )
2
+ (y 2 − y 1 )
2
(23.6)
Equations (23.5) and (23.6) explain how to apply the formula by expanding the
equation of the dot product between two points. If there is no such angle θ
◦
≥ 60
◦ ,
then only the third property is required.
23.2.1.3 Choose the Maximum Angle θ
◦
This stage is only qualified if and only if there is no such angle θ
◦
≥ 60
◦ among all
triangles. Thus, the maximum angle of the new vertices will be chosen to compute
the next triangle. However, this will lead the triangulation to produce poor quality of
triangles. Hence, it is proven that bad triangles may exist in the Delaunay triangulation although it maximizes the minimum triangle. This step requires each point to
fulfill these three properties before to create the next triangle for the triangulation.
The process of expanding the triangles is continued until the initial triangulation is
obtained and continued with the checking process in the next step.
23.3 Analysis of the Results
23.3.1 The Efficiency of the Improved Simple Sweep Line
Algorithm
The efficiency of the algorithm for this project is based on the flipping number
required for each algorithm in creating the triangulation. The lower the flipping
number applied, the higher the efficiency of the algorithm to create the Delaunay
triangulation.
Figure 23.1 observes the two types of algorithm which are SSL and ISSL with DR
triangulation that exhibit the increasing pattern for the number of flipping process.
Based on the increasing pattern, the SSL produces the lower number of flipping
process compared to the ISSL with DR triangulation for each data set in creating the
triangulation. The number of flipping process between SSL and ISSL algorithm is
decreasing without applying the DR triangulation. However, the amount is increasing
right after the proposed method applying the DR triangulation into the ISSL algorithm. This is because of the improvement that has been made on the SSL algorithm
which required new points by DR triangulation into the triangulation which are the
Steiner points and caused the increasing total number of triangles. Hence, the number
of triangles that require Lawson’s technique is increased since more triangles that
are not locally Delaunay appear in the triangulation. To sum up, the SSL algorithm
is more efficient compared to the ISSL algorithm with DR triangulation.