I need to take a list I have created and find the closest two points and print them out. How can I go about comparing each point in the list?
There isn’t any need to plot or anything, just compare the points and find the closest two in the list.
import math # 'math' needed for 'sqrt'
# Distance function
def distance(xi,xii,yi,yii):
sq1 = (xi-xii)*(xi-xii)
sq2 = (yi-yii)*(yi-yii)
return math.sqrt(sq1 + sq2)
# Run through input and reorder in [(x, y), (x,y) ...] format
oInput = ["9.5 7.5", "10.2 19.1", "9.7 10.2"] # Original input list (entered by spacing the two points).
mInput = [] # Manipulated list
fList = [] # Final list
for o in oInput:
mInput = o.split()
x,y = float(mInput[0]), float(mInput[1])
fList += [(x, y)] # outputs [(9.5, 7.5), (10.2, 19.1), (9.7, 10.2)]
asked Mar 23, 2011 at 15:50
It is more convenient to rewrite your distance() function to take two (x, y) tuples as parameters:
def distance(p0, p1):
return math.sqrt((p0[0] - p1[0])**2 + (p0[1] - p1[1])**2)
Now you want to iterate over all pairs of points from your list fList. The function iterools.combinations() is handy for this purpose:
min_distance = distance(fList[0], fList[1])
for p0, p1 in itertools.combinations(fList, 2):
min_distance = min(min_distance, distance(p0, p1))
An alternative is to define distance() to accept the pair of points in a single parameter
def distance(points):
p0, p1 = points
return math.sqrt((p0[0] - p1[0])**2 + (p0[1] - p1[1])**2)
and use the key parameter to the built-in min() function:
min_pair = min(itertools.combinations(fList, 2), key=distance)
min_distance = distance(min_pair)
answered Mar 23, 2011 at 15:58
Sven MarnachSven Marnach
567k117 gold badges934 silver badges834 bronze badges
7
I realize that there are library constraints on this question, but for completeness if you have N points in an Nx2 numpy ndarray (2D system):
from scipy.spatial.distance import pdist
x = numpy.array([[9.5,7.5],[10.2,19.1],[9.7,10.2]])
mindist = numpy.min(pdist(x))
I always try to encourage people to use numpy/scipy if they are dealing with data that is best stored in a numerical array and it’s good to know that the tools are out there for future reference.
answered Mar 23, 2011 at 17:40
JoshAdelJoshAdel
66.3k26 gold badges140 silver badges140 bronze badges
Note that the math.sqrt function is both slow and, in this case, unnecessary. Try comparing the distance squared to speed it up (sorting distances vs. distance squared will always produce the same ordering):
def distSquared(p0, p1):
return (p0[0] - p1[0])**2 + (p0[1] - p1[1])**2
answered Mar 23, 2011 at 16:05
Aaron DufourAaron Dufour
17.2k1 gold badge47 silver badges68 bronze badges
This might work:
oInput = ["9.5 7.5", "10.2 19.1", "9.7 10.2"]
# parse inputs
inp = [(float(j[0]), float(j[1])) for j in [i.split() for i in oInput]]
# initialize results with a really large value
min_distance = float('infinity')
min_pair = None
# loop over inputs
length = len(inp)
for i in xrange(length):
for j in xrange(i+1, length):
point1 = inp[i]
point2 = inp[j]
if math.hypot(point1[0] - point2[0], point1[1] - point2[0]) < min_distance:
min_pair = [point1, point2]
once the loops are done, min_pair should be the pair with the smallest distance.
Using float() to parse the text leaves room for improvement.
math.hypot is about a third faster than calculating the distance in a handwritten python-function
answered Mar 23, 2011 at 16:20
HumanCatfoodHumanCatfood
9611 gold badge7 silver badges20 bronze badges
Your fixed code. No efficient algorithm, just the brute force one.
import math # math needed for sqrt
# distance function
def dist(p1, p2):
return math.sqrt((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2)
# run through input and reorder in [(x, y), (x,y) ...] format
input = ["9.5 7.5", "10.2 19.1", "9.7 10.2"] # original input list (entered by spacing the two points)
points = [map(float, point.split()) for point in input] # final list
# http://en.wikipedia.org/wiki/Closest_pair_of_points
mindist = float("inf")
for p1, p2 in itertools.combinations(points, 2):
if dist(p1, p2) < mindist:
mindist = dist(p1, p2)
closestpair = (p1, p2)
print(closestpair)
answered Mar 23, 2011 at 16:06
orlporlp
112k36 gold badges215 silver badges312 bronze badges
5
First, some notes:
a**2 # squares a
(xi - xii)**2 # squares the expression in parentheses.
mInput doesn’t need to be declared in advance.
fList.append((x, y)) is more pythonic than using +=.
Now you have fList. Your distance function can be rewritten to take 2 2-tuple (point) arguments, which I won’t bother with here.
Then you can just write:
shortest = float('inf')
for pair in itertools.combinations(fList, 2):
shortest = min(shortest, distance(*pair))
answered Mar 23, 2011 at 16:03
nmichaelsnmichaels
49.2k12 gold badges106 silver badges135 bronze badges
3
Many of the above questions suggest finding square root using math.sqrt which is slow as well as not a good approach to find square root. In spite of using such approach just recall the basic concepts from school: think of taking the square root of any positive number, x. The square root is then written as a power of one-half: x½. Thus, a fractional exponent indicates that some root is to be taken.
so rather than using math.sqrt((p0[0] - p1[0])**2 + (p0[1] - p1[1])**2)
Use
def distance(a,b):
euclidean_distance = ((b[0]-a[0])**2 + (a[1]-a[1])**2)**0.5
return(euclidean_distance)
Hope it helps
answered Apr 17, 2020 at 13:14
Есть список с точками, и формула по которой необходимо найти расстояния между каждой точкой в списке.
Список выглядит так:
[(0, 1), (2, 4), (5, 1), (5, 5), (7, 2)]
В круглых скобках координаты точки x, y.
Формула:
((point_2[0] - point_1[0]) ** 2 + (point_2[1] - point_1[1]) ** 2) ** 0.5
Ну или http://900igr.net/prezentatsii/algebra/Prostejshie-zadachi-v-koordinatakh/007-4.-Rasstojanie-mezhdu-dvumja-tochkami.html
Не получается написать красивую функцию или однострочник, чтобы в итоге получился список из расстояний между точками. Т.е [‘расстояние между (0,1) и (2,4)’, ‘расстояние между (2,4) и (5,1)’ и т.д ]
задан 2 июл 2022 в 15:21
1
math.hypot вычисляет расстояния, zip формирует пары. Можно превратить в однострочник:
import math
def dist(p1, p2):
return math.hypot(p2[0] - p1[0], p2[1] - p1[1])
def dists(points):
return [dist(p1, p2) for p1, p2 in zip(points[:-1], points[1:])]
print(dists([(0, 1), (2, 4), (5, 1), (5, 5), (7, 2)]))
ответ дан 2 июл 2022 в 16:46
0
Можете попробовать вот так:
def distance(point_1, point_2):
return ((point_2[0] - point_1[0]) ** 2 + (point_2[1] - point_1[1]) ** 2) ** 0.5
list_point = [(0, 1), (2, 4), (5, 1), (5, 5), (7, 2)]
def get_list_distance(list_point):
return [distance(item, list_point[index])
for index, item in enumerate(list_point, start=-len(list_point) + 1)]
distance_list = get_list_distance(list_point)
print(distance_list)
Вывод
[3.605551275463989, 4.242640687119285, 4.0, 3.605551275463989, 7.0710678118654755]
ответ дан 2 июл 2022 в 15:51
Bol4onokBol4onok
7231 серебряный знак10 бронзовых знаков
2
Мне кажется, что если речь идет о расстоянии только между соседними точками, то все намного проще:
arr=[(0, 1), (2, 4), (5, 1), (5, 5), (7, 2)]
lst=[(((arr[i][0]-arr[i+1][0])**2+(arr[i][1]-arr[i+1][1])**2)**0.5) for i in range(len(arr)-1) ]
print(lst)
Результат:
[3.605551275463989, 4.242640687119285, 4.0, 3.605551275463989]
В точном соответствии с заданием: и результат — список, и решение — однострочник.
ответ дан 2 июл 2022 в 17:10
passantpassant
11.5k2 золотых знака9 серебряных знаков16 бронзовых знаков
|
0 / 0 / 0 Регистрация: 12.03.2021 Сообщений: 1 |
|
|
1 |
|
Как найти максимальное расстояние между точками списка?12.03.2021, 19:23. Показов 4084. Ответов 6
Например, a = [(1, 0), (0, 1), (-1, 0), (3, 4), (-1,0), (0,-1)]
0 |
|
Programming Эксперт 94731 / 64177 / 26122 Регистрация: 12.04.2006 Сообщений: 116,782 |
12.03.2021, 19:23 |
|
Ответы с готовыми решениями: Найти расстояние между точками с координатами Найти минимальное расстояние между точками этих множеств и сами точки Найти максимальное расстояние между точками
6 |
Найти максимальное расстояние между точками на плоскости|
u235 4383 / 2492 / 526 Регистрация: 07.11.2019 Сообщений: 4,138 |
||||
|
12.03.2021, 20:09 |
2 |
|||
|
РешениеНе оптимально считает, но можно так:
0 |
|
Arsegg 3484 / 2092 / 560 Регистрация: 02.09.2015 Сообщений: 5,336 |
||||
|
12.03.2021, 22:10 |
3 |
|||
1 |
|
Status 418
3856 / 2136 / 571 Регистрация: 26.11.2017 Сообщений: 5,004 Записей в блоге: 2 |
|
|
12.03.2021, 22:23 |
4 |
|
через стек будет O(n*log(n))
1 |
|
3484 / 2092 / 560 Регистрация: 02.09.2015 Сообщений: 5,336 |
|
|
12.03.2021, 22:42 |
5 |
|
2 |
|
496 / 276 / 72 Регистрация: 10.04.2012 Сообщений: 1,081 Записей в блоге: 2 |
|
|
13.03.2021, 11:04 |
6 |
|
eaa, можно посмотреть код Вашего решения? Очень интересно!
0 |
|
Status 418
3856 / 2136 / 571 Регистрация: 26.11.2017 Сообщений: 5,004 Записей в блоге: 2 |
|
|
13.03.2021, 11:08 |
7 |
|
VistaSV30, выше же скинули ссылку на решение.
0 |
|
IT_Exp Эксперт 87844 / 49110 / 22898 Регистрация: 17.06.2006 Сообщений: 92,604 |
13.03.2021, 11:08 |
|
7 |
Координатный квест: как найти координаты и расстояния без регистраций и смс
Уровень сложности
Средний
Время на прочтение
11 мин
Количество просмотров 1.4K
Привет, Хабр!
С вами участник профессионального сообщества NTA Алексей Майка.
Хочу поделиться своим опытом решения одной интересной задачки и описать весь проделанный путь.
Был обычный денёк, сидел я на работе и занимался своими айтишными делами. Ко мне пришел руководитель и сказал: «Нужно рассчитать дистанцию до границы регионов для этих адресов». При этом без всяких платных сервисов и API онлайн карт, и своими усилиями. Айтишник понял, айтишник принял, айтишник получил свою заветную эксельку и пошёл работать.
План работы
-
Вступление
-
Начало начал
-
Кто? А главное, зачем?
-
Дёшево и сердито
-
Финишная прямая
-
Оценка качества
-
Итог
Вступление
Из школьных уроков географии я помнил, что для определения километража требуется знать координаты (широту и долготу) двух точек. И исходя из этого, я разделил задачу на 4 части:
-
поиск координат границы;
-
предобработка данных;
-
поиск координат адресов;
-
непосредственный расчёт расстояний между координатами.
В посте продемонстрировал весь путь решения данной задачи, небольшие нюансы, проверку результатов и непосредственно код. И, познакомив читателя с моей маленькой предысторией, расскажу об инструментах, которыми я пользовался.
В качестве основного инструмента для парсинга, обработки и расчётов я использовал Python. Средой разработки выступали Jupyter Notebook (Anaconda), PyCharm и DataSpell от компании JetBrains (дело вкуса). При работе с данным проектом использовал библиотеки Numpy, Pandas, Plotly, Geopy, Selenium.
На этом прелюдия заканчивается, переходим к сути.
Начало начал
Для расчёта дистанции до границы нужны координаты, что неудивительно, самой границы. Вручную прокликивать точки на карте мне не очень хотелось, а попытка поиска готовых координат полностью провалилась. К счастью, удалось найти json‑файл с положением границ субъектов России, среди которых и находятся нужные точки.
Для начала достаю нужные области. Импортирую библиотеки для дальнейшей работы, сохраняю данные файла в словарь (dict) и смотрю на содержимое объекта:
#Библиотека для работы с ".json"-файлами
import json
#Библиотека для обработки и анализа данных
import pandas as pd
#Библиотека для работы с многомерными массивами
import numpy as np
# Считываем файл с координатами всех регионов
with open('data//gadm41_RUS_1.json', encoding = 'utf-8') as js:
dict_coordin_border = json.load(js)
Видно, что json хорошо структурирован, и с ним достаточно легко работать. Названия регионов и координаты можно найти по следующим ключам:
-
dict_coordin_border[‘features’] [‘properties’][‘NL_NAME_1’] — название субъекта федерации;
-
dict_coordin_border[‘features’] [‘geometry’][‘coordinates’] — координаты границ субъектов.
Выделяю из данного словаря только нужные пять областей, и записываю в pandas.DataFrame данные, где:
-
region — название региона;
-
lon — долгота точки границы;
-
lat — широта точки границы;
-
sequence_number — порядковый номер записи;
-
color — цвет региона.
Зачем цвет и порядковый номер? Расскажу далее, а сейчас предлагаю рассмотреть код:
Посмотреть код
df_coord_reg = pd.DataFrame()
sequence_number = 0
for regions in dict_coordin_border['features']:
#Ставим условия для поля названия субъектов
if regions['properties']['NL_NAME_1'] in ['Воронежскаяобласть',
'Брянскаяобласть',
'Курскаяобласть',
'Ростовскаяобласть',
'Белгородскаяобласть']:
for list_coordin_lv_1 in regions['geometry']['coordinates']:
for list_coordin_lv_2 in list_coordin_lv_1:
for list_coordin_finish_lvl in list_coordin_lv_2:
#Заполняем df: Название региона, координаты точки границы, порядковый номер записи, цвет региона
if regions['properties']['NL_NAME_1'] == 'Воронежскаяобласть': color = 'purple'
elif regions['properties']['NL_NAME_1'] == 'Брянскаяобласть': color = 'white'
elif regions['properties']['NL_NAME_1'] == 'Курскаяобласть': color = 'blue'
elif regions['properties']['NL_NAME_1'] == 'Ростовскаяобласть': color = 'yellow'
elif regions['properties']['NL_NAME_1'] == 'Белгородскаяобласть': color = 'red'
df_coord_reg = df_coord_reg.append({'region': regions['properties']['NL_NAME_1'], #Название региона
'lon': list_coordin_finish_lvl[0], #Долгота точки границы
'lat': list_coordin_finish_lvl[1], #Широта точки границы
'sequence_number': str(sequence_number), #Порядковый номер записи
'color': color}, #Цвет региона
ignore_index = True)
sequence_number += 1В итоге получается следующий dataframe:
На данном этапе я получил координаты границ регионов со всех сторон. Но это не совсем нужный результат, требуется только та часть границ, которые не совпадают друг с другом. И здесь я хочу рассказать про библиотеку plotly.
О plotly
Plotly — это графическая библиотека для интерактивной визуализации данных. С её помощью можно создавать диаграммы, гистограммы, карты распределения, 2D‑диаграммы, 3D‑графики и многое другое. Эта библиотека — сильный «зверь» для визуала, и она поможет расположить полученные точки на карте. Подробнее ознакомиться можно по ссылке.
Код ниже отображает точки на географической карте Европы:
Код
#Импортируем библиотеки для визуализации данных
import plotly.graph_objs as go
#Визуализируем на карте точки с координатами для проверки и дальнейшего анализа
fig = go.Figure(data=go.Scattergeo( #Scattergeo - данные, визуализируемые в виде точек географической карте
lon = df_coord_reg['lon'], #Долгота точки
lat = df_coord_reg['lat'], #Широта точки
mode = 'markers', #Вид точки
marker_color = df_coord_reg['color'], #Цвет точки
text = df_coord_reg['region'] + ' ' + df_coord_reg['sequence_number'] #Текст при наведении на точку
),
)
fig.update_layout(
title = 'Субъекты РФ ', #Задаем название карты
geo = dict(
scope='europe', #Шаблон карты
landcolor = "green", #Цвет для стран
countrycolor = "black", #Цвет границ между странами
),
width=1500, #Ширина карты
height=750 #Высота графика
)Результат выполнения кода:
Как видно на рисунке, все точки находятся на своих местах. Осталось из них выбрать только точки, не являющиеся общими для регионов. Для этого я и задавал цвет областей и их порядковый номер.
Выбираю номера точек, которые находятся на границе, и перезаписываю данные в dataframe:
#Исходя из карты, выбираем следующие срезы df и записываем их в новую переменную
df_coord_border = pd.concat([df_coord_reg[11:411],
df_coord_reg[1278:1459],
df_coord_reg[974:1226],
df_coord_reg[3084:3157],
df_coord_reg[2004:2413]])Для проверки повторно визуализирую данные и сохраняю полученные координаты в json‑файл.
Код
#Визуально проверяем полученный dataframe
fig = go.Figure(data=go.Scattergeo(lon = df_coord_border['lon'],
lat = df_coord_border['lat'],
mode = 'markers',
marker_color = df_coord_border['color'],
text = df_coord_border['region'] + ' ' + df_coord_border['sequence_number']))
fig.update_layout(
title = 'Субъекты РФ',
geo = dict(
scope='europe',
landcolor = "green",
countrycolor = "black",
),
width=1500, #Ширина карты
height=750 #Высота графика
)
#Сохраняем данные в json
df_coord_border[['lon', 'lat']].to_json('data//border.json')Результат работы кода:
Кто? А главное, зачем?
Помните об эксельке, которую я упоминал в начале? Вот теперь пришло и её время. Создаю новую тетрадку, импортирую библиотеки, читаю xlsx‑файл. Смотрю на данные.
import pandas as pd
import numpy as np
import json
#Возьмем данные из входного файла
df_start_adress = pd.read_excel('data//starting_address.xlsx')
border_coord_df.head()
Что же получается? В файле хранятся 6 228 адресов, и, даже взглянув на эту выборку, закрадывается подозрение, что данные не имеют строгого формата. Необходимо удалить из dataframe дубликаты и проверить данные на пропуски:
#Удалим дубликаты
df_start_adress = df_start_adress.drop_duplicates()
df_start_adress
#None отсутствуют
df_start_adress.info()
#NaN,None и пустота могут быть в виде строки. Проверяем по длине строки
df_start_adress[df_start_adress['полный адрес'].str.len() <= 5]
К счастью, пропусков не наблюдается, а после удаления дубликатов dataframe сократился на 2 000 строк.
Проанализировав можно выделить несколько проблем:
-
Нет строгой типизации формата адресов. Это сильно ограничивает библиотеки и технологии, такие как запросы HTTP и бесплатные API сайтов.
-
В адресах присутствует подстрока «Адрес из Росреестра:». При проверке таких адресов в «Яндекс.Картах», выдается адрес отдела Росреестра города исходного адреса или пустой результат поиска:
-
Дублируются данные внутри ячеек. При проверке в онлайн картах данные не выдаются, или строится маршрут движения по этим адресам, точнее, путь от себя к себе:
-
Присутствуют лишние данные, которые мешают поиску.
Обработать полученные данные и привести их к одному виду показалось очень трудозатратной задачей. Проверив несколько адресов, я решил использовать сервис «Яндекс Карты». Он показал, что может работать с различными адресами и выдавать корректный результат.
Но обработать адреса все равно необходимо и избавиться хотя бы от некоторых проблем: подстрока с Росреестром и повторяющиеся данные.
Для этого применяю функцию formating_text. В функции создаю список, разбиваю строку на слова и помещаю их в список поочередно. Если данное слово уже существует в списке, то его в список не добавляю. В конце удаляю из итоговой строки «Росреестр»:
def formating_text(text):
old_text = text.split()
new_text = []
for word in old_text:
if word not in new_text:
new_text.append(word)
return ' '.join(new_text).replace('Адрес из Росреестра: ', '')
df_start_adress['formating_adress'] = df_start_adress['полный адрес'].apply(lambda x: formating_text(x))
Сохраняю полученный результат и перехожу к следующему этапу.
Дёшево и сердито
Самые внимательные читатели могли заметить, что для данного проекта я использовал библиотеку Selenium. Почему именно она? Она обладает преимуществами на фоне остальных библиотек и методов парсинга. Её ближайшие аналоги:
-
API «Яндекс.Карт». Данная система хоть и очень удобна в использовании для этой задачи, но она не бесплатна. А мы договаривались в начале публикации, никаких дополнительных вложений.
Тарифы Яндекса
-
Http/Https‑запросы. В отличие от системы, описанной выше, для запроса требуется только возможность подключения к нужному сайту. Но с моими данными написание get/ post-запросов — довольно сложная задача. К примеру, запрос https://yandex.ru/maps/213/moscow/house/mokhovaya_ulitsa_11s1 состоит из названий города, улицы и номера дома на транслите. Преобразовать входящие данные в такой формат будет непосильной задачей для меня.
Методом исключения осталась только библиотека Selenium, которая будет симулировать действие человека в браузере на сайте. Это позволит обойти системы защиты Яндекса, воспользоваться их алгоритмами обработки данных и найти координаты объекта.
Сразу скажу, здесь я не буду обучать вас данной библиотеке. Лишь разберу основной алгоритм работы скрипта, покажу некоторые нюансы и возможные методы их решения.
Подключение драйвера. В данном проекте я использовал браузер Google Chrome, и примеры будут для Google. Библиотека Selenium уже имеет в себе драйвер для работы с Google, и для его подключения просто нужно прописать команду webdriver.Chrome(). Для перехода на сайт используйте функцию get.
from selenium import webdriver
#Адрес сайта "Яндекс.Карты"
url_adress = 'https://yandex.ru/maps'
#Подключение драйвера Google
driver = webdriver.Chrome('chromedriver.exe')
#Переход на сайт
driver.get(url_adress)
time.sleep(5)Поиск адреса. Адрес вписывается в поле формы поиска, код данного элемента «<input class=”input__control_bold” >». Для поиска элемента использовал комбинацию функций WebDriverWait и ExpectedCondition. Selenium будет производить поиск элемента, пока он не будет найден или не кончится время ожидания.
Далее заполняю найденную форму адресом с помощью функции send_keys и запускаю поиск, имитируя нажатие клавиши Enter функцией send_keys(Keys.ENTER).
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.support import expected_conditions as EC
# Время ожидания
delay = 10
# Поиск формы ввода на сайте
elem_search_string = WebDriverWait(driver, delay)
.until(EC.presence_of_element_located(
(By.XPATH, "//input[@class='input__control _bold']")))
# Вписываем данные в форму
elem_search_string.send_keys(adress)
# Запускаем поиск
elem_search_string.send_keys(Keys.ENTER)Результат поиска. Если все отработало штатно, Яндекс должен выдать географические координаты адреса. С помощью уже знакомой комбинации WebDriverWait и ExpectedCondition записываю координаты в переменную:
# Поиск координат на сайте
elem_search_2 = WebDriverWait(driver, delay)
.until(EC.presence_of_element_located(
(By.XPATH, "//div[@class='toponym-card-title-view__coords-badge']")))
# Запись в переменную координат адреса
coord = elem_search_2.textНо Яндекс — не всемогущ, он не всегда находит однозначный ответ, поэтому на некоторые адреса он предлагает несколько вариантов. Как, например, здесь:
На случай таких ситуаций я брал первый предложенный вариант. Скорее всего он и будет являться нужным мне адресом:
elem_first_list = WebDriverWait(driver, delay)
.until(EC.presence_of_element_located(
(By.XPATH, "//div[@class='search-snippet-view__body _type_toponym']")))
elem_first_list.click()И напоследок очищаю форму записи:
try:
elem_clear = WebDriverWait(driver, 2)
.until(EC.presence_of_element_located(
(By.XPATH, "//a[@class='small-search-form-view__pin']")))
except:
elem_clear = WebDriverWait(driver, 2)
.until(EC.presence_of_element_located(
(By.XPATH, "//div[@class='small-search-form-view__icon _type_close']")))Рекомендую объединить поиск координат на сайте и очистку формы записи на случай, если сервис не найдет никакого результата. Это позволит продолжить работу скрипта и не перезапускать программу.
Повторяю все вышеперечисленные действия ещё 3 000 раз и сохраняю
результат в файл.
Финишная прямая
Осталось дело за малым: рассчитать дистанцию между координатами адресов и кратчайших точек построенной границы. С этим поможет библиотека Geopy.
О Geopy
Geopy — это сторонняя библиотека Python для определения географического местоположения. Она позволяет разработчикам Python легко находить координаты адресов, городов, стран и достопримечательностей по всему миру, используя сторонние геокодеры и другие источники данных. Ознакомиться с библиотекой можно по ссылке.
Для начала импортирую библиотеки и данные с файлов, которые получил ранее, координаты границы и адреса. Преобразую их в нужный формат для удобства в работе.
#Импортируем библиотеки
import pandas as pd
from geopy.distance import geodesic as GD
import json
from tqdm import tqdm
#Ипортируем данные с координатами
with open("data/adress_coord.json", 'r', encoding='utf-8-sig') as ad_cor:
adress_coord_dict = json.load(ad_cor)
border_coord_df = pd.read_json("data//border.json")
#Для удобства словарь с координатами адресов преобразуем в df
atress_coord_df = pd.DataFrame(adress_coord_dict.items(), columns=['adress', 'coord'])
# Преобразуем координаты границы в список
list_border_coord = list([(row['lat'], row['lon']) for index, row in border_coord_df.iterrows()])Из библиотеки Geopy меня интересует только одна функция, которая как раз и рассчитает расстояние между двумя координатами — geodesic. Показываю, как она работает на примере:
Как видно из примера, в функцию нужно подавать широту и долготу в виде списка, множества, строки или кортежа. Главное, чтобы данные подавались попарно. В конце можно добавить единицу измерения расстояния: километры (km, kilometers), метры (m, meters), мили (mi, miles) и т. д.
Теперь пишу функцию, которая и будет считать минимальное расстояние между точками границы и адресом:
def distance_calculation(start_coord):
list_dist = []
for bord_coord in list_border_coord:
#Для расчета расстояния используем функцию GD([1 координаты точки],[2 координаты точки].[единица измерения расстояния])
dist = GD(start_coord, bord_coord).km
#Добовляем в список результат
list_dist.append(dist)
#Возвращаем минимальную дистанцию из списке
return min(list_dist)
tqdm.pandas()
atress_coord_df['dist_to_bor'] = atress_coord_df['coord'].progress_apply(lambda x: distance_calculation(x))Результат:
Оценка качества
Для сдачи итоговых результатов нужно их проверить, ведь плохой результат никто не любит. Открываю Google Maps и адреса из первоначальной эксельки, расстояние до границы и линейку. И, как видно из рисунков, результаты корректны, а погрешность — в допустимых нормах.
Итог
Что я могу сказать по итогу? Задача необычная, интересная и в меру сложная. Попрактиковался с библиотеками Pandas, Selenium, Plotly и посмотрел на новую библиотеку Geopy. Результат работы корректен, а погрешность — в допустимых рамках. Санные пошли дальше в работу.
В общем, задача мне понравилась. Я получил дополнительный опыт и даже некие новые знания, и на этом я заканчиваю пост. Желаю всем удачи!)
P. S. Кстати, чуть не забыл, с кодом вы можете ознакомиться на Github.
Проблема и цель проекта
Предприятие осуществляет доставку товаров по городу. Для контроля эксплуатации служебного автомобиля необходимо владеть информацией о том, какую дистанцию должна была проехать машина при доставке по указанным адресам.
Подбор инструментов
Преимущества свободных данных и софта
Для реализации проекта предлагается использовать данные и программное обеспечение, которые распространяются под свободными лицензиями. Преимущества такого подхода перед использованием картографических сервисов от Google или Яндекса следующие:
- Проект подразумевает обработку данных для внутренних целей, а лицензионные договоры Google и Яндекса требуют использования их сервисов только для создания общедоступных публикаций в виде карт. Т.е. использование услуг этих компаний в нужных нам целях будет незаконным. Конечно, вероятность того, что Яндекс обратит внимание на незначительную нагрузку, которую мы генерируем, очень мала. Но с точки зрения развития бизнеса или его продажи в будущем, лучше сразу отказаться от включения в работу предприятия заведомо нелегальных алгоритмов.
- В процессе работы будут постепенно «всплывать» ошибки в используемой базе данных: например, какие-то адреса будут неправильно преобразовываться в координаты. Если мы работаем на основе картографического сервиса Яндекса, то в случае обнаружения ошибок (в нашем опыте такие ошибки у Яндекса были), каждый ошибочный адрес придётся обрабатывать как исключение, поскольку сам Яндекс по нашему запросу исправит эти ошибки только через несколько месяцев. При использовании данных из базы OpenStreetMap, мы можем сами внести исправление в базу, и оно практически сразу станет доступно для нашего приложения.
- При необходимости внести какие-либо изменения в работу алгоритмов по геокодированию или прикладке маршрутов, мы можем отказаться от использования открытого API, а запустить эти сервисы на своём оборудовании, поскольку и база данных дорожной сети, и программное обеспечение доступны на условиях свободных лицензий.
Схема работы
Алгоритм вычисления расстояния между двумя адресами состоит из двух этапов:
- Геокодирование, т.е. преобразование текстовой строки, содержащей адрес, в географические координаты.
- Прокладка маршрута и вычисление его длины.
Геокодирование российских адресов
Международный сайт OpenStreetMap.org для геокодирования использует программу Nominatim. У нас есть опыт работы с API Nominatim через статистический пакет R. Исходные коды R-скриптов доступны в репозитории на github.
Для национального проекта OpenStreetMap.ru разработано собственное приложение для поиска адресов и точек интереса. Приложение «заточено» под специфику адресов в России, »понимает« нумерацию домов в духе »14 К2 С1« и может искать дома с двойным адресом. У поисковика доступно API, документация опубликована в форуме. Например, для определения координат дома по адресу «Псков, Маркса, 23» следует отправить запрос вида http://openstreetmap.ru/api/search?q=Псков, Маркса, 23. Ответ вернётся в формате JSON, координаты хранятся в полях lat и lon.
Для снижения количества ошибок геокодирования и уменьшения объёма лишней информации в ответе в строку запроса рекомендуется добавить параметры точки начала поиска (координаты центра города; аргументы запроса lat и lon), поиск только по адресам (stype=addr), количество ответов установить равным 1 (cnt=1).
Прокладка маршрута
Корифей OpenStreetMap и ведущий новостного блога ШТОСМ Илья Зверев порекомендовал использовать для маршрутизации Open Source Routing Machine. У разработчиков запущен демо-сервер с доступным API (Илья просил не более 20 запросов в минуту, также существует ряд требований).
Предположим, мы хотим узнать длину маршрута между адресами Маркса, 23 и Рижский, 69 в городе Пскове. Через API OpenStreetMap.ru мы узнаём координаты:
- Маркса, 23
- 57.818023681640625, 28.342592239379883
- Рижский, 69
- 57.812679290771484, 28.28318214416504
Полученные координаты мы отправляем на API Open Source Routing Machine в виде запроса http://router.project-osrm.org/viaroute?loc=57.818023681640625,28.342592239379883&loc=57.812679290771484,28.28318214416504. Ответ приходит в формате JSON, в поле total_time содержится предполагаемое время на дорогу (в нашем случае 467 секунд), в поле total_distance — длина маршрута (4582 метра).
OSRM позволяет прокладывать маршрут сразу между последовательностью точек, но не более 25.
Подготовлено для кафе «Моя Италия»