Elegant "Left-of" test for Polyline

Question

Given:

• (X,Y) coordinate, which is the position of a vehicle.
• Array of (X,Y)'s, which are vertices in a polyline. Note that the polyline consists of straight segments only, no arcs.

What I want:

• To calculate whether the vehicle is to the left or to the right of the polyline (or on top, ofcourse).

My approach:

• Iterate over all line-segments, and compute the distance to each segment. Then for the closest segment you do a simple left-of test (as explained here for instance).

Possible issues:

• When three points form an angle smaller than 90 degrees (such as shown in the image blow), a more complicated scenario arises. When the vehicle is in the red segment as shown below, the closest segment can be either one of the two. However, the left-of test will yield right if the first segment is chosen as the closest segment, and left otherwise. We can easily see (at least, I hope), that the correct result should be that the vehicle is left of the polyline.

My question:

• How can I elegantly, but mostly efficiently take care of this specific situation?

My fix so far:

• Compute for both segments a point on that segment, starting from the vertex point.
• Compute the distance from the vehicle to both of the points, using Euclidian distance
• Keep the segment for which the computed point is the closest.

I am not very happy with this fix, because I feel like I am missing a far more elegant solution, my fix feels rather "hacky". Efficiency is key though, because it is used on a realtime embedded system.

Existing codebase is in C++, so if you want to write in a specific language, C++ has my preference. Thanks!

[edit] I changed my fix, from a perpendicular point to a parallel point, as I think it is easier to follow the line segment than compute the outward normal.

Answer 1

This topic has been inactive for so long that I believe it's dead. I have a solution though.

However, the left-of test will yield right if the first segment is chosen as the closest segment, and left otherwise.

You've used slightly ambiguous language. I'm gonna use segments to speak of the line segments in the polyline and quadrants to speak of the areas delimited by them. So in your case, you'd have a red quadrant which seems to be on the right of one segment and on the left of the other.

If the left-of test yields different answers for different segments, you should redo the test on the segments themselves. In your case, you'd have:

• The quadrant is on the RIGHT of the first segment
• The quadrant is on the LEFT of the second segment

Both segments disagree on where the quadrant lies, so you do two further disambiguation tests:

• The second segment is on the RIGHT of the first segment
• The first segment is on the RIGHT of the second segment

This allows us to conclude that the second segment is in between the first segment and the quadrant—since each of those two lies on a different side of the second segment. Therefore, the second segment is "closer" to the quadrant than the first and it's answer to the left-right test should be used as the correct one.

(I'm almost sure you can do with only one of the two disambiguation tests, I've put both in for clarity)

For the sake of completeness: I believe this solution also accounts for your demands of efficiency and elegance, since it uses the same method you've been using from the start (the left-of test), so it meets all the conditions specified: it's elegant, it's efficient and it takes care of the problem.

Answer 2

Let infinity = M where M is big enough. You can consider that everything is in the square [-M,M]x[-M,M], split the square with your polyline and you have now two polygons. Then checking if the car is in a given polygon can be done very simply with angles.

I consider that your first point and your last point have M in there coordinates. You may need to add some of these points to have a polygon: (-M,-M), (M,-M), (M,M) and (-M,M).

Once you have a polygon for the left of the polyline, sum the angles OĈP where O is a fixed point, C is the car and P is a point of the polygon. If the sum is 0 then the car is outside of the polygon, else it is inside.