Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find N Nearest LineString From A Point Using MySQL Spatial Extensions

I'm using MySQL Spatial Extensions to store data about roads and hotels. I store the hotel data as a Point while I store the road data as LineString. The tables look like this

CREATE TABLE IF NOT EXISTS `Hotels` (
    `id` int unsigned NOT NULL AUTO_INCREMENT,
    `name` text,
    `coordinate` point NOT NULL,
    PRIMARY KEY (`id`),
    SPATIAL KEY `coordinate` (`coordinate`),
)

CREATE TABLE IF NOT EXISTS `Roads` (
    `id` int unsigned NOT NULL AUTO_INCREMENT,
    `name` text,
    `route` linestring NOT NULL,
    PRIMARY KEY (`id`),
    SPATIAL KEY `coordinate` (`route`),
)

The visualization of an instance would be like this.

http://i.stack.imgur.com/8IVVA.png

My problem is given a number N and a point P, what is the SQL query to find N nearest roads from point P? The distance is defined by the smallest perpendicular distance between a segment in the road to the point like shown above. (although in the reality, the nearest distance should be between the highway gate and a hotel, but in this case, we can enter the highway from any point :P)

If there is no single SQL statement solution for this problem, an intermediary SQL query and a post-processing are acceptable for me. But what would be an efficient SQL query and how to post-process the data?

like image 960
John Hancock Avatar asked Oct 02 '12 03:10

John Hancock


2 Answers

You can create two functions in the database:

  1. Distance : This will give you distance between two points
  2. DistanceFromLine : Here distance will be calculated from each point in line, and will give you the shortest distance.

Compare the distance between your point and lines and choose the shortest one.

Here is the Distance function


delimiter //

CREATE FUNCTION distance (latA double, lonA double, latB double, LonB double)
RETURNS double DETERMINISTIC
    BEGIN
        SET @RlatA = radians(latA);
        SET @RlonA = radians(lonA);
        SET @RlatB = radians(latB);
        SET @RlonB = radians(LonB);
        SET @deltaLat = @RlatA - @RlatB;
        SET @deltaLon = @RlonA - @RlonB;
        SET @d = SIN(@deltaLat/2) * SIN(@deltaLat/2) +
        COS(@RlatA) * COS(@RlatB) * SIN(@deltaLon/2)*SIN(@deltaLon/2);
        RETURN 2 * ASIN(SQRT(@d)) * 637101;
    END//

Here is DistanceFromLine function:


DROP function IF EXISTS `DistanceFromLine`;
delimiter //
    CREATE FUNCTION `DistanceFromLine`(
    route LINESTRING, point1 POINT
    ) RETURNS INT DETERMINISTIC
        BEGIN
        DECLARE a INT Default 0 ;
        DECLARE minDistance INT Default 0;
        DECLARE currentDistance INT Default 0;
        DECLARE currentpoint point ;
        DECLARE size INT Default 0 ;
        SET size =  NumPoints(route);
              simple_loop: LOOP
       SET a = a+1;
       SET currentpoint = PointN(route,a);
       SET currentDistance = Distance(X(point1), Y(point1),       
               X(currentpoint),Y(currentpoint));

       IF a = 1 THEN
        SET minDistance = currentDistance;
           END IF;

       IF currentDistance < minDistance THEN
        SET minDistance = currentDistance;
       END IF;
       IF a=size THEN
                 LEAVE simple_loop;
       END IF;
          END LOOP simple_loop;
     RETURN (minDistance);
 END//

like image 62
sumitarora Avatar answered Oct 31 '22 11:10

sumitarora


This was a very useful answer for me, but I'm using MySQL 5.7.18, which has more advanced or just different geo query functions. The distance function posted isn't needed anymore- use ST_Distance_Sphere. So here's an update of the same code to make DistanceFromLine compliant with modern (5.7.6+) MySQL...

DROP function IF EXISTS `DistanceFromLine`;
delimiter //
    CREATE FUNCTION `DistanceFromLine`(
    route LINESTRING, point1 POINT
    ) RETURNS INT DETERMINISTIC
        BEGIN
        DECLARE a INT Default 0 ;
        DECLARE minDistance INT Default 0;
        DECLARE currentDistance INT Default 0;
        DECLARE currentpoint point ;
        DECLARE size INT Default 0 ;
        SET size =  ST_NumPoints(route);
              simple_loop: LOOP
       SET a = a+1;
       SET currentpoint = ST_PointN(route,a);
       SET currentDistance = ST_Distance_Sphere(point1,currentpoint);

       IF a = 1 THEN
        SET minDistance = currentDistance;
           END IF;

       IF currentDistance < minDistance THEN
        SET minDistance = currentDistance;
       END IF;
       IF a=size THEN
                 LEAVE simple_loop;
       END IF;
          END LOOP simple_loop;
     RETURN (minDistance);
 END//
like image 34
Scott Kraus Avatar answered Oct 31 '22 11:10

Scott Kraus