Most efficient way to save way points and do comparisons?

Question

I would like to know your opinion. I created an application, where users create routes and we track this route and save all the way points in the database. Then, the application does comparisons of users way points.

Currently, I use a MSSQL Server, using two tables, one for Routes and the other for storing way points (with spatial data type). The comparisons are made in a stored procedure using SQL Server geographic functions such as st_distance...

I have investigated other options. One that I implemented is with Oracle 11g using objects. I store all data in only one Object Table, and the way points are stored in a Varray of a type with Latitude and Longitude attributes. This way is very efficient saving and retrieving data, but gets some complicated when comparing.

I'm looking for a NoSQL solution, some algorithm or method to do this efficiently. What do you think?

Answer 1

Using database functions like STDistance for all n records is suboptimal. Your CPU overhead will increase exponentially.

What you should do is check for the amount of points within a rectangle around the current epicenter you are searching. Here's an example (in MySQL):

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

This provides a reduced superset of points that should then be further reduced by calculating the orthodromic distance (with respect to the curvature of the Earth) using the Haversine formula.

Don't forget to set up a composite index on latitude and longitude.

Here it is in 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));
}
?>

To recap:

Here's an example image illustrating what to do:

The first search would involve a bounding box collision search (MySQL example) to determine the superset, excluding the red points. The second verification process would involve calculating if the points are within an appropriate orthodromic distance with the Haversine formula (PHP example) and taking a subset (composed of the black points).