Метод розв'язання двовимірної задачі розташування точок на регулярних сітках

Abstract

Задачі розташування точок часто виникають в таких галузях, як аналіз видимості об’єктів, визначення розташувань сенсорів, симуляції людських потоків, планування міських середовищ, керування мобільними роботами, нанесення фарб та плівок. В багатьох подібних задачах часто виникає необхідність визначення деякої множини точок, яка охоплює задані положення, наприклад, оглядові точки на поверхні, що спостерігається. Таку проблему можна розглядати із точки зору знаходження множини положень сенсору, що забезпечує максимальне охоплення точок множини за деяким критерієм досяжності, який в роботі сформульований на основі Евклідової метрики. Зазвичай, задача розташування об’єктів не має точного розв’язку, тому на практиці для її розв’язання використовують методи оптимізації, які не гарантують знаходження глобального оптимуму розв’язку. Це викликає необхідність пошуку більш ефективних методів для розв’язання задач розташування точок. В роботі представлено спосіб розв’язання задачі розташування множини точок, що забезпечує задане охоплення вхідної точкової множини за критерієм досяжності на основі нанесення кіл на регулярну (піксельну) сітку, та визначення точок сітки, які належать таким колам. Представлений метод дозволяє розв’язувати такі задачі за лінійний від кількості точок вхідної множини, час. В роботі наведено основні ітерації алгоритму для пошуку множини точок, яка охоплює задану множину, проведено експериментальне дослідження на тестових точкових множинах на площині, наведено приклади отриманих розв’язків. Представлений підхід складається з наступних кроків: формування критерію взаємної досяжності точок; визначення розмірності піксельної сітки та масиву-акумулятору; нанесення кіл заданого радіусу на сітку; визначення точок, що належать нанесеним колам; інкремент значень в акумуляторі.Ключові слова: задача розташування, точкова множина, взаємна досяжність точок, піксельна сітка, охоплення множини точок.Point location problems often arise in areas such as object visibility analysis, sensor location, human flow simulation, urban planning, mobile control, and paint and film application. In many such problems, it is often necessary to define a set of points that cover given positions, such as viepoints on the observed surface. This problem can be considered in terms of finding the set of sensor positions, which provides maximum coverage of the points of the set by some criterion of reachability, which is formulated in the paper on the basis of the Euclidean metric. Usually, the object location problem does not have an exact solution, so in practice, optimization methods are used to solve it, which do not guarantee finding a global optimum solution. This makes it necessary to find more effective methods for solving point location problems. The paper presents a method of solving the problem of location of a set of points, which provides a given coverage of the input point set by the criterion of reachability based on drawing circles on a regular (pixel) grid, and determining the grid points that belong to such circles. The presented method allows to solve such problems in a linear time from the number of points of the input set. The main iterations of the algorithm for finding a set of points covering a given set are presented, an experimental study on test point sets on a plane is performed, and examples of the obtained solutions are given. The presented approach consists of the following steps: formation of the criterion of mutual reach of points; determining the dimensions of the pixel grid and the battery array; drawing circles of a given radius on the grid; determination of points belonging to the applied circles; increment of values in the accumulator.