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

Есть плоскость (размером ~2000х2000), на которой разбросаны точки (массив точек) с координатами [x,y]. Известно, что точно есть максимальное скопление. Его надо найти. Массив точек известен.

Единственное, что пришло в голову — просканировать всю плоскость окошком, и посмотреть, сколько в него попало точек. Где больше всего — там и скопление.
Но я точно не первый, кто столкнулся с такой задачкой, и может быть есть другие, более «скоростные» и чётко настроенные алгоритмы?

UPD
Скопление точек,- это… эээ… скопление точек… Место, в котором плотность точек максимальна.
Например, вот такая штука получается, если полученный массив отобразить графически:

Невооруженным взглядом виден максимум.
Есть ли какие-нибудь скоростные алгоритмы для его поиска?
  • Вопрос задан
  • 8169 просмотров
Решения вопроса 1
FrostMoon
@FrostMoon
ИМХО, для данной задачи, где не до конца ясна цель. Если есть площадь A-C по ширине, 1-3 по высоте.
Пройтись вектором-сканером по ширине А(1-3), B(1-3), C(1-3), и понять на какой отметке больше всего точек, потом так же пройтись по высоте 1(A-C), 2(A-C), 3(A-C) так же получить отметку где скопление точек плотнее. ну и пересечение 2х этих отметок и будет место максимального скопления.
Ответ написан
Пригласить эксперта
Ответы на вопрос 17
Monnoroch
@Monnoroch
Кстати, если вам не нравятся графические эвристики — есть способ даже лучше.
А именно посчитать мат. ожидание и дисперсию вашего списка точек. Это займет линейное время, а требуемой областью скорее всего будет круг с центром в мат. ожидании и радиусом в корень из дисперсии.
Не уверен, что всегда сработает именно такая постановка — может оказаться слишком большой разброс, однако очевидным плюсом будет линейное время работы. А сложные штуки с ползающей рамкой можно применять как запасной метод на случай большой дисперсии.
Ответ написан
Mrrl
@Mrrl
Заводчик кардиганов
Задача сия мне попадалась неоднократно. В разных размерностях (от 1 до 6, причем шестимерное пространство было совсем не декартовым — оно описывало перемещения трехмерного пространства) и с разным числом точек, но всегда без точной формулировки. Хорошего решения я, кажется, не написал ни разу, каждый раз махал рукой и шел другим путем. Но мысли остались следующие.
1) без понятия «масштаб» задача не имеет смысла. То есть, прежде чем решать ее, надо задаться неким «размером окошка», «радиусом размытия точки», «шириной серой зоны» и т.п.
2) чаще всего этот размер заранее неизвестен. Если взять его с запасом, то результат будет правдоподобен, но неточен а если размер окажется слишком маленьким, то наоборот, найдется локальное скопление среди пустоты. Лучше всего, наверное, выбрать убывающую последовательность r1>r2>r3>r4… (например, для окна 2000х2000 это моут быть степени двойки от 128 до 8), найти квадрат со стороной r1, содержащий максимальное количество точек, в нем — квадрат со стороной r2, и т.д. В этом случае наш результат будет правдоподобен во всем диапазоне масштабов.
3) Искать границы квадратов с точностью до пикселя смысла нет. Если мы ищем квадрат NxN, то достаточно перебрать квадраты с шагом N/4 по каждой координате. Например, если мы ищем квадрат 128х128 на плоскости размером 2000х2000, то достаточно рассмотреть 3600 возможных положений этого квадрата (вершина имеет координаты от 0 до 1888 с шагом 32). Завести целочисленный массив такого размера. Каждая точка попадает в 16 квадратов (или меньше) — увеличить 16 ячеек на 1. Найти максимальную — она даст стартовый квадрат.
После этого в этом квадрате перебрать 25 квадратов 64х64, в максимальном из них 25 квадратов 32х32 и т.д.
Если r1 выбран слишком маленьким, а плоскость была слишком большой, то вместо массива (который был 60х60) можно воспользоваться каким-нибудь деревом (для экономии памяти и времени на инициализацию).
Не исключено, что имеет смысл просмотреть не одну последовательность квадратов, а несколько (выбрать 10 квадратов размером r1 с наибольшим весом, из всех квадратов со стороной r2, лежащих в них — 10 наибольших и т.д.) Но это будет писать сложнее, а сработает оно только если скопление выражено нечетко, а где-то есть разреженная туманность. Впрочем, в этой ситуации надо сразу уменьшать r1.
Ответ написан
Комментировать
lsdima
@lsdima
Просто уменьшите всё ваше поле в 10-100 раз, с округлением координат точек до целого числа, затем пройдитесь по уменьшенному полю и найдите на какую координату поля приходится наибольшее количество точек. Если таких координат несколько, сравните эти области в оригинальном размере.
Ответ написан
Комментировать
Monnoroch
@Monnoroch
Решение станет понятнее, если определиться с задачей. Я вот не очень понимаю, что такое скопление точек, да еще и максимальное.
1) Есть много вариантов: такой квадрат со стороной A, что в него попадает точек больше, чем в любой другой квадрат с такой же стороной.
2) То же, только с кругом и радиусом.
3) Такая точка плоскости, что сумма расстояний до всех данных точек минимальна.
И это только навскидку.

Для разных задач решения разные.
Ответ написан
Monnoroch
@Monnoroch
Чтобы найти данное скопление достаточно применить к картинке фильтр усреднения цвета. Он сотрет все одинокие точки, а пятно оставит да еще и размоет, убрав шум. Искать пятно легко, много алгоритмов готовых есть. Но что вы будете делать, если явного пятна не будет?
Ответ написан
@Eddy_Em
В <a href=«habrahabr.ru/blogs/image_processing/134352/>похожей задаче я просто пользовался медианным усреднением.
Как и говорили выше, если вычислить среднеквадратичное отклонение (но не от среднего, а от медианы), с большой надежностью (чем больше точек — тем лучше) получим что-то вроде центра тяжести, вокруг которого в круге с радиусом σ будет находиться наибольшее количество точек.

Еще вариант: как было предложено выше. Т.е. преобразовать эти точки в изображение, дискретизуя с большим шагом. Найдя „пиксель“ с наибольшей интенсивностью (количеством точек) перейти к меньшей дискретизации. Эдакая вариация дихотомии.

Есть еще вариант: построить вокруг точек выпуклые непересекающиеся оболочки максимальной площади, содержащие ровно по одной точке. Функция распределения площади оболочек от координат даст понятие распределения плотности точек. Но эта задача сложна математически, да и вряд ли нужно так усложнять, когда предыдущие способы вполне сгодятся.
Ответ написан
Комментировать
lashtal
@lashtal
Вам, думаю, подойдет этот ответ:
stackoverflow.com/questions/356035/algorithm-for-detecting-clusters-of-dots
Ответ написан
Комментировать
Sekira
@Sekira
Делим массив на два четырехугольника, считаем в каждом, в котором больше, опять делим на два, считаем, снова делим на 2 считаем, и так сколько надо раз, пока не будет четырехугольник нужной точности. В идеале надо дойти до 1 точки, и из неё уже делать квадрат, круг или нужную фигуру, нужным размером.
Ответ написан
Alroniks
@Alroniks
MODX Джедай, работаю с Laravel
помнится еще в университета с точками этими возились. сейчас алгоритм не помню, но считали расстояния между точками и по нему определяли разбросанные. цель задачи не помню, но могу выяснить если напомните завтра днем.
Ответ написан
Skiminok
@Skiminok
Попробуйте поиграться с DBSCAN. Если установить в нем параметр плотности достаточно большим, то алгоритм скорее всего найдет в вашем массива ровно один кластер — искомое скопление точек.
Ответ написан
Комментировать
alexius2
@alexius2
При размерах плоскости 2000x2000 в большинстве случаев вполне можно обойтись полным перебором вашим алгоритмом (всего-то ~ 4 млн вариантов). Причем алгоритм можно сильно ускорить, если сдвигать окно сразу на несколько единиц. Например, если сдвигать окно на 5 единиц (точек), то будет всего 160 тысяч вариантов.
При больших объемах данных можно придумать итеративный алгоритм с уменьшающимися размерами окна и сдвига.
Ответ написан
Комментировать
pixxxel
@pixxxel
Используйте что-то похожее на алгоритм «K ближайших соседей». Грубо говоря, для каждой точки посчитайте расстояния до k ближайших соседей, и у кого сумма этих расстояний будет меньше, те точки находятся ближе к эпицентру :) Таким образом можно найти кучку «центральных» точек.
Если делать это динамическим программированием, то будет работать не очень медленно
Ответ написан
darkdimius
@darkdimius
А вероятностный алгоритм вам не подойдет?
А именно: если в ожидаемом окне k точек из n — выбираем случайную точку как искомую, рассматриваем окна ее содержащие.
Вероятность того, что за m попыток вы не найдете правильный ответ — ((n-k)/n)^m.
Ответ написан
Комментировать
@relgames
Java Developer
Первое, что пришло в голову — для начала взять квадрат (0,0) — (width, height) и потом каким-то образом сдвигать границы.

Второе — нумеровать точки через рекурсию: для каждой не помеченной точки, f(i) = пометить точку номером i и вызвать себя же для всех не помеченных точек, расположенных на расстоянии < L от точки. Так мы пометим номерами все группы точек, внутри которых точки расположены друг от друга не дальше расстояния L.
Ну и потом нужно подсчитать, за каким номером больше всего точек (а можно и сразу считать).
Ответ написан
Комментировать
EndUser
@EndUser
Заменить точки кругами (радиус выбирать по вкусу): ввести дополнительную плоскость, на которой рисовать круги. Круги рисовать не цветом, а счётчиком — если зона накрыта 1 раз, то вписать «1», если 2 раза, то «2».
Это почти что «размазать точки графическим фильтром».
А потом с дополнительной плоскости снимать готовые результаты в виде ячеек с максимальным числом перекрытий. Или детекцией краёв изображения по определённой яркости, если рассуждать в терминах графических алгоритмов.
Ответ написан
RenegadeMS
@RenegadeMS
Выше уже написали про метод К-средних, думаю вам следует взять любой из общеизвестных методов кластеризации, там кроме К-средних есть и другие
Ответ написан
Комментировать
RxR
@RxR
Программист фрилансер -> разработчик в Inostudio
Алгоритм к-средних.
работает как-то так:
https://media1.giphy.com/media/12vVAGkaqHUqCQ/sour...
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
28 окт. 2021, в 05:45
1000 руб./за проект
28 окт. 2021, в 04:48
1200 руб./за проект
28 окт. 2021, в 03:00
500000 руб./за проект