XNA line segment intersection?

Lets say we have 4 Vector2's (yes this is 2d), so we have lineOneStart开发者_Go百科, lineOneEnd, lineTwoStart and lineTwoEnd.

How can I detect if the 2 lines cross? I don't care where they cross, I just want to know if they intersect.

---

Check this formula by Bourke.

I recently had to solve this issue too. Another option is using (getting) the equation of the line (y = mx + c) but there are several edge cases you need to be concerned with, as well as actually checking if the point of intersection is within the line segment. The formula in the link above works, though I cannot really comment on how the equation is re-arranged, all I'll say is it works ;)

Edit:

As mentioned by AndiDog, another site I used (the example is excellent too) is this tutorial. As this is XNA the second link will be right up your street.

Edit (Content from broken link):

The equations of the lines are Pa = P1 + ua ( P2 - P1 ) and Pb = P3 + ub ( P4 - P3 )

Solving for the point where Pa = Pb gives the following two equations in two unknowns (ua and ub) x1 + ua (x2 - x1) = x3 + ub (x4 - x3) and y1 + ua (y2 - y1) = y3 + ub (y4 - y3) Solving gives the following expressions for ua and ub

Substituting either of these into the corresponding equation for the line gives the intersection point. For example the intersection point (x,y) is x = x1 + ua (x2 - x1) y = y1 + ua (y2 - y1)

Notes: The denominators for the equations for ua and ub are the same. If the denominator for the equations for ua and ub is 0 then the two lines are parallel. If the denominator and numerator for the equations for ua and ub are 0 then the two lines are coincident. The equations apply to lines, if the intersection of line segments is required then it is only necessary to test if ua and ub lie between 0 and 1. Whichever one lies within that range then the corresponding line segment contains the intersection point. If both lie within the range of 0 to 1 then the intersection point is within both line segments.

---

There's a tutorial on that topic (line segment intersection).

---

For completeness I will include below the algorithm when lines are represented in (a,b,c) coordinates such that the equation for the line is a*x+b*y+c=0.

• Two lines with coordinates (a1,b1,c1) and (a2,b2,c2) intersect at a point (x,y)

• Find the homogeneous coordinates of the point as

  u = b1*c2-b2*c1;
  v = a2*c1-a1*c2;
  w = a1*b2-a2*b1;
  

• If lines are parallel then w=0.

• Otherwise the intersection point is located at

  x = u/w;
  y = v/w;
  

Appendix

• To define a line (a,b,c) through two points (x1,y1) and (x2,y2) use

  a= y1-y2;
  b= x2-x1;
  c= x1*y2-y1*x2;
  

• To define a line (a,b,c) through a point (x,y) with polar direction (cos(θ),sin(θ))

  a= -sin(θ);
  b=  cos(θ);
  c= x*sin(θ)-y*cos(θ);