Подтвердить что ты не робот

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

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

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

Вот пример картинки:
Example

Input:
  int n (n <= 50) – количество баллов,
  float x[n] и float y[n] – массивы с координатами X и Y точек

  float r – радиус круга.

Вывод:
  float cx и float cy – координаты центра окружности

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

Код С++ является предпочтительным, но не обязательным.

4b9b3361

ОТВЕТЫ

Ответ 1

Отредактировано в лучшую редакцию, как это было предложено:

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

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

Алгоритм:

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

Ответ 2

Это "проблема частичного покрытия диска" в литературе - это должно дать вам хорошее место для начала поиска в Интернете. Здесь бумага, охватывающая одно возможное решение, но немного математически математически: http://www.utdallas.edu/~edsha/papers/bin/ISPAN04_cover.pdf

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

Ответ 3

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

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

Ответ 4

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

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

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

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

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

Ответ 5

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

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

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

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

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

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

Источники:
К-мерный алгоритм - Университет Линчёпинга
Quadtree - en.wikipedia.org/wiki/Quadtree

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

Ответ 6

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

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

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

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

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

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

Детерминированный подход более эффективный, чем грубой силы

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

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

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

Ответ 7

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

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

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

Ответ 8

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

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

Ответ 9

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

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