Ближайшая дорога с учетом широты и долготы

У меня есть база данных, которая содержит все путевые точки для каждой дороги в Великобритании.

Я пытаюсь создать навигационное приложение, учитывая широту и долготу пользователей, оно рассчитает ближайшую дорогу из базы данных и отобразит имя

Фрагмент JSON-представления базы данных

[
{
    "NAME": "Trinity Road",
    "coordinates": [
        [
            1.7595267,
            52.4778475
        ],
        [
            1.7587864,
            52.4774
        ]
    ]
},
{
    "NAME": "Wilde Street",
    "coordinates": [
        [
            1.7593497,
            52.4795499
        ],
        [
            1.7594677,
            52.4795041
        ],
        [
            1.7598164,
            52.4793277
        ]
    ]
}
]

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

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

Может кто подскажет подходящий алгоритм?

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

Я хотел бы решить эту проблему без использования веб-API, такого как google-maps, или PostGIS (необходимо использовать sqlite - мобильное приложение)


algorithm geo math
person Ryan    schedule 13.09.2013    source источник
comment
Основана ли эта база данных на OpenstreetMap, Ordnance Survey, TomTom или Nokia Maps?   -  person AlexWien    schedule 24.07.2014
comment
это бесплатно сейчас или в рамках контракта с ОС, кстати, посмотрите на мой ответ   -  person AlexWien    schedule 25.07.2014

Ответы (2)


arrow_upward
3
arrow_downward

Вы можете использовать r-дерево или дерево квадрантов, чтобы ограничить пространство поиска, а затем диаграмму Вороного, чтобы найти ближайшую дорогу. Затем вы можете использовать 2 или более точек дороги, чтобы заполнить диаграмму Вороного, а затем найти на диаграмме ячейку Вороного, содержащую местоположение. Возможно, вы можете попробовать взвешенную диаграмму Вороного. Вы можете скачать мою взвешенную диаграмму Вороного с добавлением класса php @ https://awvd.codeplex.com/.

person Gigamegs    schedule 13.09.2013

arrow_upward
0
arrow_downward

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

Вам не нужна (сложная) диаграмма Вороного.

Результатом поиска в дереве квадов будет список линий, перекрывающих узел квадрацикла.

Теперь используйте DistanceToLineSegment(Point, point0, point1); (поищите в интернете это имя)

взять кратчайшее расстояние.

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

person AlexWien    schedule 25.07.2014