Учитывая набор точек на 2D-плоскости, я хочу найти наборы X точек, которые находятся в пределах Y друг от друга. Например:
8|
7| a b
6|
5| c
4|
3| e
2| d
1|
-------------------------
1 2 3 4 5 6 7 8 9 0 1
a, b, c и d - это точки на 2D-плоскости. При заданных аргументах 3 для количества точек (X) и 3 для расстояния (Y) алгоритм вернет [[a, b, c]]. Некоторые примеры:
algorithm(X = 3, Y = 3) returns [[a, b, c]]
algorithm(X = 2, Y = 3) returns [[a, b, c], [d, e]] -- [a, b, c] contains at least two points
algorithm(X = 4, Y = 3) returns [] -- no group of 4 points close enough
algorithm(X = 5, Y = 15) returns [[a, b, c, d, e]]
Ограничения:
- оси x и y (цифры выше) имеют длину 10000 единиц
- На графике 800 точек (a, b, c, d и т. Д.)
- Не думаю, что это имеет значение, но я использую JavaScript
Вещи, которые я пробовал:
- Я на самом деле беспокоюсь о выводе новых точек, которые близки к нескольким входным точкам, поэтому я попытался перебрать сетку и «оглядеть» ее, используя Пифагора, чтобы найти каждую точку на заданном расстоянии. Это слишком медленно, учитывая общую площадь. См. Источник здесь .
Вы также можете увидеть размер данных в тесте реальных данных .
- DBSCAN , что, кажется, имеет другую цель - я знаю, насколько большим я хочу, чтобы размер моего кластера был.
- Я в настоящее время пытаюсь сравнивать точки друг с другом и строить близкие пары, затем закрывать триплеты и т. Д. До конца, но, похоже, это тоже ведет к неэффективной дыре , Я собираюсь продолжить и попробовать что-то вроде хеширования или словаря, чтобы избежать этих циклов.