УЗАГАЛЬНЕНИЙ МЕТОД ПРОСТОРОВОЇ ОБРОБКИ ТОЧКОВИХ МНОЖИН НА ПЛОЩИНІ

Анотація

Роботу присвячено розробці універсального підходу до розв’язання задач просторової обробки точкових множин на площині, до яких можна віднести задачі визначення сусідства точок, відстаней між точками, визначення взаємовпливу точок, визначення входження точок до деяких областей довільної геометричної форми, визначення метричних та просторових характеристик точкових множин, визначення розташувань точок на основі заданих метричних обмежень та генерація точкових множин. В таких задачах існує необхідність ефективного з точки зору часу обчислень розв’язання просторових задач на точкових множинах із великою кількістю точок, наприклад, визначення відстаней між об’єктами, пошук найближчих або найвіддаленіших об’єктів, визначення взаємовпливу об’єктів в залежності від їхніх взаємних розташувань. Існуючі методи для розв’язання подібних задач базуються на використання методів математичної оптимізації, є витратними за часом і не надають точних розв’язків. В роботі представлено узагальнений метод для розв’язання задач просторової обробки точкових множин на площині за рахунок використання просторової хеш-таблиці та масиву-акумулятору для зберігання дискретизованої регулярної сітки, які дозволяють за лінійний від кількості точок час визначати усі точки множини, що входять до деякої області впливу. Лінійність досягається за рахунок ланцюгових відображень координат точок з простору хешів до простору дискретизованої сітки. Представлений підхід складається з наступних кроків: формування критерію взаємної досяжності точок на основі обраної метрики; визначення розмірності дискретизованої сітки; індексація точок сітки; нанесення областей впливу заданої форми на сітку; визначення точок, що належать нанесеним областям; аналіз вагових значень в масиві-акумуляторі.Ключові слова: просторова обробка, точкова множина, взаємовплив точок, дискретизована регулярна сітка, просторове хешування.