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

Just a quick idea: would it be possible to connect the last and first vertex of your polyline, so that it would become a polygon? You could then do a simple inside/outside check do determine whether the vehicle is left/right of the line (this ofcourse depends on the direction of the polygon).

However, this method does assume that the polygon is still not self-intersecting after connecting the last and first vertex.

Answer 2

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 3

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.

Answer 4

This is a standard sort of problem from computational geometry. Since you're looking to test whether a point (x0, y0) is left-of a given surface (your polyline), you need to identify which segment to test against by its height. One easy way to do this would be to build a tree of the lower point of each segment, and search in that for the test point's predecessor. Once you have that segment, you can do your left-of test directly: if it's left of both endpoints, or between them on the appropriate side, then you return true.

I am assuming here that you guarantee that the vertical extent of your polyline is greater than where you might find your query point, and that the line doesn't overlap itself vertically. The latter assumption might be quite poor.

Expansion in response to OP's comment:

Note that the angle example in the question contradicts the first assumption - the polyline does not reach the height of the search point.

One way to conceptualize my method is by sorting your segments vertically, and then iterating through them comparing your point's y-coordinate against the segments until your point is above the lower endpoint and below the higher endpoint. Then, use the endpoints of the segment to figure out the x-intercept at the given y. If the point has a lower x-cooordinate, it's to the left, and if it has a greater x-coordinate, it's to the right.

There are two ways to improve on this explanation in a real implementation, one of which I mentioned about:

1. Use a balanced search tree to find the right segment instead of iterating through a sorted list, to bring the time from O(n) to O(log n)
2. Reconceptualize the search as finding the intersection of the polyline and the horizontal line y = y0 through the search point. Then just compare the x value of the intersection against the search point.