TRIANGULATING A REGION BETWEEN ARBITRARY POLYGONS
DOI:
https://doi.org/10.47839/ijc.16.3.899Keywords:
Triangulation, simple polygon, holes, region, reducible problem, monotone polygon.Abstract
The paper presents an optimal algorithm for triangulating a region between arbitrary polygons on the plane with time complexity O(N logN ). An efficient algorithm is received by reducing the problem to the triangulation of simple polygons with holes. A simple polygon with holes is triangulated using the method of monotone chains and keeping overall design of the algorithm simple. The problem is solved in two stages. In the first stage a convex hull for m polygons is constructed by Graham’s method. As a result, a simple polygon with holes is received. Thus, the problem of triangulating a region between arbitrary polygons is reduced to the triangulation of a simple polygon with holes. In the next stage the simple polygon with holes is triangulated using an approach based on procedure of splitting polygon onto monotone polygons using the method of chains [15]. An efficient triangulating algorithm is received. The proposed algorithm is characterized by a very simple implementation, and the elements (triangles) of the resulting triangulation can be presented in the form of simple and fast data structure: a tree of triangles [17].References
B. Chazelle, N. Shouraboura, “Bounds on the size of tetrahedralizations,” J. Discrete & Computational Geometry, vol. 14, no. 1, pp. 429-444, 1995.
V. Tereshchenko, S. Pilipenko, A. Fisunenko, “Domain triangulation between convex polytopes,” J. Procedia Computer Science, vol. 18, pp. 2500–2503, 2013.
F. Preparata, M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, Berlin, 1985, 398 p.
V. S. Bileckiy, Small Mine Encyclopedia, vol. 1-3, Shidniy Vidavnichiy Dim, Donetsk, 2013, 1936 p. (in Ukrainian)
J. E. Goodman, J. O’Rourke, Handbook of Discrete and Computational Geometry, 2nd ed., CRC, A CRC Press Company, Boca Raton, London, 2004, 1453 p.
B. Joe, “Construction of three-dimensional Delaunay triangulations using local transformations,” J. Computer Aided Geometric Design, no. 8, pp. 123-142, 1991.
R. E. Tarjan, C. J. Van Wyk, “An O(nlog logn)-time algorithm for triangulating a simple polygon,” SIAM J. Comput, vol. 17, pp. 143–178, 1988.
D. G. Kirkpatrick, M. M. Klawe, R. E. Tarjan, “Polygon triangulation in O(nlog logn) time with simple data structures,” J. Discrete Comput. Geom., vol. 7, pp. 329–346, 1992.
K. L. Clarkson, R. E. Tarjan, C. J. Van Wyk, “A fast Las Vegas algorithm for triangulating a simple polygon,” J. Discrete Comput. Geom., vol. 4, pp. 423–432, 1989.
O. Devillers, “Randomization yields simple O(nlogn) algorithms for difficult Ω(n) problems,” Internat. J. Comput. Geom. Appl., vol. 2, pp. 97–111, 1992.
R. Seidel, “A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons,” J. Comput. Geom. Theory Appl., vol. 1, pp. 51–64, 1991.
V. Tereshchenko, I. Budjak, A. Fisunenko, “The unified algorithmic platform for solving complex problems of computational geometry,” J. Parallel Computing Technologies, vol. 7979, pp. 424-428, 2013.
M. de Berg, M. van Kreveld, M. Overmars, O. Cheong, Computational Geometry, 3rd ed., Springer-Verlag, Berlin, 2008, 398 p.
B. Chazelle, “Triangulating a simple polygon in linear time,” J. Discrete Comput. Geom., vol. 6, pp. 485-524, 1991.
E. Edelsbrunner, L. J. Guibas, J. Stolfi, “Optimal point location a monotone subdivision,” SIAM J. Comput., vol. 15, no. 2, pp. 317–340, 1986.
G. H. Meisters, “Polygons have ears,” J. American Mathematical Monthly, vol. 82, pp. 648–651, 1975.
V. Tereshchenko, Y. Tereshchenko, D. Kotsur, “Point triangulation using Graham’s scan,” in Proceedings of the 5-th IEEE International Conference on Innovative Computing, Galicia, Spain, May 20-22, 2015, pp. 148-151.
U. Grossmann, M. Schauch, S. Hakobyan, “The accuracy of algorithms for WLAN indoor positioning and the standardization of signal reception for diferent mobile devices”, International Journal of Computing, vol. 6, issue 1, pp. 103-109, 2007.
D. Zahorodnia, Y. Pigovsky, P. Bykovyy, “Canny-based method of image contour segmentation,” International Journal of Computing, vol. 15, issue 3, pp. 200-205, 2016.
N. I. Korsunov, D. A. Toropchin, “The method of finding the spam images based on the hash of the key points of the image,” International Journal of Computing, vol. 16, issue 4, pp. 259-264, 2016.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
