Calculate Distance From One Point To All Others

I am working with a list of ID, X, and Y data for fire hydrant locations. I am trying to find the three closest fire hydrants for each fire hydrant in the list. a = [[ID, X, Y],[ID

Solution 1:

You do not have to calculate all distances of all points to all others to get the three nearest neighbours for all points.

A kd-tree search will be much more efficient due to its O(log n) complexity instead of a O(n**2) time complexity for the brute force method (calculating all distances).

Example

import numpy as np
from scipy import spatial

#Create some coordinates and indices#It is assumed that the coordinates are unique (only one entry per hydrant)
Coords=np.random.rand(1000*2).reshape(1000,2)
Coords*=100
Indices=np.arange(1000) #Indices defget_indices_of_nearest_neighbours(Coords,Indices):
  tree=spatial.cKDTree(Coords)
  #k=4 because the first entry is the nearest neighbour # of a point with itself
  res=tree.query(Coords, k=4)[1][:,1:]
  return Indices[res]

Solution 2:

Here you go. Let's say you have an input list with this format [[ID, X, Y],[ID, X, Y]].

You can simply loop through each hydrant when looping through each hydrant and calculate the min distance between them. You just need to have some variable to store the min distance for each hydrant and the ID of the closest hydrant.

import math # for sqrt calculationdefdistance(p0, p1):
    """ Calculate the distance between two hydrant """return math.sqrt((p0[1] - p1[1])**2 + (p0[2] - p1[2])**2)


input = [[0, 1, 2], [1, 2, -3], [2, -3, 5]] # your input list of hydrantfor current_hydrant ininput:  # loop through each hydrant
    min_distance = 999999999999999999999999
    closest_hydrant = 0for other_hydrant ininput:  # loop through each other hydrantif current_hydrant != other_hydrant:
            curr_distance = distance(current_hydrant, other_hydrant) # call the distance functionif curr_distance < min_distance: # find the closet hydrant
                min_distance = curr_distance
                closest_hydrant = other_hydrant[0]
    print("Closest fire hydrants to the", current_hydrant[0], "is the hydrants",
          closest_hydrant, "with the distance of", min_distance)  # print the closet hydrant

Since the distance function is not very complicated i rewrite it, you can use some other function in scipy or numpy library to get the distance.

Hope this can help ;)

Solution 3:

If you have geolocation, we can perform simple distance calculation(https://en.m.wikipedia.org/wiki/Haversine_formula) to get kilometers distance between two locations. This code is NOT meant to be efficient. If this is what you want we can use numpy to speed it up:

import math

def distance(lat,lon, lat2,lon2):

    R = 6372.8  # Earth radius in kilometers

    # change lat and lon to radians to find diff

    rlat = math.radians(lat)
    rlat2 = math.radians(lat2)
    rlon = math.radians(lon)
    rlon2 = math.radians(lon2)

    dlat = math.radians(lat2 - lat)
    dlon = math.radians(lon2 - lon)


    m = math.sin(dlat/2)**2 + \
        math.cos(rlat)*math.cos(rlat2)*math.sin(dlon/2)**2

    return 2 * R * math.atan2(math.sqrt(m),
                               math.sqrt(1 - m))

a = [['ID1', 52.5170365, 13.3888599],
     ['ID2', 54.5890365, 12.5865499],
     ['ID3', 50.5170365, 10.3888599],
    ]

b = []  
for id, lat, lon in a:
    for id2, lat2, lon2 in a:
        if id != id2:
            d = distance(lat,lon,lat2,lon2)
            b.append([id,id2,d])

print(b)