Determine if a POINT is between two other POINTs on a LINESTRING (SQL Server 2008 Geography)

I have a SQL Server 2008 GEOGRAPHY data type in my dat开发者_如何转开发abase containing a LINESTRING. The LINESTRING describes a potentially curvy road.

I have another table that contains a start point and end point, both GEOGRAPHY POINT's, on the road. I need to know if a third point falls between those two points on the road (LINESTRING).

Currently, I'm testing that:

• the third point is on the line
• the distance between the new point to the start point and the distance between the new point and the end point are both less than the distance between the start point and end point

This works, but it seems really inelegant doesn't work at all if the road u-turns on itself! Is there a way that works?

As you have noted, your method will fail in the following case, where S is the start point, E is the end point, and X is the point you are testing:

Determine if a POINT is between two other POINTs on a LINESTRING http://img10.imageshack.us/img10/4937/gmap.png

Using that method, point X will falsely result as being between point S and point E, because it passes both test 1 and test 2 of your algorithm: ie. Point X is on the linestring, and the distances from X to S and from X to E are both smaller than the distance from S to E.

One Possible Solution

You can "explode" your linestring path into separate line segmenets with just two points each, so that:

LINESTRING(-122.360 47.656, -122.343 47.656, -122.310 47.690, -122.310 47.670)

would get broken down into:

LINESTRING(-122.360 47.656, -122.343 47.656)
LINESTRING(-122.343 47.656, -122.310 47.690)
LINESTRING(-122.310 47.690, -122.310 47.670)

Then you would be able to iterate through each of the above line segments and test if the point lies on one of these segments using STIntersects. When a point passes this test, you would be able to determine if this was within the start point and the end point.

If possible, I would suggest storing your start/end points as an index to a point on your linestring path, instead of a raw geography point. First of all, this will make it easier to solve this problem, but apart from that, you would eliminate the duplication of data, which also comes with a guarantee where you cannot have a start/end point that is not part of a linestring. The disadvantage of this is that you will not able to have start/end points in the middle of a line segment, but they have to be on one of the corners of the path. Now you have to determine if this limitation is acceptable in your application.

If you opt for the above representation, we could solve this problem with the following recursive function, where @path is the linestring representing the road, @start_point and @end_end represent the indexes of two points on the @path (first index is 1), and @test_point is the geography point that will be tested. The test point can lie anywhere on the lie.

CREATE FUNCTION [dbo].[func_PointBetween](@path        geography, 
                                          @start_point int, 
                                          @end_point   int,
                                          @test_point  geography)   
RETURNS tinyint
AS
BEGIN
    DECLARE @result       tinyint = 0;
    DECLARE @num_points   int = @path.STNumPoints();
    DECLARE @line_segment geography;

    IF (@start_point < @end_point) AND (@end_point < @num_points)
    BEGIN
        /* Generate the line segment from the current start point
           to the following point (@start_point + 1). */

        SET @line_segment = geography::STLineFromText('LINESTRING(' + 
            CAST(@path.STPointN(@start_point).Long AS varchar(32))+ ' ' + 
            CAST(@path.STPointN(@start_point).Lat AS varchar(32)) + ',' +
            CAST(@path.STPointN(@start_point + 1).Long AS varchar(32))+ ' ' + 
            CAST(@path.STPointN(@start_point + 1).Lat AS varchar(32)) + ')', 
            4326);

        /* Add a buffer of 25m to @test_point. This is optional, but 
           recommended, otherwise it will be very difficult to get a
           point exactly on the line. The buffer value may be tweaked
           as necessary for your application. */

        IF @test_point.STBuffer(25).STIntersects(@line_segment) = 1
        BEGIN
            /* The test point is on one of the line segments between
               @start_point and @end_point. Return 1 and stop the 
               recursion. */

            SET @result = 1;
        END
        ELSE
        BEGIN
            /* The test point is not between the @start_point and
               @start_point + 1. Increment @start_point by 1 and
               continue recursively. */

            SET @result = [dbo].[func_PointBetween](@path, 
                                                    @start_point + 1,
                                                    @end_point,
                                                    @test_point);
        END
    END
    ELSE
    BEGIN
        /* There are no further points. The test point is not between the
           @start_point and @end_point. Return 0 and stop the recursion. */

        SET @result = 0;
    END

    RETURN @result;
END

To test the above function, I am defining the 6-point linestring which is shown in the map above. Then we'll define two test points: @test_point_a, which lies exactly between the third and the fourth point, and @test_point_b, which lies out of the path.

DECLARE @road geography;
DECLARE @test_point_a geography;
DECLARE @test_point_b geography;

SET @road = geography::STGeomFromText('LINESTRING(-122.360 47.656, 
                                                  -122.343 47.656, 
                                                  -122.310 47.690, 
                                                  -122.310 47.670, 
                                                  -122.300 47.670, 
                                                  -122.290 47.660)', 
                                                  4326);

/* This point lies between point 3 and point 4 */           
SET @test_point_a = geography::STGeomFromText('POINT(-122.310 47.680)', 4326);

/* This point lies outside the path */
SET @test_point_b = geography::STGeomFromText('POINT(-122.310 47.700)', 4326);

/* This returns 1, because the test point is between start and end */
SELECT dbo.func_PointBetween(@road, 2, 5, @test_point_a);

/* This returns 0 because the test point is not between start and end */
SELECT dbo.func_PointBetween(@road, 4, 5, @test_point_a);

/* This returns 0 because the test point lies outside the path */
SELECT dbo.func_PointBetween(@road, 1, 6, @test_point_b);

You should be able to check the distance (STDistance) between the new point and the subset of the line segment between the start and end points. That distance should evaluate to zero. If I have a chance to delve further into the geography data types I'll try to put together the exact query, but hopefully this gets you started.