2

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.

Line, Polygon and first intersection

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.

  • 1
    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
  • 1
    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
1

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
1

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.

1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.