Побудова алгоритму та структури даних для пришвидшеного пошуку елементів дискретизації 2D-областей

Abstract

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