3

I have two points, A and B, and a line string L. A line string is formed by a sequence of points such that consecutive points are joined by a straight line. This is the same as a LineString in Geos - I don't know if CGAL has an equivalent construct.

My question is - what is the most efficient way to determine if A and B lie on the same or different side of the polyline L? I would ideally like to use the Geos::geom library, since my data is in that form, but a CGAL solution would also work.

1

My idea may not be most efficient but anyway, I believe you can at least get a correct answer by creating offset lines to the left and to the right from linestring L and computing shortest distances from A and B to the offset lines. If both A and B have shorter distance to the same offset line it means that they are on the same side of L. That's not true if A and/or B locate between the offset lines so check also that distance from A and B to L is greater than the tolerance used with OffsetLine.

I suppose that GEOS has both OffsetLine and Distance functions.

Another idea:

Build linestring from A to B and check if AB crosses L. If not A and B are on the same side. If they cross you must count the number of intersections. If number is odd (1, 3, 5...) A and B are on different sides but if the number is even (2, 4, 6...) then A and B are still on the same side and line AB just goes through loop(s) in L.

1
  • I think the second method is what I would try if I were doing this from scratch. Iterate through the segments then you're just dealing with segments. Also, in addition to this method, I would keep in mind that since your linestring has two end-points it may mess up points that are beyond your 'boundaries'...so in order to guard for this, perhaps extrapolate the last segments on either end to a bit more than the max/min of any point you're testing. – user1269942 Jun 3 '15 at 20:51
1

My idea is to make line from A and B points (AB). And Find the crossing points AB and L. If 0 than A and B on the same side, if 1 they aren't. If you have more than one it means A and B on the same side just like in the first case. (It may can happen sometimes AB above Lp1 or below Lpn- so it would be better to extend L endpoints with a distance n)

Another idea based on this link below + within. but this is for postgre/postgis... How to create one-sided buffers or parallel lines in PostGIS?

1

I assume that the polyline is unbounded; that is, either the polyline comprises a single line or the first and last pieces are rays. Otherwise, the problem is not well defined.

You can use the CGAL 2D-Arrangement data structure to solve your problem easily: Construct a 2D-Arrangement induced by the polyline and issue two point locations queries for A and B, respectively. If the 2 points lie on the same cell, you will get identical answers.

0

Please check isLeft() function in this link.

1
  • That works for a single line segment, not a polyline – TCSGrad Jun 4 '15 at 16:05

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.