# How to find the “first” intersection of a line with anything else

I am trying to find the first intersection of a line with anything else.

By first intersection I mean the first intersection, if you follow the line in its direction from start to end.

Check the image below, it should make it clear. Black is a line, blue is another geometry, here a polygon, red is the point I am looking for. Maybe there is some standard algorithm for this that I am not aware of? Or maybe a combination of multiple ones?

I am not interested in solutions of closed-source software.

• As Mac and Tosh discovered in the classic Looney Toons short, the definition of "first" is dependent on order of execution. – Vince Nov 9 '16 at 21:31
• Yeah but a linestring has a start and an end if you consider a standard Simple Feature ordered list of points as its "body". – bugmenot123 Nov 9 '16 at 22:07
• If you break the line at the Polygon boundaries, wont the polyline containing the start point have the first node at it's end? – klewis Nov 9 '16 at 23:04
• It can be more complicated than that. Computationally, there may be an advantage to fiipping the coordiate stream. – Vince Nov 9 '16 at 23:20
• Oh, I like that idea @klewis! I think that should be bug free or does someone see a problem with that approach? – bugmenot123 Nov 9 '16 at 23:39

Piece-wise example about how to do it with PostGIS functions http://postgis.net/docs/ST_Intersection.html and http://www.postgis.org/docs/ST_Line_Locate_Point.html

1. Find intersection points of the linestring and the exterior of the polygon.
``````select ST_AsText(
ST_Intersection(
ST_GeomFromText('LINESTRING ( 440 280, 760 480 )'),
ST_ExteriorRing(
ST_geomFromText('POLYGON (( 500 400, 620 480, 740 360, 640 280, 500 400 ))'))))
``````
``````"MULTIPOINT(555.66265060241 352.289156626506,673.846153846154 426.153846153846)"
``````
1. Find the distance to each intersection point
``````ST_Line_Locate_Point(
ST_GeomFromText('LINESTRING ( 440 280, 760 480 )'),St_GeomFromText('Point (555.66265060241 352.289156626506)'))

0.361445783132531

ST_Line_Locate_Point(
ST_GeomFromText('LINESTRING ( 440 280, 760 480 )'),St_GeomFromText('Point (673.846153846154 426.153846153846'))

0.730769230769231
``````

The first point is located at length of 36.14% from the start point and it is closer that the latter (73.07%).

EDIT

However, if the aim is to get the shortest direct distance to the intersection points, it can be found with http://postgis.net/docs/ST_StartPoint.html and http://postgis.net/docs/ST_Distance.html. Example with the same points as above.

``````select
ST_Distance(ST_StartPoint(
ST_GeomFromText('LINESTRING ( 440 280, 760 480 )')),St_GeomFromText('Point (555.66265060241 352.289156626506)'))
136.394907933349

select
ST_Distance(ST_StartPoint(
ST_GeomFromText('LINESTRING ( 440 280, 760 480 )')),St_GeomFromText('Point (673.846153846154 426.153846153846)'))
275.762525398578
``````
• Thanks! Unfortunately this will fail if the shapes of the geometries are such that the first intersection actually is further away than others. Think many meandering curves. – bugmenot123 Nov 9 '16 at 23:00
• The function ST_Line_Locate_Point is measuring the distance by following the line. Isn't that just what you want: If you follow the path, how long have you walked when you cross the border for the first time? Or do you want to know the shortest direct distance? – user30184 Nov 10 '16 at 6:18
• Oh ouch, I misread it. Yes, ST_Line_Locate_Point seems perfect. Thanks! – bugmenot123 Nov 10 '16 at 9:35

Alternative SQL method based on the suggestion of @klevis.

• Split linestring with the outer ring of the polygon
• Result is a GeometryCollection, select the first part of the collection
• First part should be the one with the original starting point, so select the last point of that first part and you have found the answer.
``````select ST_AsText(
ST_EndPoint(
ST_GeometryN(
ST_Split(
ST_GeomFromText('LINESTRING ( 440 280, 760 480 )'),
ST_ExteriorRing(ST_GeomFromText('POLYGON (( 500 400, 620 480, 740 360, 640 280, 500 400 ))'))),1)));

"POINT(555.66265060241 352.289156626506)"
``````

I am not sure if ST_Split is guaranteed to keep the order of the parts and it might be good to add a test that the start points of the original line and the selected part are equal. If not, select next part with ST_GeometryN and loop as long as needed.

I have a solution in theory which always should work, but require multiple queries and I only provide for postgis: