10
\$\begingroup\$

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

Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ 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")? \$\endgroup\$
    – bummzack
    Dec 12, 2011 at 14:56
  • 1
    \$\begingroup\$ 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"? \$\endgroup\$
    – Hackworth
    Dec 12, 2011 at 15:12
  • \$\begingroup\$ 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. \$\endgroup\$
    – brandon
    Dec 12, 2011 at 15:13
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – sam hocevar
    Dec 12, 2011 at 16:17
  • \$\begingroup\$ I've split my question in 2, as requested. The 2nd part is here: gamedev.stackexchange.com/questions/21463/… \$\endgroup\$
    – Robin Rodricks
    Dec 23, 2011 at 13:22

2 Answers 2

Reset to default
11
\$\begingroup\$

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?

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ 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 :) \$\endgroup\$
    – notlesh
    Dec 12, 2011 at 18:10
  • \$\begingroup\$ @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. \$\endgroup\$
    – Cascabel
    Dec 12, 2011 at 19:19
  • \$\begingroup\$ +1 for the trollface, and good math :). However your 'towards' diagram actually still has a 'away' - just move the starting point above the line. \$\endgroup\$
    – Jonathan Dickinson
    Dec 12, 2011 at 21:50
  • \$\begingroup\$ @JonathanDickinson thanks, I updated the image to make it slightly clearer what my interrogation is! \$\endgroup\$
    – sam hocevar
    Dec 12, 2011 at 22:44
2
\$\begingroup\$

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)

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 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"? \$\endgroup\$
    – Hackworth
    Dec 12, 2011 at 16:13
  • \$\begingroup\$ 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. \$\endgroup\$
    – Ravachol
    Dec 12, 2011 at 16:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .