CODEWITHSUNDEEP
pythonnumpy
Nahush Rai
Nahush Rai

Reputation: 11

How do i group points together within a range large space

I have 73,000 points with (x,y) coordinates in a space 2200x1700 I want to group all the (x,y) points together which fall in the circle with a radius of 35units. To do this I have to run nested for loops having a time complexity of O(73000x73000) as i am computing the distance between each point and grouping the points whos computed distance is less than 35.

I need a optimized solution for this !

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

Upvotes: 0

Views: 382

Answers (1)

xashru
xashru

Reputation: 3590

One optimization you can do is sort the points according to their x coordinates. Then for each point you need to consider just the points that have x coordinates within 35 difference of that point. With binary search you can find the points that are within this strip (i.e., find points (x1, y1) such that abs(x-x1) <= 35). Roughly the steps are

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

Upvotes: 2

Related Questions