Efficient maths algorithm to calculate intersections

Question

For a game I am developing I need an algorithm that can calculate intersections. I have solved the problem, but the way I have done it is really nasty and I am hoping someone here might have a more elegant solution.

A pair of points represent the end points of a line drawn between them. Given two pairs of points, do the drawn lines intersect, and if so, at what point?

So for example call the lines (A.x, A.y)-(B.x, B.y) and (C.x, C.y)-(D.x, D.y)

Can anyone think of a solution? A solution in any language will do.

Edit: A point I should have made clearer, the algorithm must return false if the point of intersection is beyond the lengths of the line segments. I.E. this isn't an intersecition: lines.gif

Answer 1

Here are some nice stuff to read:

http://mathworld.wolfram.com/Intersection.html

http://www.idevgames.com/forum/showthread.php?t=8784

I think you will find what you need here.

Answer 2

You need to solve the simultaneous equations for the two lines.

See here for the algorithm with some code.

Answer 3

public struct PointD
{
   pubic double X
{get;set;}
public double Y
{get;set;}
}


 /// <summary>
 /// Find the intersection point between two lines.
 /// </summary>
 /// <param name="IntersectPoint">The intersection point. A <see cref="Esteem.Geometry.PointD">PointD</see> structure.</param>
 /// <param name="L1StartPoint">The starting point of first line. A PointD structure.</param>
 /// <param name="L1EndPoint">The end point of first line. A PointD structure.</param>
 /// <param name="L2StartPoint">The starting point of second line. A PointD structure.</param>
 /// <param name="L2EndPoint">The end point of second line. A PointD structure.</param>
 /// <param name="L1IntersectPos">The intersection position at first line.</param>
 /// <param name="L2IntersectPos">The intersection position at second line.</param>
 /// <returns>Returns a boolean. True if there is intersection, false otherwise.</returns>
 /// <remarks>The formula is taken from comp.graphics.algorithms Frequently Asked Questions.</remarks>
 public static bool LineIntersect(out PointD IntersectPoint, PointD L1StartPoint, PointD L1EndPoint, PointD L2StartPoint, PointD L2EndPoint, out double L1IntersectPos, out double L2IntersectPos) 
 {
  IntersectPoint = new PointD();
  double ay_cy, ax_cx, px, py;
  double dx_cx = L2EndPoint.X - L2StartPoint.X,
   dy_cy = L2EndPoint.Y - L2StartPoint.Y,
   bx_ax = L1EndPoint.X - L1StartPoint.X,
   by_ay = L1EndPoint.Y - L1StartPoint.Y;

  double de = (bx_ax) * (dy_cy) - (by_ay) * (dx_cx);
  //double tor = 1.0E-10;  //tolerance


  L1IntersectPos = 0;   L2IntersectPos = 0;
  if (Math.Abs(de)<0.01)
   return false;
  //if (de > -tor && de < tor) return false; //line is in parallel

  ax_cx = L1StartPoint.X - L2StartPoint.X;
  ay_cy = L1StartPoint.Y - L2StartPoint.Y;
  double r = ((ay_cy) * (dx_cx) - (ax_cx) * (dy_cy)) / de;
  double s = ((ay_cy) * (bx_ax) - (ax_cx) * (by_ay)) / de;
  px = L1StartPoint.X + r * (bx_ax);
  py = L1StartPoint.Y + r * (by_ay);

  IntersectPoint.X = px;  //return the intersection point
  IntersectPoint.Y = py; //return the intersection position
  L1IntersectPos = r;   L2IntersectPos = s;

  return true; //indicate there is intersection
 }

To check whether the intersection point is not beyond the original length of the line, just make sure that 0<r<1 and 0<s<1

Answer 4

A simple optimization that may save you alot of time is to check the axis-aligned bounding boxes of the lines prior to getting into the intersection calculation.
If the bounding boxes are completely disjoint then you can be certain there is no intersection.
Of course this is dependent of the data you have. if an intersection is very likely in every check you make then you might find yourself wasting time on a check that is always true.

Answer 5

float x12 = x1 - x2;
float x34 = x3 - x4;
float y12 = y1 - y2;
float y34 = y3 - y4;

float c = x12 * y34 - y12 * x34;

if (fabs(c) < 0.01)
{
  // No intersection
  return false;
}
else
{
  // Intersection
  float a = x1 * y2 - y1 * x2;
  float b = x3 * y4 - y3 * x4;

  float x = (a * x34 - b * x12) / c;
  float y = (a * y34 - b * y12) / c;

  return true;
}

Formulas taken from:
Line-line intersection - Wikipedia

Answer 6

Well, mathematics and scalar products can help there.
- Say you want to intersect segments [AB] and [CD]
- Suppose the line intersection of the lines is M

M is inside segment [ÅB] if and only if
Vector(AB) . Vector(AM) >= 0
and
Vector(AB) . Vector(MB) >= 0

Where the dot "." denotes a scalar product : u . v = ux * vx + uy * vy

So, your algo is :
- find M
- M is inside both segment if and only if the 4 eq below are true
Vector(AB) . Vector(AM) >= 0
Vector(AB) . Vector(MB) >= 0
Vector(CD) . Vector(CM) >= 0
Vector(CD) . Vector(MD) >= 0

Hope this helps

Answer 7

Below is my line-line intersection as described in MathWorld. For general collision detection/intersection you may want to look at the Separating Axis Theorem. I found this tutorial on SAT very informative.

    /// <summary>
    /// Returns the intersection point of the given lines. 
    /// Returns Empty if the lines do not intersect.
    /// Source: http://mathworld.wolfram.com/Line-LineIntersection.html
    /// </summary>
    public static PointF LineIntersection(PointF v1, PointF v2, PointF v3, PointF v4)
    {
        float tolerance = 0.000001f;

        float a = Det2(v1.X - v2.X, v1.Y - v2.Y, v3.X - v4.X, v3.Y - v4.Y);
        if (Math.Abs(a) < float.Epsilon) return PointF.Empty; // Lines are parallel

        float d1 = Det2(v1.X, v1.Y, v2.X, v2.Y);
        float d2 = Det2(v3.X, v3.Y, v4.X, v4.Y);
        float x = Det2(d1, v1.X - v2.X, d2, v3.X - v4.X) / a;
        float y = Det2(d1, v1.Y - v2.Y, d2, v3.Y - v4.Y) / a;

        if (x < Math.Min(v1.X, v2.X) - tolerance || x > Math.Max(v1.X, v2.X) + tolerance) return PointF.Empty;
        if (y < Math.Min(v1.Y, v2.Y) - tolerance || y > Math.Max(v1.Y, v2.Y) + tolerance) return PointF.Empty;
        if (x < Math.Min(v3.X, v4.X) - tolerance || x > Math.Max(v3.X, v4.X) + tolerance) return PointF.Empty;
        if (y < Math.Min(v3.Y, v4.Y) - tolerance || y > Math.Max(v3.Y, v4.Y) + tolerance) return PointF.Empty;

        return new PointF(x, y);
    }

    /// <summary>
    /// Returns the determinant of the 2x2 matrix defined as
    /// <list>
    /// <item>| x1 x2 |</item>
    /// <item>| y1 y2 |</item>
    /// </list>
    /// </summary>
    public static float Det2(float x1, float x2, float y1, float y2)
    {
        return (x1 * y2 - y1 * x2);
    }

Answer 8

Most of the answers already here seem to follow the general idea that:

1. find the intersection of two straight lines passing the given points.
2. determine if the intersection belong to both line segments.

But when intersection does not occur often, a better way probably is to reverse these steps:

1. express the straight lines in the form of y = ax + b (line passing A,B) and y = cx + d (line passing C,D)
2. see if C and D are on the same side of y = ax+b
3. see if A and B are on the same side of y = cx+d
4. if the answer to the above are both no, then there is an intersection. otherwise there is no intersection.
5. find the intersection if there is one.

Note: to do step 2, just check if (C.y - a(C.x) - b) and (D.y - a(D.x) - b) have the same sign. Step 3 is similar. Step 5 is just standard math from the two equations.

Furthermore, if you need to compare each line segment with (n-1) other line segments, precomputing step 1 for all lines saves you time.