Как построить путь из одной координаты в другую, используя промежуточные координаты из списка?
Извиняюсь за корявый заголовок, не смог придумать лучше.
Есть список координат, разбросанных по всему миру.
Нужно построить путь и точки A (некие координаты) в точку B (вторые некие координаты), но при используя промежуточные пункты из списка.
Как это реализовать на Python?
s4q, Путь должен проходить через промежуточные точки в заданном порядке или как угодно? Надо посетить все промежуточные точки, или можно пропускать их?
Это координаты в мире, т.е. путь строится по дорогам условным google maps? Или дело на плоскости, и можно проводить прямые? В тегах вы указали "графы", может быть у вас есть произвольный граф на котором надо решить задачу?
s4q, но тогда кратчайший путь - прямая из начала в конец (скорее всего не посещая ни одну точку).
Судя по обсуждению под ответами, у вас есть важное ограничение - иерархическая структура логистики почтовых отделений. Нельзя из районного отделения новосибираска отправить посылку напрямую в районное отделение в архангельске - слишком много различных путей для посылок будет. Посылка должна идти через городской пункт, через областной в новосибирске, оттуда, скорее всего, через москву в сортировочный центр в арзангельской области.
Wataru, да, но нужно найти кратчайший путь через промежуточные точки.
Судя по обсуждению под ответами, у вас есть важное ограничение - иерархическая структура логистики почтовых отделений. Нельзя из районного отделения новосибираска отправить посылку напрямую в районное отделение в архангельске - слишком много различных путей для посылок будет. Посылка должна идти через городской пункт, через областной в новосибирске, оттуда, скорее всего, через москву в сортировочный центр в арзангельской области.
Верно, у меня есть массив с сортировочными центрами, нужно по ним маршрут построить
s4q, Надо задать к этому массиву еще и список, между какими двумя центрами можно возить товары. Обычно это только между отделением и родительским ему а так же между любыми двумя отделениями верхнего уровня.
Вы должны задать эти ограничения. По координатам их вывести невозможно, ибо границы областей/поселений нарезаны весьма произвольно. Если вы их не задаете, то ответ остается такой-же: кратчайший путь будет без промежуточных точек, по прямой.
Задача выглядит как поиск кратчайшего пути в графе. Но решать в географических координатах
сложно т.к. надо учитывать кривизну планеты Земля. На эту тему есть куча формул и еще лучше,
куча систем координат и API.
Но я-бы просил автора нарисовать на картинке как это он себе видит. Возможно тут либо все очень
проще. Либо очень сложнее.
Как смог)
Желтые точки - все остальные точки из списка.
Красная и синяя точки - начало и конец пути.
Черная линия - маршрут по ближайшим точкам от т. A до т. B.
Я пытаюсь сделать построение примерного маршрута посылки от отделения до отделения - у меня есть координаты двух отделений и координаты сортировочных центров. Мне нужно получить список, через какие СЦ пройдет посылка на пути от отделения к отделению. Это если упростить :)
s4q, этих сведений мало. Почему в твоём примере нельзя сразу сделать прыжок A -> B? Какие точки считаются "соседними"? А вообще есть классический алгоритм дейкстры.
s4q, зачем?
Ну, в том смысле, какую цель в итоге хотим достичь?
Потому что можно оптимизировать три разных параметра:
стоимость
время
качество (вероятность утраты/повреждения/ошибки)
И чем-то придется пожертвовать. И для каждого варианта свои способы решения.
Самый тупой способ - получаем функцию оси - прямой, проходящей через А и Б, потом можно сделать поворот, затем для каждой из промежуточных точек опускаем перпендикуляр на ось и измеряем его.
Фильтруем точки, у которых координата x вне АБ. Сортируем оставшиеся точки по длинам перпендикуляров по asc и отбираем нужное количество.
Другой вариант - для каждой точки меряем расстояния до А и до Б, затем сортируем их по сумме этих расстояний. Те, у которых сумма ближе всего к отрезку АБ, и есть самые подходящие.
Алан Гибизов, я писал. Мне просто нужно рассчитать, через какие СЦ пройдет посылка на пути к получателю.
Однако, спасибо вам за варианты, попытаюсь реализовать второй.
p.s. рассчитать без учета ошибок на почте или перенаправлений
Я по натуре не согласен с такой постановкой. Мы не учитываем длину по дорогам. Эта длина
слабо коррелирует с координатами. Все знают что такое пробки, окружные трассы, плохие
грунтовые дороги и погодные условия.
Ну да ладно. Автор. Дай нам пример тестовых данных (хотя-бы штук 100 координат).
s4q, ну так я на то и намекаю. Пока ты не сформулируешь критерий оптимальности маршрута, ничего не попишешь.
Самый короткий маршрут всегда будет прямой A -> B.
Если брать самый "жадный" маршрут (т.е. ехать всегда в ближайшее к текущему отделение), то можно, как это ни смешно, начать выписывать вензеля по карте.
Минимальный вариант я привёл выше - если ты сможешь для каждой точки определить те, с которыми она может быть связана, то у тебя получится взвешенный граф, в котором можно искать кратчайший путь алгоритмом Дейкстры. Простейший способ это сделать - наложить ограничение на длину одного переезда.
А если у тебя задача практическая, то тут вообще убиться можно, потому что ещё есть такие вещи как пропускная способность дорог, вместимость и пропускная способность отделений, и так далее, и так далее. Т.е. если многие оптимальные маршруты ведут через одно и то же отделение, это может замедлить дело, так как отделение будет перегружено.
s4q, в действительности во втором мы получим только точки, подтянутые к оси АБ. Но там много нюансов: например, их порядок. Но это можно их отсортировать по сумме координат, а если ось ляжет неудачно, то там еще придется пошаманить.
И например могут попасться точки вне АБ, это тоже надо убирать.
Кстати, по-моему для обоих случаев вначале можно повыкидывать все, у которых координата х вне АхВх, а координата y вне AyBy.
В аттачменте приведено 95 координат. Нужно построить матрицу расстояний. Тоесть будет квадрат 95 на 95 ячеек. В каждой ячейке - расстояние.
Расстояние посчитаем сначала в градусах. По теореме Пифагора. Вот это расстояние будет метрикой
стоимости пути в алгоритме Дейкстры или в любом другом алгоритме.
Потом градусы можно перевести в километры. Для экваториальных измерений там обычно
1 градус был равен 111 километров. Для измерений ближе к полюсам там соотв надо делать поправку.
Впрочем для автора такое искривление возможно безразлично.
s4q, на практике точно рассчитать путь и сроки доставки посылки нельзя. Это зависит от тысячи причин. Хотя бы от того, что посылка не перемещается независимо от других посылок, существуют таможенные процедуры, очереди, посылка может долго лежать на складе, ожидая когда таких посылок примерно в ту же сторону накопится много и тогда будет отправлен рейс. В логистике, если ей заниматься по серьезному, есть куча ньюансов и неочевидных моментов.
Это как точно рассчитать, почему вы в магазине рассчитались на кассе №3, а не № 1, 2, 4. Видимо так сложились обстоятельства, что в данный текущий момент там была меньше очередь или кассы были закрыты на перерыв или просто случайность. Или как рассчитать путь IP пакета в сети интернет. Маршруты, в любом случае, будут менятся динамически.
Для экваториальных измерений там обычно
1 градус был равен 111 километров. Для измерений ближе к полюсам там соотв надо делать поправку.
Впрочем для автора такое искривление возможно безразлично.
для длины дуги меридиана, возможно, безразлично (насколько помню, там в пределах 10% различия), а вот длина дуги параллели меняется от 0 (прописью: от нуля!) точно на полюсе до примерно тех самых 111 км на экваторе, так что если пути не строго в направлении север -- юг, то искажение может быть от огромного в средних широтах до чудовищного ближе к полюсу.
Я это к тому, что пренебрегать искажением можно вблизи экватора, как вы и сказали, но в средних (а тем более в высоких) широтах очень сложно игнорировать поправку, потому что не просто расстояния искажаются; это бы ещё пол беды, если в близких между собой широтах расстояния остаются пропорциональными, их можно хотя бы сравнивать; другая половина беды в том, что искажаются направления, и очень сильно. Т.е. я хочу сказать, что сложно найти такую задачу, где можно невозбранно загрубить поверхность эллипсоида до плоскости и все градусы умножать на 111 км. Только к этому тезису я придираюсь, а больше ни к чему.
hint000, я согласен. Все равно ему надо карту автодорог добавлять в качестве метрик расстояния.
Даже если мы точно посчитаем... что он? По воздуху полетит?
Средний
