Пространственный поиск с ravenDB

Question

У меня довольно специфический пространственный поиск, который мне нужно сделать. По сути, есть объект (давайте назовем его obj1) с двумя местоположениями, назовем их точкой A и точкой B.

Затем у меня есть коллекция объектов (давайте назовем каждый объект obj2), каждый из которых имеет свои собственные местоположения A и B.

Я хочу вернуть 10 лучших объектов из коллекции, отсортированной по:

(расстояние от obj1 A до obj2A) + (расстояние от obj1B до obj2B)

Есть идеи? Спасибо, Ник

Обновление: Вот немного подробнее о документах и ​​о том, как я хочу их сравнить.

Модель домена:

Листинг: ListingId int Строка заголовка Цена двойная Место происхождения Место назначения

Расположение: Почтовый индекс Десятичная широта Долгота десятичная

То, что я хочу сделать, это взять объект списка (не в базе данных) и сравнить его с коллекцией списков в базе данных. Я хочу, чтобы запрос возвратил верхнее 12 (или x) количество списков, отсортированных по расстоянию вороны от источника плюс расстояние воронки от места назначения.

Меня не волнует расстояние от пункта отправления до пункта назначения - только расстояние от пункта отправления до пункта назначения плюс пункт назначения до пункта назначения.

По сути, я пытаюсь найти списки, где начальная и конечная локации близки.

Пожалуйста, дайте мне знать, если я могу уточнить больше. Спасибо!

Answer 1

Похоже, вы создаете сайт Ridehare. :)

Суть в том, что для сортировки результата запроса по расстоянию на поверхности вам потребуется пространственная индексация, встроенная в ядро ​​базы данных. Я думаю, что ваши варианты здесь MySQL с расширениями OpenGIS (уже упоминалось) или PostgreSQL с PostGIS . Похоже, это возможно и в ravenDB: http://ravendb.net/documentation/indexes/sptial

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

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

Давайте еще раз упростим и представим, что нам небезразлично Чебышевское (максимальное) расстояние . Это будет работать для сужения нашей области видимости в БД, прежде чем мы получим более точную информацию. Мы можем сделать «бинарный поиск» для близлежащих записей. Мы должны определить приблизительное количество ближайших записей для возврата; скажем 10 . Затем мы запрашиваем внутри квадратной области, скажем, 1 градус широты на 1 градус долготы (это около 60x60 миль) вокруг интересующего места. Скажем, наше местоположение интереса - широта, lng = 43,5,86,5. Тогда наш запрос БД - ВЫБЕРИТЕ СЧЕТЧИК (*) ОТ МЕСТА, ГДЕ (ШТ> 43 И ШТ <44) И (ЛГ> 86 И ЛГ <87) Если у вас есть индексы в полях lat / lng, это должен быть быстрый запрос. </p>

Наша цель - получить чуть более 10 суммарных результатов внутри коробки. Здесь начинается «бинарный поиск». Если мы получили только 5 результатов, мы удваиваем область окна и снова ищем. Если мы получили 100 результатов, мы разрезаем площадь пополам и снова ищем. Если сразу после этого мы получим 3 результата, мы увеличим площадь бокса на 50% (вместо 100%) и попробуем снова, продолжая, пока не подойдем достаточно близко к нашей цели 10 результатов.

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

Удачи!

Answer 2

Вот как можно решить такую ​​проблему в

mysql 4.1 &

mysql 5 .

Ссылка из MySQL 4.1 кажется весьма полезной, особенно.В первом примере речь идет в основном о том, о чем вы спрашиваете.

Но если это не совсем полезно, я думаю, вам придется зацикливаться и выполнять запросы либо к obj1, либо к obj2 относительно его таблицы-аналога.

Answer 3

С алгоритмической точки зрения, я бы нашел центр ограничительной рамки, а затем выбрал кандидатов с увеличивающимся радиусом, в то время как я нашел достаточно.

Также я просто хочу напомнить, что расстояние вороньего шара над земным шаром не является расстоянием Пифагора, и необходимо использовать другую формулу:

public static double GetDistance(double lat1, double lng1, double lat2, double lng2)
{
    double deltaLat = DegreesToRadians(lat2 - lat1);
    double deltaLong = DegreesToRadians(lng2 - lng1);

    double a = Math.Pow(Math.Sin(deltaLat / 2), 2) +
        Math.Cos(DegreesToRadians(lat1))
        * Math.Cos(DegreesToRadians(lat2))
        * Math.Pow(Math.Sin(deltaLong / 2), 2);

    return earthMeanRadiusMiles * (2 * Math.Atan2(Math.Sqrt(a), Math.Sqrt(1 - a)));
}

Answer 4

Я не думаю, что вы найдете решение прямо из коробки.

Будет гораздо эффективнее, если вы будете использовать ограничивающую сферу вместо ограничивающего прямоугольника для указания вашего объекта. http://en.wikipedia.org/wiki/Bounding_sphere

     C = ( A + B)/2 and R = distance(A,B) /2

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

В обоих случаях, я думаю, что вы должны кодировать координату C как путь в октодереве, если вы используете 3D или квадри, если вы используете 2D. http://en.wikipedia.org/wiki/Quadtree

Это первый черновик, я могу добавить больше информации, если этого недостаточно. Если вы не знакомы с 3D, начните с 2D, проще начать.

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

Я думаю, что если вы измените систему координат «конечной точки» на полярную координату относительно «начальной точки». Если вы округлите радиальную координату до своего допуска (х миль) и упорядочите их по этому значению.