Obtenha a distância mais próxima com dois geodataframe nos pandas

14

Aqui está meu primeiro geodatframe:

!pip install geopandas
import pandas as pd
import geopandas

city1 = [{'City':"Buenos Aires","Country":"Argentina","Latitude":-34.58,"Longitude":-58.66},
           {'City':"Brasilia","Country":"Brazil","Latitude":-15.78 ,"Longitude":-70.66},
         {'City':"Santiago","Country":"Chile ","Latitude":-33.45 ,"Longitude":-70.66 }]
city2 =  [{'City':"Bogota","Country":"Colombia ","Latitude":4.60 ,"Longitude":-74.08},
           {'City':"Caracas","Country":"Venezuela","Latitude":10.48  ,"Longitude":-66.86}]
city1df = pd.DataFrame(city1)
city2df = pd.DataFrame(city2)
gcity1df = geopandas.GeoDataFrame(
    city1df, geometry=geopandas.points_from_xy(city1df.Longitude, city1df.Latitude))
gcity2df = geopandas.GeoDataFrame(
    city2df, geometry=geopandas.points_from_xy(city2df.Longitude, city2df.Latitude))

Cidade1

           City    Country  Latitude  Longitude                     geometry
0  Buenos Aires  Argentina    -34.58     -58.66  POINT (-58.66000 -34.58000)
1      Brasilia     Brazil    -15.78     -47.91  POINT (-47.91000 -15.78000)
2      Santiago      Chile    -33.45     -70.66  POINT (-70.66000 -33.45000)

e meu segundo geodataframe: City2:

         City    Country  Latitude  Longitude                     geometry
1        Bogota   Colombia      4.60     -74.08    POINT (-74.08000 4.60000)
2       Caracas  Venezuela     10.48     -66.86   POINT (-66.86000 10.48000)

eu gostaria do terceiro dataframe com a cidade mais próxima de city1 a city2 com a distância como:

           City    Country  Latitude  Longitude                     geometry    Nearest    Distance
0  Buenos Aires  Argentina    -34.58     -58.66  POINT (-58.66000 -34.58000)    Bogota    111 Km

Aqui está minha solução atual usando geodjango e dict (mas é muito longo):

from django.contrib.gis.geos import GEOSGeometry
result = []
dict_result = {}
for city01 in city1 :
  dist = 99999999
  pnt = GEOSGeometry('SRID=4326;POINT( '+str(city01["Latitude"])+' '+str(city01['Longitude'])+')')
  for city02 in city2:
    pnt2 = GEOSGeometry('SRID=4326;POINT('+str(city02['Latitude'])+' '+str(city02['Longitude'])+')')
    distance_test = pnt.distance(pnt2) * 100
    if distance_test < dist :
      dist = distance_test
  result.append(dist)
  dict_result[city01['City']] = city02['City']

Aqui estão minhas tentativas:

from shapely.ops import nearest_points
# unary union of the gpd2 geomtries 
pts3 = gcity2df.geometry.unary_union
def Euclidean_Dist(df1, df2, cols=['x_coord','y_coord']):
    return np.linalg.norm(df1[cols].values - df2[cols].values,
                   axis=1)
def near(point, pts=pts3):
     # find the nearest point and return the corresponding Place value
     nearest = gcity2df.geometry == nearest_points(point, pts)[1]

     return gcity2df[nearest].City
gcity1df['Nearest'] = gcity1df.apply(lambda row: near(row.geometry), axis=1)
gcity1df

aqui :

    City    Country     Latitude    Longitude   geometry    Nearest
0   Buenos Aires    Argentina   -34.58  -58.66  POINT (-58.66000 -34.58000)     Bogota
1   Brasilia    Brazil  -15.78  -70.66  POINT (-70.66000 -15.78000)     Bogota
2   Santiago    Chile   -33.45  -70.66  POINT (-70.66000 -33.45000)     Bogota

Saudações

user462794
fonte
Olá e bem-vindo ao StackOverflow! Você parece ter a impressão de que o StackOverflow é um site em que você publica um problema e recebe algum código em troca. De fato, não é esse o caso. Sua pergunta provavelmente será encerrada ou mesmo excluída em breve. Para impedir que isso aconteça no futuro, faça o tour e dê uma olhada no centro de ajuda . Em particular, torne-se familiar quanto ao que é considerado tópico por aqui
azro
Além disso, quando você postar sobre DF, poste código pyhton com o conteúdo do DF, para todas as pessoas que gostariam de ajudá-lo a não escrever por conta própria
azro
@ azro eu editei e adicionei minha solução ao problema e aos meus dados iniciais.
user462794
são suas cidades apenas na América do Sul? Caso contrário, a que distância eles podem estar um do outro? Quantas cidades podem estar na cidade1 e quantas na cidade2? É importante encontrar a solução mais rápida ou uma solução mais simples, executada em um tempo razoável, OK? Se este for o caso, qual seria um tempo razoável?
Walter Tross
@ WalterTross minha cidade está em todo o mundo e estou procurando a solução fastet. Graças
user462794

Respostas:

11

Em primeiro lugar, mesclo dois quadros de dados por junção cruzada. E então, eu encontrei a distância entre dois pontos usando mapem python. Eu uso map, porque na maioria das vezes é muito mais rápido do que apply, itertuples, iterrowsetc. (Referência: https://stackoverflow.com/a/52674448/8205554 )

Por fim, agrupo por quadro de dados e busco valores mínimos de distância.

Aqui estão bibliotecas,

import pandas as pd
import geopandas
import geopy.distance
from math import radians, cos, sin, asin, sqrt

Aqui estão as funções usadas,

def dist1(p1, p2):
    lon1, lat1, lon2, lat2 = map(radians, [p1.x, p1.y, p2.x, p2.y])

    dlon = lon2 - lon1 
    dlat = lat2 - lat1 
    a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
    c = 2 * asin(sqrt(a)) 

    return c * 6373

def dist2(p1, p2):
    lon1, lat1, lon2, lat2 = map(radians, [p1[0], p1[1], p2[0], p2[1]])

    dlon = lon2 - lon1 
    dlat = lat2 - lat1 
    a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
    c = 2 * asin(sqrt(a)) 

    return c * 6373

def dist3(p1, p2):
    x = p1.y, p1.x
    y = p2.y, p2.x

    return geopy.distance.geodesic(x, y).km

def dist4(p1, p2):
    x = p1[1], p1[0]
    y = p2[1], p2[0]

    return geopy.distance.geodesic(x, y).km

E dados,

city1 = [
  {
    'City': 'Buenos Aires',
    'Country': 'Argentina',
    'Latitude': -34.58,
    'Longitude': -58.66
  },
  {
    'City': 'Brasilia',
    'Country': 'Brazil',
    'Latitude': -15.78,
    'Longitude': -70.66
  },
  {
    'City': 'Santiago',
    'Country': 'Chile ',
    'Latitude': -33.45,
    'Longitude': -70.66
  }
]

city2 = [
  {
    'City': 'Bogota',
    'Country': 'Colombia ',
    'Latitude': 4.6,
    'Longitude': -74.08
  },
  {
    'City': 'Caracas',
    'Country': 'Venezuela',
    'Latitude': 10.48,
    'Longitude': -66.86
  }
]


city1df = pd.DataFrame(city1)
city2df = pd.DataFrame(city2)

Junção cruzada com geopandasquadros de dados,

gcity1df = geopandas.GeoDataFrame(
    city1df, 
    geometry=geopandas.points_from_xy(city1df.Longitude, city1df.Latitude)
)
gcity2df = geopandas.GeoDataFrame(
    city2df, 
    geometry=geopandas.points_from_xy(city2df.Longitude, city2df.Latitude)
)

# cross join geopandas
gcity1df['key'] = 1
gcity2df['key'] = 1
merged = gcity1df.merge(gcity2df, on='key')

mathfunções e geopandas,

# 6.64 ms ± 588 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%%timeit

# find distance
merged['dist'] = list(map(dist1, merged['geometry_x'], merged['geometry_y']))

mapping = {
    'City_x': 'City',
    'Country_x': 'Country',
    'Latitude_x': 'Latitude',
    'Longitude_x': 'Longitude',
    'geometry_x': 'geometry',
    'City_y': 'Nearest',
    'dist': 'Distance'
}

nearest = merged.loc[merged.groupby(['City_x', 'Country_x'])['dist'].idxmin()]
nearest.rename(columns=mapping)[list(mapping.values())]

           City    Country  Latitude  Longitude                     geometry  \
2      Brasilia     Brazil    -15.78     -70.66  POINT (-70.66000 -15.78000)   
0  Buenos Aires  Argentina    -34.58     -58.66  POINT (-58.66000 -34.58000)   
4      Santiago     Chile     -33.45     -70.66  POINT (-70.66000 -33.45000)   

  Nearest     Distance  
2  Bogota  2297.922808  
0  Bogota  4648.004515  
4  Bogota  4247.586882 

geopye geopandas,

# 9.99 ms ± 764 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%%timeit

# find distance
merged['dist'] = list(map(dist3, merged['geometry_x'], merged['geometry_y']))

mapping = {
    'City_x': 'City',
    'Country_x': 'Country',
    'Latitude_x': 'Latitude',
    'Longitude_x': 'Longitude',
    'geometry_x': 'geometry',
    'City_y': 'Nearest',
    'dist': 'Distance'
}

nearest = merged.loc[merged.groupby(['City_x', 'Country_x'])['dist'].idxmin()]
nearest.rename(columns=mapping)[list(mapping.values())]

           City    Country  Latitude  Longitude                     geometry  \
2      Brasilia     Brazil    -15.78     -70.66  POINT (-70.66000 -15.78000)   
0  Buenos Aires  Argentina    -34.58     -58.66  POINT (-58.66000 -34.58000)   
4      Santiago     Chile     -33.45     -70.66  POINT (-70.66000 -33.45000)   

  Nearest     Distance  
2  Bogota  2285.239605  
0  Bogota  4628.641817  
4  Bogota  4226.710978 

Se você deseja usar em pandasvez de geopandas,

# cross join pandas
city1df['key'] = 1
city2df['key'] = 1
merged = city1df.merge(city2df, on='key')

Com mathfunções,

# 8.65 ms ± 2.21 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)
%%timeit

# find distance
merged['dist'] = list(
    map(
        dist2, 
        merged[['Longitude_x', 'Latitude_x']].values, 
        merged[['Longitude_y', 'Latitude_y']].values
    )
)

mapping = {
    'City_x': 'City',
    'Country_x': 'Country',
    'Latitude_x': 'Latitude',
    'Longitude_x': 'Longitude',
    'City_y': 'Nearest',
    'dist': 'Distance'
}

nearest = merged.loc[merged.groupby(['City_x', 'Country_x'])['dist'].idxmin()]
nearest.rename(columns=mapping)[list(mapping.values())]

           City    Country  Latitude  Longitude Nearest     Distance
2      Brasilia     Brazil    -15.78     -70.66  Bogota  2297.922808
0  Buenos Aires  Argentina    -34.58     -58.66  Bogota  4648.004515
4      Santiago     Chile     -33.45     -70.66  Bogota  4247.586882

Com geopy,

# 9.8 ms ± 807 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%%timeit

# find distance
merged['dist'] = list(
    map(
        dist4, 
        merged[['Longitude_x', 'Latitude_x']].values, 
        merged[['Longitude_y', 'Latitude_y']].values
    )
)

mapping = {
    'City_x': 'City',
    'Country_x': 'Country',
    'Latitude_x': 'Latitude',
    'Longitude_x': 'Longitude',
    'City_y': 'Nearest',
    'dist': 'Distance'
}

nearest = merged.loc[merged.groupby(['City_x', 'Country_x'])['dist'].idxmin()]
nearest.rename(columns=mapping)[list(mapping.values())]

           City    Country  Latitude  Longitude Nearest     Distance
2      Brasilia     Brazil    -15.78     -70.66  Bogota  2285.239605
0  Buenos Aires  Argentina    -34.58     -58.66  Bogota  4628.641817
4      Santiago     Chile     -33.45     -70.66  Bogota  4226.710978
E. Zeytinci
fonte
essas distâncias são calculadas com uma fórmula aproximada que não leva em consideração o achatamento da Terra. Usando geopy.distance.distance()as mesmas distâncias são 3 (arredondada) 2285, 4629e 4227km.
Walter Tross
Verifico estes valores com o link: distance.to/-33.45,-70.66/4.6,-74.08 O que há de errado?
E. Zeytinci
além do fato de eu confiar mais geopy , como site confio em mais edwilliams.org/gccalc.htm , o que concorda geopy. O site da NOAA, nhc.noaa.gov/gccalc.shtml , diz que é baseado no primeiro, mas depois produz resultados diferentes. Provavelmente é baseado em uma versão antiga da primeira.
Walter Tross 31/01
5

Eu acho que é bastante difícil encontrar uma solução com uma complexidade de tempo melhor que O (m · n) , onde m e n são os tamanhos de city1ecity2 . Mantendo a comparação da distância (a única operação O (m · n)) simples e aproveitando as operações vetorizadas fornecidas por numpy e pandas, a velocidade não deve ser um problema para qualquer tamanho de entrada razoável.

A ideia é que, para comparar distâncias em uma esfera, você possa comparar as distâncias entre os pontos em 3D. A cidade mais próxima também é a mais próxima passando pela esfera. Além disso, você normalmente usa raízes quadradas para calcular distâncias, mas se precisar compará-las apenas, pode evitar as raízes quadradas.

from geopy.distance import distance as dist
import numpy as np
import pandas as pd

def find_closest(lat1, lng1, lat2, lng2):
    def x_y_z_of_lat_lng_on_unit_sphere(lat, lng):
        rad_lat, rad_lng = np.radians(lat), np.radians(lng)
        sin_lat, sin_lng = np.sin(rad_lat), np.sin(rad_lng)
        cos_lat, cos_lng = np.cos(rad_lat), np.cos(rad_lng)
        return cos_lat * cos_lng, cos_lat * sin_lng, sin_lat
    x1, y1, z1 = x_y_z_of_lat_lng_on_unit_sphere(lat1, lng1)
    x2, y2, z2 = x_y_z_of_lat_lng_on_unit_sphere(lat2, lng2)
    return pd.Series(map(lambda x, y, z:
                         ((x2-x)**2 + (y2-y)**2 + (z2-z)**2).idxmin(),
                         x1, y1, z1))

city1 = [{"City":"Tokyo",    "Ctry":"JP", "Latitude": 35.68972, "Longitude": 139.69222},
         {"City":"Pretoria", "Ctry":"ZA", "Latitude":-25.71667, "Longitude": 28.28333},
         {"City":"London",   "Ctry":"GB", "Latitude": 51.50722, "Longitude": -0.12574}]
city2 = [{"City":"Seattle",  "Ctry":"US", "Latitude": 47.60972, "Longitude":-122.33306},
         {"City":"Auckland", "Ctry":"NZ", "Latitude":-36.84446, "Longitude": 174.76364}]
city1df = pd.DataFrame(city1)
city2df = pd.DataFrame(city2)

closest = find_closest(city1df.Latitude, city1df.Longitude, city2df.Latitude, city2df.Longitude)

resultdf = city1df.join(city2df, on=closest, rsuffix='2')
km = pd.Series(map(lambda latlng1, latlng2: round(dist(latlng1, latlng2).km),
                   resultdf[['Latitude',  'Longitude' ]].to_numpy(),
                   resultdf[['Latitude2', 'Longitude2']].to_numpy()))
resultdf['Distance'] = km
print(resultdf.to_string())
#        City Ctry  Latitude  Longitude     City2 Ctry2  Latitude2  Longitude2  Distance
# 0     Tokyo   JP  35.68972  139.69222   Seattle    US   47.60972  -122.33306      7715
# 1  Pretoria   ZA -25.71667   28.28333  Auckland    NZ  -36.84446   174.76364     12245
# 2    London   GB  51.50722   -0.12574   Seattle    US   47.60972  -122.33306      7723

Observe que qualquer solução que use latitude e longitude como se fossem coordenadas cartesianas está errada, porque, movendo-se para os polos, os meridianos (linhas de igual longitude) se aproximam.

Walter Tross
fonte
3

Essa solução provavelmente não é a maneira mais rápida de resolver seu problema, mas acredito que isso funcionará.

#New dataframe is basicly a copy of first but with more columns
gcity3df = gcity1df.copy()
gcity3df["Nearest"] = None
gcity3df["Distance"] = None

#For each city (row in gcity3df) we will calculate the nearest city from gcity2df and 
fill the Nones with results

for index, row in gcity3df.iterrows():
    #Setting neareast and distance to None, 
    #we will be filling those variables with results

    nearest = None
    distance = None
    for df2index, df2row in gcity2df.iterrows():
        d = row.geometry.distance(df2row.geometry)
        #If df2index city is closer than previous ones, replace nearest with it
        if distance is None or d < distance:
            distance = d
            nearest = df2row.City 
    #In the end we appends the closest city to gdf
    gcity3df.at[index, "Nearest"] = nearest
    gcity3df.at[index, "Distance"] = distance

Se você precisar trabalhar em medidores e não em graus, sempre poderá reprojetar sua camada (isso também apagará o erro que Walter está dizendo). Você pode fazer isso gcity3df = gcity3df.to_crs({'init': 'epsg:XXXX'})onde XXXX é o código epsg para crs sendo usados ​​em sua região mundial.

Mativane
fonte