Получите ближайшее расстояние с двумя геоданных в пандах

14

Вот мой первый геодатфрейм:

!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))

City1

           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)

и мой второй геодатафрейм: 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)

я хотел бы третий датафрейм с ближайшим городом от города1 до города2 с расстоянием, как:

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

Вот мое реальное решение с использованием geodjango и dict (но это слишком долго):

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']

Вот мои попытки:

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

Вот :

    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

С уважением

user462794
источник
Здравствуйте и добро пожаловать в StackOverflow! Похоже, у вас сложилось впечатление, что StackOverflow - это сайт, на котором вы публикуете проблему и получаете взамен некоторый код. Это на самом деле не так. Ваш вопрос, скорее всего, будет закрыт или даже удален в ближайшее время. Чтобы этого не случилось в будущем, просмотрите экскурсию и обратитесь в справочный центр . В частности, познакомьтесь с тем, что здесь рассматривается по теме
Азро
Кроме того, когда вы пишете о DF, пожалуйста, публикуйте код Pyhton с контентом DF, для всех людей, которые хотели бы помочь вам не писать самостоятельно
azro
@azro Я отредактировал и добавил свое решение проблемы и мои исходные данные.
user462794
твои города только в Южной Америке? Если нет, как далеко они могут быть друг от друга? Сколько городов может быть в city1 и сколько в city2? Важно ли найти самое быстрое решение или более простое решение, которое работает в разумные сроки? Если последнее так, то какой будет разумный срок?
Уолтер Тросс
@WalterTross мой город по всему миру, и я ищу быстрое решение. Спасибо
user462794

Ответы:

11

Во-первых, я объединяю два фрейма данных путем перекрестного соединения. И тогда я нашел расстояние между двумя точками mapв Python. Я использую map, потому что в большинстве случаев это намного быстрее, чем apply, itertuplesи iterrowsт. Д. (Ссылка: https://stackoverflow.com/a/52674448/8205554 )

Наконец, я группирую по фрейму данных и выбираю минимальные значения расстояния.

Вот библиотеки,

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

Здесь используются функции,

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

И данные,

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)

Перекрестное соединение с geopandasфреймами данных,

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')

mathфункции и 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 

geopyи 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 

Если вы хотите использовать pandasвместо geopandas,

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

С mathфункциями,

# 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

С 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
Э. Зейтинчи
источник
эти расстояния рассчитываются по приближенной формуле, которая не учитывает выравнивание Земли. Используя geopy.distance.distance()те же 3 расстояния (округленно) 2285, 4629и 4227км.
Уолтер Тросс
Я проверяю эти значения по ссылке: distance.to/-33.45 , -70.66/4.6 , -74.08 Что не так?
Э. Зейтинчи
Помимо того, что я доверяю больше geopy, как веб-сайт, я доверяю больше edwilliams.org/gccalc.htm , с чем согласен geopy. Сайт NOAA, nhc.noaa.gov/gccalc.shtml , говорит, что он основан на первом, но затем дает другие результаты. Это вероятно основано на старой версии прежнего.
Уолтер Тросс
5

Я думаю, что довольно сложно найти решение с временной сложностью лучше, чем O (m · n) , где m и n - размеры city1иcity2 . Благодаря простоте сравнения расстояний (единственная операция O (m · n)) и использованию векторизованных операций, предоставляемых numpy и pandas, скорость не должна быть проблемой для любого разумного размера ввода.

Идея состоит в том, что для сравнения расстояний на сфере вы можете сравнить расстояния между точками в 3D. Самый близкий город - также самый близкий, проходящий через сферу. Кроме того, вы обычно берете квадратные корни для вычисления расстояний, но если вам нужно только сравнить их, вы можете избежать квадратных корней.

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

Обратите внимание, что любое решение, которое использует широту и долготу, как если бы они были декартовыми координатами, является неправильным, потому что, двигаясь к полюсам, меридианы (линии равной долготы) становятся ближе друг к другу.

Уолтер Тросс
источник
3

Возможно, это решение не самый быстрый способ решить вашу проблему, но я верю, что оно поможет.

#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

Если вам нужно работать в метрах, а не в градусах, вы всегда можете перепроектировать свой слой (это также устранит ошибку, которую Уолтер имеет в виду). Вы можете сделать это, gcity3df = gcity3df.to_crs({'init': 'epsg:XXXX'})если XXXX - это код epsg для crs, который используется в вашем регионе мира.

Mativane
источник