Как группировать точки в пределах большого пространства

Question

У меня 73 000 точек с координатами (x, y) в пространстве 2200x1700 Я хочу сгруппировать все точки (x, y), которые попадают в круг с радиусом 35 единиц.Для этого мне нужно запустить вложенные циклы, имеющие временную сложность O (73000x73000), так как я вычисляю расстояние между каждой точкой и группирую точки, чье вычисленное расстояние меньше 35.

Мне нужен оптимизированныйрешение для этого!

temp_cluster=cluster
for key,value in cluster.items():
    pointa=np.array((key[0],key[1]))
    for key2,value2 in temp_cluster.items():
        pointb=np.array((key2[0],key2[1]))
        distance=np.linalg.norm(pointa-pointb)
        if(distance<=35):
            cluster[(key[0],key[1])]=cluster[(key[0],key[1])]+1## here we are counting how many points lies within a radius of 35 for that particular point

Answer 1

Одна оптимизация, которую вы можете сделать, это отсортировать точки в соответствии с их x координатами.Затем для каждой точки нужно учитывать только те точки, которые имеют x координаты в пределах 35 разницы этой точки.С помощью бинарного поиска вы можете найти точки, которые находятся в этой полосе (то есть найти точки (x1, y1), такие что abs(x-x1) <= 35). Примерно шаги

sort(points) according to their x coordinates
for each point (x, y):
    count = 0
    start_index = starting index of points with x-x1 >= 35 (find using binary search)
    end_index = end index of point with x1-x<=35 (find using binary search)
    for each point(x1, y1) in (start_index, end_index):
        distance = calculate_distance(x, y, x1, y1)
        if distance <= 35:
            count = count + 1
    cluster[(x,y)] = count