МЕТОД РОЗВ’ЯЗАННЯ ДВОВИМІРНОЇ ЗАДАЧІ РОЗТАШУВАННЯ ТОЧОК НА РЕГУЛЯРНИХ СІТКАХ

Анотація

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