23 An Improved Simple Sweep Line Algorithm for Delaunay …
269
applying the circumcircle properties, most of the triangles satisfy the properties of the
triangles where no such point is inside the circumcircle. DR triangulation is applied
on the Delaunay triangulation since skinny triangles may appear anyway. By inserting
the Steiner point from the circumcenter of the poor quality of triangle, it manages
to improve the better quality of triangulation. This is important since it can avoid
any error to occur in initializing the triangulation. To sum up, the ISSL algorithm
with DR triangulation produces a higher quality of triangles for the triangulation
compared to SSL algorithm.
23.4 Conclusion
This paper intends to obtain a triangulation while maintaining the properties of the
Delaunay triangulation. New circumcircle properties have been introduced into the
initial triangulation to manage to decrease the amount of skinny triangles. The number
of the flipping process is decreasing for the ISSL algorithm and proved that the ISSL
algorithm is better than the SSL algorithm. However, after the ISSL algorithm is
applied to the DR triangulation technique, the number of the flipping process is
increasing. Hence SSL has a higher efficiency compared to the ISSL. Next, the
percentage of bad angles is decreasing in identifying the quality of the triangles.
There are two types of bad angles that have been used for this project. First, angles
that have less than 60
◦ for comparison between SSL and ISSL algorithm. Second,
angles that have less than 30
◦ for comparison between ISSL algorithm with and
without DR triangulation. Both comparisons show that the percentage of bad angles
is reduced for each data set of points. In conclusion, the proposed algorithm, ISSL
algorithm with DR triangulation, produced a higher quality of triangulation but lower
efficiency compared to the SSL algorithm.
References
1. Li, X.: Anisotropic mesh adaptation for image representation. EURASIP-JVP, 26 (2016)
2. Dinas, S., Banon, J.M.: A review on Delaunay triangulation with application on computer
vision. Int. J. Comput. Sci. Eng. 3, 9–18 (2014)
3. Fortune, S.: Voronoi diagrams and Delaunay triangulations. In: Computing in Euclidean
geometry, pp. 225–265. World Scientific (1995)
4. Bern, M., Eppstein, D.: Mesh generation and optimal triangulation. In: Computing in Euclidean
Geometry, vol. 1, pp. 23–90. World Scientific (1992)
5. Van Kreveld, M., Schwarzkopf, O., de Berg, M., Overmars, M.: Computational Geometry
Algorithms and Applications. Springer (2000)
6. Zˇalik, B., Kolingerova, I.: An incremental construction algorithm for delaunay triangulation
using the nearest-point paradigm. Int. J. Geogr. Inf. Sci. 17, 119–138 (2003)
7. Dwyer, R.A.: A faster divide-and-conquer algorithm for constructing Delaunay triangulations.
Algorithmica 2(1–4), 137–151 (1987)
8. Guibas, L., Stolfi, J.: Primitives for the manipulation of general subdivisions and the
computation of Voronoi diagrams. ACM Trans. Graph. 4(2), 75–123 (1985)
269
applying the circumcircle properties, most of the triangles satisfy the properties of the
triangles where no such point is inside the circumcircle. DR triangulation is applied
on the Delaunay triangulation since skinny triangles may appear anyway. By inserting
the Steiner point from the circumcenter of the poor quality of triangle, it manages
to improve the better quality of triangulation. This is important since it can avoid
any error to occur in initializing the triangulation. To sum up, the ISSL algorithm
with DR triangulation produces a higher quality of triangles for the triangulation
compared to SSL algorithm.
23.4 Conclusion
This paper intends to obtain a triangulation while maintaining the properties of the
Delaunay triangulation. New circumcircle properties have been introduced into the
initial triangulation to manage to decrease the amount of skinny triangles. The number
of the flipping process is decreasing for the ISSL algorithm and proved that the ISSL
algorithm is better than the SSL algorithm. However, after the ISSL algorithm is
applied to the DR triangulation technique, the number of the flipping process is
increasing. Hence SSL has a higher efficiency compared to the ISSL. Next, the
percentage of bad angles is decreasing in identifying the quality of the triangles.
There are two types of bad angles that have been used for this project. First, angles
that have less than 60
◦ for comparison between SSL and ISSL algorithm. Second,
angles that have less than 30
◦ for comparison between ISSL algorithm with and
without DR triangulation. Both comparisons show that the percentage of bad angles
is reduced for each data set of points. In conclusion, the proposed algorithm, ISSL
algorithm with DR triangulation, produced a higher quality of triangulation but lower
efficiency compared to the SSL algorithm.
References
1. Li, X.: Anisotropic mesh adaptation for image representation. EURASIP-JVP, 26 (2016)
2. Dinas, S., Banon, J.M.: A review on Delaunay triangulation with application on computer
vision. Int. J. Comput. Sci. Eng. 3, 9–18 (2014)
3. Fortune, S.: Voronoi diagrams and Delaunay triangulations. In: Computing in Euclidean
geometry, pp. 225–265. World Scientific (1995)
4. Bern, M., Eppstein, D.: Mesh generation and optimal triangulation. In: Computing in Euclidean
Geometry, vol. 1, pp. 23–90. World Scientific (1992)
5. Van Kreveld, M., Schwarzkopf, O., de Berg, M., Overmars, M.: Computational Geometry
Algorithms and Applications. Springer (2000)
6. Zˇalik, B., Kolingerova, I.: An incremental construction algorithm for delaunay triangulation
using the nearest-point paradigm. Int. J. Geogr. Inf. Sci. 17, 119–138 (2003)
7. Dwyer, R.A.: A faster divide-and-conquer algorithm for constructing Delaunay triangulations.
Algorithmica 2(1–4), 137–151 (1987)
8. Guibas, L., Stolfi, J.: Primitives for the manipulation of general subdivisions and the
computation of Voronoi diagrams. ACM Trans. Graph. 4(2), 75–123 (1985)