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

Question

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

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

Вот пример изображения:

Введите:
int n (n <= 50) - количество баллов; <br> float x[n] и float y[n] & ndash; массивы с координатами точек X и Y;
float r - радиус круга.

Выход:
float cx и float cy & ndash; координаты центра круга

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

Код C ++ предпочтителен, но не обязателен.

Answer 1

Отредактировано для лучшей формулировки, как предложено:

Основные наблюдения:

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

Тогда алгоритм таков:

• Для каждой пары точек, если их расстояние <2, вычислите две единичные окружности С1 и С2, которые проходят через них. </li>
• Вычислить количество точек вашего набора внутри C1 и C2
• Возьми макс.

Answer 2

Это «проблема частичного покрытия диска» в литературе, которая должна дать вам хорошее место, чтобы начать поиск в Google.Вот статья, в которой рассматривается одно из возможных решений, но математически оно немного интенсивно: http://www.utdallas.edu/~edsha/papers/bin/ISPAN04_cover.pdf

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

Answer 3

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

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

Answer 4

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

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

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

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

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

Answer 5

Вот две идеи: алгоритм аппроксимации O (n) и точный (не приближенный) алгоритм O (n ^ 2 log n):

Быстрое приближение

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

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

Это в основном линейное время с точки зрения количества точек, и вы можете на лету обновлять свой набор данных, чтобы постепенно получать новые ответы в постоянное время для каждой точки (постоянная относительно n = количество точек).

Подробнее о хэшах, чувствительных к локальности, в целом или о моей личной любимой версии, которая будет работать в этом случае .

Детерминистский подход лучше, чем грубая сила

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

Развертывание вокруг точки p может быть выполнено за n log n времени путем: (a) нахождения углового интервала для другой точки q, такого, что когда мы помещаем окружность под углом theta, то она содержит q; и (b) сортировка интервалов, чтобы мы могли маршировать / перемещаться вокруг p по линейному времени.

Таким образом, требуется O (n log n), чтобы найти лучший круг, касающийся фиксированной точки p, а затем умножить его на O (n), чтобы выполнить проверку для всех точек. Общее время O (n ^ 2 log n).

Answer 6

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

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

Основной алгоритм для K-средних:

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

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

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

Источники:
Алгоритм K-средних - Университет Линчёпинга
Quadtree - ru.wikipedia.org / wiki / Quadtree

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

Answer 7

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

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

Answer 8

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

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

Answer 9

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

Пусть 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) .

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

Answer 10

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