DEVELOPMENT OF ALGORITHM AND DATA STRUCTURE FOR 2D REGIONS DISCRETE MODEL ELEMENTS ACCELERATED SEARCH

2024;
: 79-93
https://doi.org/10.23939/cds2024.01.079
Received: March 04, 2024
Revised: March 20, 2024
Accepted: April 01, 2024
1
Lviv Polytechnic National University
2
Lviv Polytechnic National University, Lviv, Ukraine

This paper is devoted to improving the search request processing productivity for planar discrete models used in engineering software. A data structure has been developed to accelerate the search for discretization elements based on a hierarchical triangular mesh. The developed indexing structure is built by a downward iterative algorithm, which constructs each new level of the hierarchy based on the previous level or indexed triangulation by simplifying it, which ensures that the morphology of the triangulation mesh is preserved throughout all levels of the hierarchical indexing structure. The developed building algorithm ensures the presence of tree-like connections between the levels of the hierarchical triangulation mesh, which allows downward navigation between geometrically close triangles. Search acceleration is achieved by performing a directed search in the top level of the indexing structure and then navigating between levels using downward links until the indexed triangle is found. The program implementation was carried out using C++17, and visualization of triangulation grids and isolines was carried out using the ObjectARX library. Based on the software implementation, an executive library was created.

[1] Zhang, X and Du, Z.,“Spatial Indexing”,The Geographic Information Science & Technology Body of Knowledge (4th Quarter 2017 Edition), John P. Wilson (ed). https://doi.org/10.22224/gistbok/2017.4.12

[2] M. Andrew, “Another Efficient Algorithm for Convex Hullsin Two Dimensions”, Info. Proc. Letters 9, 216-219 (1979). https://doi.org/10.1016/0020-0190(79)90072-3

[3] D. H. Eberly, “Triangulation by Ear Clipping”, Geometric Tools, LLC.,www.geometrictools.com, 1998 https://doi.org/10.1145/282918.282923

[4] Guibas L, Stolfi J,“Primitives for the manipulation of general subdivision sand the computation of Voronoi”,ACM Transactionson Graphics 1985 Volume 4, Issue 2, p 107,doi:10.1145/282918.282923

[5] Dutton, G. “Encoding and handling geospatial data with hierarchical triangular meshes”,Advancesin GIS Research II. London: Taylor&Francis, 1996, p 505-518

[6] Rigaux, P., Scholl, M., &Voisard, A.  “Spatial Databases – with application to GIS”,Morgan Kaufmann, San Francisco 2002, p 410.

[7] M. Bern, D. Eppstein, “Mesh generation and optimal triangulation”, Computing in Euclidean geometry 1992, 1, p 23–90. https://doi.org/10.1142/9789814355858_0002

[8] de Berg, M., Cheong, O., van Kreveld, M. and Overmars, M. “Computational Ge-ometry: Algorithms and Applications”, Springer, 3rd edition, ISBN 9783540847441(2008). https://doi.org/10.1007/978-3-540-77974-2

[9] Kunszt, P. Z.. Szalay. A. S., Csabai, I., Thakar. A. R. 2000, in ASP Conf.Ser.. Vol. 216. Astronomical Data Analysis Software and Systems IX. cds. N.Manset, C. Veillet, D. Crabtree (SanP'raucisco:ASP), 141

[10] P. Z. Kunszt, A. S. Szalay, and A. R. Thakar. The hierarchical triangular mesh. In Miningthesky, pages 631–637. Springer,2001. https://doi.org/10.1007/10849171_83

[11] S. Szalay, J. Gray, G. Fekete, P.Z. Kunszt, P. Kukol, and A. Thakar, “Indexing the Sphere with the Hierarchical Triangular Mesh,” Micr. Res. Tech. Rpt.,MSR-TR-2005-123, 2005

[12] K.M. Górski, E. Hivon, A.J. Banday, B.D. Wandelt, F.K. Hansen, M. Reinecke, M. Bartelmann, HEALPix: a framework for high-resolution discretization and fast analysis of data distributed on the sphere, Astrophys. J. 622 (2) (2005) 759–771. https://doi.org/10.1086/427976

[13] O’Mullane, A. Banday, K. Gorski, P. Kunszt, and A. Szalay, “Splitting the sky-htm and healpix,” in Miningthe Sky. Springer, 2000, pp. 638–648

[14] Michael Rilee, Niklas Griessbaum, Kwo-SenKuo, James Frew, and Robert Wolfe. 2020. STARE-based Integrative Analysis of Diverse Data Using Dask Parallel Programming Demo Paper. In Proceedings of ACMSIGSPATIAL conference (SIGSPATIAL’20). ACM, NewYork, NY, USA, 4pages. https://doi.org/10.1145/3397536.3422346

[15] Rilee M, Kuo K, Clune T, etal. Addressing  the big-earth-data variety challenge with the hierarchical triangular mesh. 2016 IEEE International Conferenceon Big Data (Big Data); 2016 Dec 5-8; Washington, DC,USA: IEEE; p. 1006–1011. https://doi.org/10.1109/BigData.2016.7840700

[16] O. Esen, V. Tongur, I. B. Gundogdu HEALPix Mapping Technique and Cartographical Application May 2013 Conference: 26th International Cartographic Conference At: Dresden, Germany

[17] list class |Microsoft Learn.Retrieved from:https://learn.microsoft.com/en-us/cpp/standard-library/list-class

[18] set class | Microsoft Learn. Retrieved from:https://learn.microsoft.com/en-us/cpp/standard-library/set