PSEUDO-TRIANGULATION OF MONOTONE POLYGON USING SWEEP LINE ALGORITHM
DOI:
https://doi.org/10.53808/KUS.2022.ICSTEM4IR.0039-seKeywords:
Polygon, triangulation, pseudo-triangle, sweep line, edge, vertexAbstract
In the field of computational geometry, pseudo-triangulation of a polygon is an interesting topic. Breaking a polygon into pseudo-triangles reduces the calculation cost and increases computational power. The sweep line algorithm also known as the plane sweep algorithm uses an imaginary line or a plain surface on the Euclidean plain to perform various computations. Finding line intersection with sweep line was a revolutionary outcome. As polygons are the combination of edges and vertices, we tried to implement the concept of a sweep line to create pseudo-triangles inside the polygon. Among the vast triangulation algorithms, a few pseudo-triangulation algorithms are available. Using the sweep line algorithm, we have been able to pseudo-triangulate a monotone polygon which uses the time complexity of to execute. As complex polygons can often be divided into a monotone polygon in just so it is possible to chain with our sweep line-based technique, any complex polygon can be pseudo-triangulated in .
Downloads
References
Alipour, S. (2016). On guarding polygons with holes. 23, 1–5.
Aronov, B., Asano, T., & Funke, S. (2012). Optimal Triangulations of Points and Segments with Steiner Points. Http://Dx.Doi.Org/10.1142/S0218195910003219, 20(1), 89–104. https://doi.org/10.1142/ S0218195910003219
Bern, M., Dobkin, D., & Eppstein, D. (1995). Triangulating Polygons Without Large Angles. http://citeseerx.ist. psu.edu/viewdoc/summary?doi=10.1.1.32.5231
Chwa, K. Y. (1987). A New Triangulation-Linear Class of Simple Polygons. International Journal of Computer Mathematics, 22(2), 135–147. https://doi.org/10.1080/00207168708803587
Emamy, Z. S. (2015). Pseudo-triangulating a simple polygon from its visibility graph. 2015 5th International Conference on Computer and Knowledge Engineering, ICCKE 2015, 106–111. https://doi.org/10.1109/ ICCKE.2015.7365868
Eppstein, D. (1994). Approximating the minimum weight steiner triangulation. Discrete & Computational Geometry 1994 11:2, 11(2), 163–191. https://doi.org/10.1007/BF02574002
Erten, H., & Üngör, A. (2009). Quality Triangulations with Locally Optimal Steiner Points. Http://Dx.Doi.Org/10.1137/080716748, 31(3), 2103–2130. https://doi.org/10.1137/080716748
Garey, M. R., Johnson, D. S., Preparata, F. P., & Tarjan, R. E. (1978). Triangulating a simple polygon. Information Processing Letters, 7(4), 175–179. https://doi.org/10.1016/0020-0190(78)90062-5
Hadi, N. binti A., Farhani, A., & Dahalan, W. M. (2021). An Improved Simple Sweep Line Algorithm for Delaunay Refinement Triangulation. Advanced Structured Materials, 147, 263–270. https://doi.org/ 10.1007/978-3-030-67307-9_23
Hai, Y., Guo, Y., & Dong, M. (2022). A CAE-oriented mesh hole-filling algorithm focusing on geometry and quality. Engineering Computations, ahead-of-print(ahead-of-print). https://doi.org/10.1108/EC-07-2021-0411
Hertel, S., & Mehlhorn, K. (1983). Fast triangulation of simple polygons. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 158 LNCS, 207–218. https://doi.org/10.1007/3-540-12689-9_105
Hoffmann, F., Kaufmann, M., & Kriegel, K. (1991). The art gallery theorem for polygons with holes. [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, 39–48. https://doi.org/10.1109/ SFCS.1991.185346
Iwerks, J., & Mitchell, J. S. B. (2012). The art gallery theorem for simple polygons in terms of the number of reflex and convex vertices. Information Processing Letters, 112(20), 778–782. https://doi.org/10.1016/ J.IPL.2012.07.005
Kolingerová, I., Trčka, J., & Hobza, L. (2011). Construction of pseudo-triangulation by incremental insertion. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6784 LNCS(PART 3), 30–43. https://doi.org/10.1007/978-3-642-21931-3_3
Lamot, M., & Zalik, B. (1999). An overview of triangulation algorithms for simple polygons. Proceedings of the International Conference on Information Visualisation, 1999-Janua, 153–158. https://doi.org/10.1109/
Alipour, S. (2016). On guarding polygons with holes. 23, 1–5.
Aronov, B., Asano, T., & Funke, S. (2012). Optimal Triangulations of Points and Segments with Steiner Points. Http://Dx.Doi.Org/10.1142/S0218195910003219, 20(1), 89–104. https://doi.org/10.1142/ S0218195910003219
Bern, M., Dobkin, D., & Eppstein, D. (1995). Triangulating Polygons Without Large Angles. http://citeseerx.ist. psu.edu/viewdoc/summary?doi=10.1.1.32.5231
Chwa, K. Y. (1987). A New Triangulation-Linear Class of Simple Polygons. International Journal of Computer Mathematics, 22(2), 135–147. https://doi.org/10.1080/00207168708803587
Emamy, Z. S. (2015). Pseudo-triangulating a simple polygon from its visibility graph. 2015 5th International Conference on Computer and Knowledge Engineering, ICCKE 2015, 106–111. https://doi.org/10.1109/ ICCKE.2015.7365868
Eppstein, D. (1994). Approximating the minimum weight steiner triangulation. Discrete & Computational Geometry 1994 11:2, 11(2), 163–191. https://doi.org/10.1007/BF02574002
Erten, H., & Üngör, A. (2009). Quality Triangulations with Locally Optimal Steiner Points. Http://Dx.Doi.Org/10.1137/080716748, 31(3), 2103–2130. https://doi.org/10.1137/080716748
Garey, M. R., Johnson, D. S., Preparata, F. P., & Tarjan, R. E. (1978). Triangulating a simple polygon. Information Processing Letters, 7(4), 175–179. https://doi.org/10.1016/0020-0190(78)90062-5
Hadi, N. binti A., Farhani, A., & Dahalan, W. M. (2021). An Improved Simple Sweep Line Algorithm for Delaunay Refinement Triangulation. Advanced Structured Materials, 147, 263–270. https://doi.org/ 10.1007/978-3-030-67307-9_23
Hai, Y., Guo, Y., & Dong, M. (2022). A CAE-oriented mesh hole-filling algorithm focusing on geometry and quality. Engineering Computations, ahead-of-print(ahead-of-print). https://doi.org/10.1108/EC-07-2021-0411
Hertel, S., & Mehlhorn, K. (1983). Fast triangulation of simple polygons. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 158 LNCS, 207–218. https://doi.org/10.1007/3-540-12689-9_105
Hoffmann, F., Kaufmann, M., & Kriegel, K. (1991). The art gallery theorem for polygons with holes. [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, 39–48. https://doi.org/10.1109/ SFCS.1991.185346
Iwerks, J., & Mitchell, J. S. B. (2012). The art gallery theorem for simple polygons in terms of the number of reflex and convex vertices. Information Processing Letters, 112(20), 778–782. https://doi.org/10.1016/ J.IPL.2012.07.005
Kolingerová, I., Trčka, J., & Hobza, L. (2011). Construction of pseudo-triangulation by incremental insertion. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6784 LNCS(PART 3), 30–43. https://doi.org/10.1007/978-3-642-21931-3_3
Lamot, M., & Zalik, B. (1999). An overview of triangulation algorithms for simple polygons. Proceedings of the International Conference on Information Visualisation, 1999-Janua, 153–158. https://doi.org/10.1109/ IV.1999.781552
Lamot, M., & Zalik, B. (2000). A Contribution to Triangulation Algorithms for Simple Polygons. 319–331.
Lewis, B. A., & Robinson, J. S. (1978). Triangulation of planar regions with applications. The Computer Journal, 21(4), 324–332. https://doi.org/10.1093/COMJNL/21.4.324
Livesu, M. (2020). Mapping Surfaces with Earcut. http://arxiv.org/abs/2012.08233
Livesu, M., Cherchi, G., Scateni, R., & Attene, M. (2021). Deterministic Linear Time Constrained Triangulation using Simplified Earcut. IEEE Transactions on Visualization and Computer Graphics, 14(8), 1–7. https://doi.org/10.1109/TVCG.2021.3070046
Majid, R. N. (2012). Pseudo Triangulation of Point Set Using Polygon Construction. 24–26.
Mandot, M. (2013). Application of the Triangulation of Polygon. 3(11), 1188–1209.
Mašović, S. H., Elshaarawy, I. A., Stanimirović, P. S., & Krtolica, P. V. (2018). Orbiting triangle method for convex polygon triangulation. Applicable Analysis and Discrete Mathematics, 12(2), 439–454. https://doi.org/10.2298/AADM170829013M
Rote, G., Santos, F., & Streinu, I. (2008). Pseudo-triangulations—a survey. 0000, 343–410. https://doi.org/10.1090 /conm/453/08807
Roy, S., & Akter, R. (2018). Pseudo-Triangulation of a Complex Polygon Using Augmented Ear Cutting Approach and Visibility Information.
Roy, S., & Shapla, R. (2018). Pseudo-Triangulation of a Complex Polygon Using Augmented Ear Cutting Approach and Visibility Information Swarna Roy.
Shamos, M. I., & Hoey, D. (1975). Geometric intersection problems. 17th IEEE Symp. Foundations of Computer Science (FOCS ’76), 208–215. https://doi.org/10.1109/sfcs.1976.16
Shen, L., Yang, Z., & Hao, S. (2021). An adaptive triangulation optimization algorithm based on empty circumcircle. IMCEC 2021 - IEEE 4th Advanced Information Management, Communicates, Electronic and Automation Control Conference, 1880–1884. https://doi.org/10.1109/IMCEC51613.2021.9482071
Speckmann, B., & Tóth, C. D. (2005). Allocating vertex π-guards in simple polygons via pseudo-triangulations. Discrete and Computational Geometry, 33(2), 345–364. https://doi.org/10.1007/s00454-004-1091-9
Tarjan, R. E., & Van Wyk, C. J. (1986). A linear-time algorithm for triangulating simple polygons. 380–388. https://doi.org/10.1145/12130.12170
Toussaint, G. (1991). Efficient triangulation of simple polygons. The Visual Computer, 7(5–6), 280–295. https://doi.org/10.1007/BF01905693
Toussaint, G. T. (1984). A new linear algorithm for triangulating monotone polygons. Pattern Recognition Letters, 2(3), 155–158. https://doi.org/10.1016/0167-8655(84)90039-4
Üngör, A. (2004). Off-Centers: A New Type of Steiner Points for Computing Size-Optimal Quality-Guaranteed Delaunay Triangulations. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2976, 152–161. https://doi.org/10.1007/978-3-540-24698-5_19
Žalik, B. (2005). An efficient sweep-line Delaunay triangulation algorithm. CAD Computer Aided Design, 37(10), 1027–1038. https://doi.org/10.1016/j.cad.2004.10.004
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Khulna University Studies
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
