Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 8 down vote favorite
2

Given the 4 points describing 2 line segments, how do you calculate if line A is towards or away from line B?

The 2 lines have a fixed length, and can be measured as distance from x1/y1 to x2/y2.

enter image description here

share|improve this question
How is the case with the bezier curve different from the case with straight lines? Do you have a curve that could completely enclose the other line (so that every direction would point "towards")? – bummzack Dec 12 '11 at 14:56
1  
You probably need to clarify your terms. In Geometry, a "line" extends infinitely in either direction, as opposed to a half-line or segment, so 2 lines always cross unless they're parallel. Which one are you asking about? You have drawn an arrow, which implies direction, which to me implies a segment or at most half-line. And what is your definition of "towards" and "away"? – Hackworth Dec 12 '11 at 15:12
Bezier curve might be harder to represent in the equality required to solve a ray-line intersect test. By the way, I'de change the word that represents your arrow to "ray". You might get a quicker response. I'll answer this if I have time during lunch if nobody else does. If not, this is an extremely common task in games. Google "Ray line segment intersect test". I suspect the bezier curve test is similar, but I've never tried it. – brandon Dec 12 '11 at 15:13
3  
You should split your question in two. The part with line segments is very easy. The part with bezier curves is extremely complex and only has an approximate numerical solution. – Sam Hocevar Dec 12 '11 at 16:17
I've split my question in 2, as requested. The 2nd part is here: gamedev.stackexchange.com/questions/21463/… – Jarvis Dec 23 '11 at 13:22

2 Answers

up vote 9 down vote accepted

Let A and B be two points on the black line. Let C and D be your blue segment. The sign of the z coordinate of cross product AB^AC tells you whether C is "left" or "right" of the black line. Similarly, cross product AB^CD tells you whether CD steers "left" or "right" of the black line.

We don't really want to know whether it's left or right; all we want is to make sure they're the same direction or the opposite direction, that's why we multiply the two values.

The following pseudocode should therefore work:

z1 = (xB-xA)*(yC-yA) - (yB-yA)*(xC-xA);
z2 = (xB-xA)*(yD-yC) - (yB-yA)*(xD-xC);
z3 = z1 * z2;

if (z3 < 0)
    ; /* Pointing towards (BUT maybe even crossing) */
else if (z3 > 0 || z2 != 0)
    ; /* Pointing away */
else
    ; /* Parallel */

I am afraid I need some time to write a proper solution for the Bezier curve. Is the following situation towards or away?

Problem?

share|improve this answer
For the curve, I believe you could find the tangent of the curve at the point closest to your line segment and use this in the same way you test your other line segments. Probably a bit harder than it sounds :) – stephelton Dec 12 '11 at 18:10
@stephelton: Look again at the second picture for the bezier curves, pointing toward a curve which curves away. Or consider a curve with a tangent parallel to the possibly intersecting segment, but which curves toward the segment and intersects. – Jefromi Dec 12 '11 at 19:19
+1 for the trollface, and good math :). However your 'towards' diagram actually still has a 'away' - just move the starting point above the line. – Jonathan Dickinson Dec 12 '11 at 21:50
@JonathanDickinson thanks, I updated the image to make it slightly clearer what my interrogation is! – Sam Hocevar Dec 12 '11 at 22:44
up vote 2 down vote

Assuming start point is the green circle, and end point is the red arrow

Compute the distance between the start point as DS and the black segment, and do the same for the end point (red arrow) as DE. If DS>DE, then the segment is pointing toward. if DE>DS, it is pointing away. If both are equal, the two are parallels.

You can find how to compute the distance from a point to a segment here, and to a quadratic bezier curve here. However, depending of the shape of the bezier curve, it might return weird results (the curve can be crossing itself)

share|improve this answer
DS>DE is guaranteed to work only for straight lines. It can fail for Beziers. Also, you don't know his definition of "towards". If the extension of the arrow would cross a line defined by 2 points, but not the segment defined by the same points, is it still "towards"? – Hackworth Dec 12 '11 at 16:13
I'm talking about two segments, not lines, so there is no "extension of the arrow". Also, it doesn't matter where the arrow points, as we are talking about distances here. The closest point on the black line could be a start/end point of the black line, it doesn't matter. The two segments could be collinears, this method would still works as intended. For bezier curves I mentionned it would give weird results depending of the curve's shape. – Ravachol Dec 12 '11 at 16:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.