2
\$\begingroup\$

I need to find the point of intersection between two line segments in 2D space. I receive them in terms of both coordinates of both lines. Because they are line segments I would also need to know if they actually intersect in the first place.

I can find many ways to do this but I would like to know what method would have the best performance in GLSL.

\$\endgroup\$
  • \$\begingroup\$ You'll just have to solve the formula. (Try stackoverflow.com/questions/563198/…) \$\endgroup\$ – Lolums Feb 12 '16 at 16:12
  • \$\begingroup\$ You know you have accepted an answer that was a copy-paste from the internet, right? \$\endgroup\$ – Vaillancourt Feb 26 '16 at 14:16
  • \$\begingroup\$ @AlexandreVaillancourt yeah well its not like someone is coming up with anything else... \$\endgroup\$ – Gerharddc Feb 26 '16 at 15:22
2
\$\begingroup\$

This problem can be extremely easy or extremely difficult; it depends on your application. If all you want is the intersection point, the following should work:


Let A,B,C,D be 2-space position vectors. Then the directed line segments AB & CD are given by:

AB=A+r(B-A), r in [0,1]
CD=C+s(D-C), s in [0,1]

If AB & CD intersect, then

A+r(B-A)=C+s(D-C), or

Ax+r(Bx-Ax)=Cx+s(Dx-Cx)
Ay+r(By-Ay)=Cy+s(Dy-Cy)  for some r,s in [0,1]

Solving the above for r and s yields

    (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
r = -----------------------------  (eqn 1)
    (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)

    (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
s = -----------------------------  (eqn 2)
    (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)

Let P be the position vector of the intersection point, then

P=A+r(B-A) or

Px=Ax+r(Bx-Ax)
Py=Ay+r(By-Ay)

By examining the values of r & s, you can also determine some other limiting conditions:

If 0<=r<=1 & 0<=s<=1, intersection exists
    r<0 or r>1 or s<0 or s>1 line segments do not intersect

If the denominator in eqn 1 is zero, AB & CD are parallel
If the numerator in eqn 1 is also zero, AB & CD are collinear.
  • If they are collinear, then the segments may be projected to the x- or y-axis, and overlap of the projected intervals checked.
  • If the intersection point of the 2 lines are needed (lines in this context mean infinite lines) regardless whether the two line segments intersect, then
  • If r>1, P is located on extension of AB
  • If r<0, P is located on extension of BA
  • If s>1, P is located on extension of CD
  • If s<0, P is located on extension of DC

Also note that the denominators of eqn 1 & 2 are identical.


Source (copy-paste): http://www.gamers.org/dEngine/rsc/usenet/comp.graphics.algorithms.faq

\$\endgroup\$
  • \$\begingroup\$ Please state the source of your copy-pastes. \$\endgroup\$ – Vaillancourt Feb 26 '16 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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