Самый эффективный способ сохранить путевые точки и сделать сравнения?

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

В настоящее время я использую сервер MSSQL, используя две таблицы: одну для маршрутов, а другую для хранения точек пути (с пространственным типом данных). Сравнение выполняется в хранимой процедуре с использованием географических функций SQL Server, таких как st_distance...

Я изучил другие варианты. Один из которых я реализовал с использованием Oracle 11g с использованием объектов. Я сохраняю все данные только в одной таблице объектов, а точки точек хранятся в Varray типа с атрибутами широты и долготы. Этот способ очень эффективен при сохранении и извлечении данных, но при сравнении он усложняется.

Я ищу решение NoSQL, некоторый алгоритм или метод, чтобы сделать это эффективно. Как вы думаете?

Ответы

Ответ 1

Использование функций базы данных, таких как STDistance для всех n записей является субоптимальным. Накладные расходы процессора будут экспоненциально увеличиваться.

Что вам нужно сделать, так это проверить количество точек внутри прямоугольника вокруг текущего эпицентра, который вы ищете. Вот пример (в MySQL):

SELECT * FROM `points`
    WHERE `latitude` >= X1 AND `latitude` <= X2
    AND `longitude` >= Y1 AND `longitude` <= Y2

Это обеспечивает уменьшенные superset точек, которые затем должны быть дополнительно уменьшены путем вычисления ортодромного расстояния (относительно кривизны Земли) с помощью Формула Хаверсина.

Не забудьте создать составной индекс на latitude и longitude.

Orthodromic distance

Здесь он находится в PHP:

<?php
function haversine($latitude1, $longitude1,
                   $latitude2, $longitude2, $unit = 'Mi') {
    $theta = $longitude1 - $longitude2;
    $distance = (sin(deg2rad($latitude1)) * sin(deg2rad($latitude2))) +
    (cos(deg2rad($latitude1)) * cos(deg2rad($latitude2)) * cos(deg2rad($theta)));
    $distance = acos($distance);
    $distance = rad2deg($distance);
    $distance = $distance * 60 * 1.1515;
    switch ($unit) {
    case 'Mi':
        break;
    case 'Km':
        $distance = $distance * 1.609344;
    }
    return (round($distance, 2));
}
?>

Обновить:

Вот пример изображения, иллюстрирующий, что делать:

Example with CN Tower

Первый поиск будет включать поиск столкновений с ограничивающим полем (пример MySQL) для определения superset, исключая красные точки. Второй процесс проверки должен включать вычисление, если точки находятся в пределах соответствующего ортодромного расстояния с формулой Хаверсина (пример PHP) и принимают subset (состоящий из черных точек).