13

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.

Error scenario

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.

Community
  • 1
  • 1
Yuri
  • 2,008
  • 17
  • 36
  • I assume the polyline is not self-intersecting, is it? – Sergey Kalinichenko May 14 '12 at 12:38
  • @dasblinkenlight nope, this is explicitly checked beforehand. A polyline is rejected if it is. – Yuri May 14 '12 at 12:39
  • 1
    I think I need better definition for "on the left of" there cases when I can not tell if the case is "on the left" of or "on the right of" – Ivaylo Strandjev May 14 '12 at 12:44
  • @izomorphius I am not really sure how to formalize it. If you want some kind of analogy to make it more intuitive, think of it as a fence, where the begin and endpoints extend to infinity. (Ofcourse this is a direct fence, hence it is oriented in a specific manner, as if you are walking along that fence in a direction). Now is the vehicle to the left or the right of the fence. Does this help? – Yuri May 14 '12 at 12:53
  • If the polyline is (0,0) -> (10,0) and the polygon is (20,-20), (-20, -20), (-20, 20), (20,20) is the polygon on the left or on the right? That is what I meant when I said you need to formalize better - there are cases where you can not decide which one is correct unless you define better what is on the left. – Ivaylo Strandjev May 14 '12 at 13:16
  • @Izomorphius Now I understand your confusion. I think you misread the question. I have a polyline and a vertex. – Yuri May 14 '12 at 13:22
  • @Yuri no it does not help. A polyline can never define half-plane(assuming you made a typo by replacing plane with space) as it is finite. – Ivaylo Strandjev May 14 '12 at 13:24
  • @izomorphius You are indeed right that I meant space, but I replaced my reply with a different reply, as I think I now understand your confusion. Sorry for that. – Yuri May 14 '12 at 13:28

4 Answers4

1

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.

Thomash
  • 6,339
  • 1
  • 30
  • 50
  • Sorry, but I disagree. The fact that I didn't tell you that I define **on the line** as *left*, or *right*, or maybe even the value *unknown* doesn't make it ambiguous, incomplete maybe. I just posted a very specific scenario for which I am seeking an elegant method. As you can see, I already have a fix, which works. The problem is that I don't like the method itself, as it feels like a workaround to a nice geometric proof. – Yuri May 14 '12 at 13:18
  • I think you don't understand me (maybe because my English is not perfect), If your polyline is finite (and that's how I understand your problem), how can you say that a car is to the left or to the right? – Thomash May 14 '12 at 13:31
  • I treat the first and last segment of the polyline as if they are extended to infinity. – Yuri May 14 '12 at 13:36
  • Ok, then 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. – Thomash May 14 '12 at 13:42
  • This sounds like a valid alternative to my solution. However, do you feel like it is easier to implement? If so: Could you provide some more explanation. I can hardly use external libraries, due to policy. – Yuri May 14 '12 at 13:51
  • It is easy to implement, I have edited my answer to provide more explanation. – Thomash May 14 '12 at 14:05
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.

kadu
  • 746
  • 12
  • 29
0

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.

Intru
  • 650
  • 1
  • 4
  • 16
  • Unfortunately, the drawback you mention is something that is definitely going to happen. – Yuri May 14 '12 at 12:58
0

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.
Phil Miller
  • 36,389
  • 13
  • 67
  • 90
  • Both your assumptions are OK. They are quite restrictive, but the input does indeed fulfill those criteria. Unfortunately I do not really understand from your post how to select the proper segment. Could you provide a more step-by-step example for the image I posted, maybe? – Yuri May 14 '12 at 13:20