sql - 保存航路点和进行比较的最有效方法？

Question

我想知道你的意见。我创建了一个应用程序，用户在其中创建路线，我们跟踪这条路线并将所有路径点保存在数据库中。然后，该应用程序会比较用户的路径点。

目前，我使用 MSSQL 服务器，使用两个表，一个用于路线，另一个用于存储路径点(具有空间数据类型)。使用 SQL Server 地理函数(例如 st_distance...)在存储过程中进行比较。

我研究了其他选项。我实现的一个是使用对象的 Oracle 11g。我只将所有数据存储在一个对象表中，点存储在具有纬度和经度属性的类型的 Varray 中。这种方式保存和检索数据的效率很高，但在比较时会变得有些复杂。

我正在寻找一个 NoSQL 解决方案，一些算法或方法来有效地做到这一点。你怎么看？

Answer 1

使用像 STDistance 这样的数据库函数对于所有 n 条记录是次优的。您的 CPU 开销将呈指数增长。

您应该做的是检查您正在搜索的当前震中周围的矩形内的点数。这是一个示例(在 MySQL 中):

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

这提供了点的缩减超集，然后应使用 Haversine formula 计算正向距离(相对于地球曲率)进一步缩减点.

不要忘记设置composite index在 latitude 和 longitude 上。

在 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));
}
?>

回顾:

这是一个示例图片，说明要执行的操作:

第一个搜索将涉及边界框碰撞搜索(MySQL 示例)以确定 superset，不包括红点。第二个验证过程将涉及使用 Haversine 公式(PHP 示例)计算这些点是否在适当的正向距离内，并获取一个子集(由黑点组成)。