Алгоритм для покрытия максимального числа очков одним кругом данного радиуса

Проблема возвращается к поиску глобального оптимума функции f : R x R -> N . Входными данными для f является центральная точка круга, а значение, конечно же, является количеством включенных точек из набора. График функции будет прерывистым, лестничным.

Вы можете начать с тестирования функции в каждой точке, соответствующей точке в наборе, упорядочить точки, уменьшив значения f , затем активизировать поиск вокруг этих точек (например, двигаясь по спирали ).

Другой вариант - рассмотреть все точки пересечения отрезков, соединяющих любые пары точек в наборе. Я думаю, ваша оптимальная точка будет на одном из этих пересечений, но их количество, вероятно, слишком велико, чтобы рассматривать.

Вы также можете скрещивать варианты 1 и 2 и учитывать пересечения сегментов, сгенерированных из точек, вокруг «хороших заданных точек».

В любом случае, если количество заданных точек невелико (позволяющее проверять все пересечения), я не думаю , что вы можете гарантировать нахождение оптимума (просто хорошее решение).

Вы можете пикселизировать всю область, затем перейти к каждой точке и увеличить значение всех пикселей внутри круга радиуса вокруг этой точки. Пиксели с наибольшей суммой - хорошие кандидаты.

Конечно, вы можете потерять несколько хороших участков или «галлюцинировать» хорошие области из-за ошибок округления. Возможно, вы могли бы сначала попробовать сделать грубую пикселизацию, а затем уточнить перспективные области.

Могу я предложить карту плотности? Найдите минимальные и максимальные границы для x и y. Разделите диапазон границ x и y на ячейки, ширина которых равна диаметру вашего круга. Подсчитайте количество точек в каждой ячейке для x и y отдельно. Теперь найдите на вашей карте плотности пересечение между ячейкой x с наивысшим рейтингом и ячейкой y с самым высоким рейтингом.

Это ОЧЕНЬ быстрый алгоритм для быстрого обобщения больших наборов данных, но он не всегда точен. Для повышения точности вы можете разделить интервалы на более мелкие и мелкие части или сдвинуть позиции интервалов влево или вправо n раз и использовать система голосования для выбора ответа, который чаще всего встречается между испытаниями.

Это знаменитый K алгоритм ближайшей точки. Описано здесь: http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf

Это "проблема частичного покрытия диска" в литературе, которая должна дать вам хорошее место для начала поиска в Google. Вот статья, описывающая одно возможное решение, но оно немного сложное с математической точки зрения: Разработка аппроксимационных алгоритмов для задачи частичного покрытия диска

На самом деле, это относится к области, называемой вычислительной геометрией, которая увлекательна, но может трудно понять. ДеБерг сделал хороший обзор различных алгоритмов, связанных с этим предметом.

Если вы хотите что-то простое, возьмите случайную позицию (x, y), вычислите количество точек внутри круга и сравните с предыдущей позицией. Бери по максимуму. Повторите операцию в любое время.

Какого черта голос против? Вы когда-нибудь слышали о методах Монте-Карло? На самом деле для большого количества точек детерминированный алгоритм может не завершиться в разумные сроки.

Если верно, что точность не важна и алгоритм может делать небольшие ошибки, то я думаю следующее.

Пусть f(x,y) - функция, которая имеет максимум в точке (0,0) и значима только в точках внутри окружности радиуса R. Например, f(x,y) = e^{(x^2 + y^2)/ (2 * R^2)}.

Пусть (x_i,y_i) - точки и E_i(x,y) = f(x - x_i, y - y_i).

Ваша задача - найти максимум \sum_i E_i(x,y) .

Вы можете использовать градиентный спуск, начиная его из каждой точки.

На первый взгляд, я бы сказал, что это решение четырехмерного дерева.

Также существует метод визуализации информации/добычи данных под названием K-means, который создает кластеры из заданных данных. Его можно использовать с дополнительной функциональностью в конце, чтобы соответствовать вашим целям.

Основной алгоритм K-Means следующий:

1. Поместите K точек в пространство, представленное элементами. которые подвергаются кластеризации - эти точки представляют собой начальные центроиды групп
2. Присвоить каждый элемент данных группе, которая имеет самый близкий центроид
3. Когда все элементы будут назначены, пересчитайте пересчитайте положение K центроидов, вычислив среднее положение ваших точек
4. Повторяйте шаги 2 и 3, пока центроиды не перестанут двигаться или будут двигаться очень слабо

Добавленная функциональность будет следующей:

5. Подсчитать количество точек в окружности, расположенных на K центроидах
6. Выбрать тот, который подходит вам больше всего ;)

Источники:
Алгоритм K-means - Linköping University
Quadtree - en.wikipedia.org/wiki/Quadtree

Быстрый поиск в Википедии и вы найдете исходный код: en.wikipedia.org/wiki/K-means_clustering