МЕТОД РЕШЕНИЯ ДВУМЕРНОЙ ЗАДАЧИ РАЗМЕЩЕНИЯ ТОЧЕК НА РЕГУЛЯРНЫХ СЕТКАХ

Аннотация

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