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.

Improve this question

4 Answers 4

Reset to default
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.

Improve this answer
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. Commented Jun 3, 2015 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?

Improve this answer
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.

Improve this answer
0

Please check isLeft() function in this link.

Improve this answer
1
  • That works for a single line segment, not a polyline Commented Jun 4, 2015 at 16:05

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.