Способы рассчитать расстояния до дороги в городе очень быстро

Question

Итак, у меня есть набор точек в городе (например, дома или резиденции), и я хочу найти кратчайшее расстояние между этими точками и набор точек-кандидатов для магазина. Я ищу лучшие магазины, которые минимизируют расстояние до всех домов в комплекте. Поэтому я буду итеративно перемещать точки хранилища кандидатов, а затем пересчитывать расстояния между каждым магазином и домом (опять же используя алгоритм Джикстры). Из-за огромного объема вычислений я не могу продолжать использовать базу данных для каждой итерации алгоритма оптимизации.

Я использовал pgrouting много раз, и это сработает, однако это будет слишком медленно из-за большого количества точек и того факта, что он должен каждый раз искать диск.

Есть ли инструмент, в котором я загружаю небольшую карту Карты уличной карты Open Street в память, а затем вычисляю кратчайшие маршруты в памяти? Мне нужно что-то быстрое, поэтому желательно на C или python? Но любой язык в порядке, пока он работает.

Answer 1

В python вы можете использовать networkx для работы графика. Он имеет функции поиска в первом порядке.

https://networkx.github.io/

Answer 2

Heres и идея. Получить latlongs дома и всех магазинов. Считайте geohash всех точек (дом и магазины) с максимальной точностью (12) и проверьте, соответствует ли geohash любых магазинов тем, что в доме. Если это не так, вычислите geohash с более низкой точностью (11), а затем промойте и повторите, пока вы не получите магазин (может быть несколько случаев, когда я попаду в это позже), что соответствует геохашированию дома.

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

1. Цикл geohash с понижательной точностью. Перерыв, когда geohash магазина (-ов) совпадают с gohash дома
2. IF (более одного болячки) Перейти на простой расчет расстояния и найти ближайший магазин и вернуть его
3. ELSE возвращает один магазин, который соответствует geohash

Преимущество этого метода: Измените свои строгие требования на проблему с нечеткой вероятностью. Если у вас появляется одна боль, отлично. Если вы, по крайней мере, не сокращаете количество кандидатов для расчета расстояния

Недостаток этого метода: что, если все магазины земли в одном и том же геохаше? Здесь мы вводим такую ​​же сложность.

Вы будете надеяться на то, что не все (или большинство) магазины попадают под один и тот же geohash. Реально говоря, недостатком является лишь недостаток в угловых случаях. Таким образом, в целом вы должны улучшить производительность Soo.