Дана робота присвячена покращенню швидкодії обробки пошукових запитів до планарних дискретних моделей, що застосовуються в інженерному програмному забезпеченні. Розроблено структуру даних для пришвидшення пошуку елементів дискретизації на основі ієрархічної триангуляційної сітки. Розроблена індексаційна структура будується висхідним ітеративним алгоритмом, який конструює кожен новий рівень ієрархії на основі попереднього або індексованої триангуляції шляхом його спрощення, що забезпечує наскрізне збереження морфології триангуляційної сітки у всіх рівнях ієрархічної індексаційної структури. Розроблений алгоритм побудови забезпечує наявність деревоподібних зв’язків між рівнями ієрархічної триангуляційної сітки, що дозволяє низхідну навігацію між геометрично близькими трикутниками. Пришвидшення пошуку досягається завдяки виконанню направленого пошуку в верхньому рівні індексаційної структури та подальшої навігації між рівнями з використанням низхідних зв’язків, доки не буде знайдено трикутник індексованої дискретизації. Здійснена програмна реалізація засобами С++17, візуалізація триангуляційних сіток та ізоліній здійснена засобами бібліотеки ObjectARX. На основі програмної реалізації створено виконавчу бібліотеку.
[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
[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, https://doi.org/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 https://doi.org/10.1007/10849171_84
[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