Line to line intersection - detect direction

Question

Hi,

I am working on a geomapping application and here is my problem.

We have a feature that allow users to draw a line on a map. Then the application will show all the objects (cars for instance) who went trough that line (we get daily position data of the objects so we can detrmine their path).

I am using MultiLineString to determine the path of each ojects and Line for the line (huh). Then I use STIntersects to determine which paths are crossing the line.

SELECT * FROM Paths WHERE Path.STIntersetct(@line) = 1

That works perfectly, but now I need to determine in which way the line has been crossed, left to right or top to bottom.

In fact it does not really matter, I just need to split in half the objects who crossed in a direction and the ones who crossed in the other direction.

Any idea for a straightforward way to do it ?

Answer 1

First, work out the equation for your straight line. The gradient of the line can be calculated as follows:

DECLARE @m float = (@line.STEndPoint().STY - @line.STStartPoint().STY) / (@line.STEndPoint().STX - @line.STStartPoint().STX);

Therefore, the y value at any x value along the line is given by:

y = @m(x - @line.STEndPoint().STX) + @line.STStartPoint().STY;

What you can then do is take the start point and end point of each of your paths and compare them to the y value of the line at the corresponding x value - if their y value is less than this expected value then they lie underneath the line, whereas if it is greater than this value they are above it.

Group the results according to whether the y value of the path startpoint is greater or less than this value, and you'll have those objects that crossed in one direction separated from those that crossed in the other direction.

---

twitter: @alastaira blog: http://alastaira.wordpress.com/

Answer 2

Hi !

First, thank you for your answer. I see what you mean but the problem I can see coming is due to the fact that the path is not a straight line. Therefore by taking the start point and the end point and calculating the gradient, I could get a wrong result.

Let's take a concrete example. A car which is going from point a to point b accross a river so it need to drive over a bridge. The line is perpendicular to the bridge. The path is like a U with the left side lower than the right side. And imagine there is several cars going from anywere in one side of the bridge to anywhere on the other side of the bridge.

I think we should take the two points of the path that are the closest to the intersection.

Does it make sense or I might have misunderstood something ?

Thanks

Answer 3

The paths of your objects aren't straight, but your line is a straight line, right?

So long as each path only crosses the line once (is that a fair assumption?), you can still work out the direction it crossed the line in by looking at the start and end points of the path (I think).

In the example below, whatever route is taken from the start to the end point it must cross the line from left to right.

edit: I see from your example that you're talking about quite big distances (i.e. intercontinental) and I guess therefore that you want to work out the answer on a geodetic model of the earth rather than using flat geometry? That makes it more complicated - in my answer I assumed you were doing this at a city-wide scale, say...

 

---

twitter: @alastaira blog: http://alastaira.wordpress.com/

Answer 4

In fact the line is not necessary straight, it could be in any direction. And the start and end point of the path can potentially be anymwhere.

Therefore, the kind of situations illustrated below are very likely to happend.

                          

What I am thinking is to get the intersection point, add a buffer (as small as possible), get the portion of the path which intersects the buffer and take the start point and end point of that segment to determine the crossing direction.

How does it sounds to you ? I think it is quiet heavy and performance might be an issue as we are working with thousands of paths. But then it is still not clear how to determine the direction given the fact that the line can be potentially in any direction.

Note : geometry is fine for our specific case, I used geography previously before changing for geometry.

Answer 5

In fact the line is not necessary straight, it could be in any direction. And the start and end point of the path can potentially be anymwhere.

Therefore, the kind of situations illustrated below are very likely to happend.

                          

What I am thinking is to get the intersection point, add a buffer (as small as possible), get the portion of the path which intersects the buffer and take the start point and end point of that segment to determine the crossing direction.

How does it sounds to you ? I think it is quiet heavy and performance might be an issue as we are working with thousands of paths. But then it is still not clear how to determine the direction given the fact that the line can be potentially in any direction.

Note : geometry is fine for our specific case, I used geography previously before changing for geometry.

Sounds like a reasonable approach - give it a try! The alternative would be to create a custom SQLCLR procedure that iterated through each point in the path and tested whether the direct line between that point and the next crossed the line. If so, extract just the line segment between those points.

Don't know whether that would be more performant than the buffer method or not - probably depends on exactly how many points there are in your paths...

---

twitter: @alastaira blog: http://alastaira.wordpress.com/

Answer 6

ouch almost there but one problem remains...

 

@path.STIntersection(@path.STIntersection(@line).STBuffer(2)).STStartPoint();

So basically, the purple line is like the finishing line, the green one is my path. The blue circle is the buffer, and the point is the start point.

The only problem is when I get the result of the STIntersection function, the order in which the path is defined is lost.
I tried to change the order of the point in my MultiLineString geometry, it does switch the start point and end point of the path, but as soon as I get the result of STIntersection, this line is always defined in the same order.

Any idea how to detect which one is really the start point according to the order in which the path is defined ?

Here are some sample data to play with if you like :

LINESTRING (96.2511893434822 -23.4393241145558, 72.102759276879 12.2629590791594) 

LINESTRING (24.8316 -34.99096667, 29.08773333 -34.64005, 34.03255 -33.8163, 38.49656667 -32.59425, 43.29673333 -30.97231667, 51.82653333 -27.48506667, 56.20056667 -25.39876667, 60.05246667 -23.39663333, 64.21128333 -21.03548333, 68.24725 -18.56361667, 71.95763333 -16.15951667, 75.6007 -13.69758333, 77.32101667 -12.48135, 81.91408333 -7.96966667, 84.41055 -5.34908333, 87.43131667 -2.13338333, 90.31636667 0.95783333, 93.02673333 3.92996667, 103.79908 1.1684333, 104.20072 1.2639166, 105.59388333 3.83276667, 111.203 10.13955, 116.32558333 16.38365, 117.56136667 17.8572, 121.34707 22.148016, 122.49859 24.989267, 123.85421667 31.86485)