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.

Answer 1

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.

Answer 2

If you get the chance you should really check out the Collision Detection bible, "Real Time Collision Detection" if you plan on doing anything non-trivial. I'm not a professional game programmer and I understood and could apply the concepts in it with little trouble.

Amazon - Real Time Collision Detection

Basically, doing a set of line intersection tests is expensive no matter what. What you do is use things like Bounding Boxes (axis aligned or oriented) over your complex polygons. This will allow you to quickly do a worst case O(N^2) check of collision between each "object". You can then speed things up even further by using spatial trees (Binary Partitioning or QuadTrees) by only checking intersections of objects close to eachother.

This allows you to prune many, many collision tests. The best optimization is not doing something at all. Only once you have a collision between bounding boxes do you do your expensive line intersections to determine if the objects truly do intersect or not. This allows you to scale the number of objects up while still keeping the speed reasonable.

Answer 3

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 4

public struct PointD
{
    public 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 5

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 6

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 7

(I would leave this as a comment, except I haven't yet figured out how to do so.)

I would just like to add, as an alternative/complement to a bounding box test, you could also test to see if the distance between the mid-points of the lines are greater than half of the combined length of the lines. If so, the lines can't possibly intersect.

Imagine a minimal enclosing circle for each line, then test circle intersection. This allows for pre-computation (at least for static lines, and lines that preserve their length) and an efficient way to exclude a lot of potential intersections.

Answer 8

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 9

private function Loop(e:Event):void
{
    var x12:Number = Ball1.x - Ball2.x;
    var x34:Number = Ball3.x - Ball4.x;
    var y12:Number = Ball1.y - Ball2.y;
    var y34:Number = Ball3.y - Ball4.y;

    // Det
    var c:Number = x12 * y34 - y12 * x34;

    if (Math.abs(c) < 0.01)
    {
        Circle.visible = false;
    }
    else
    {
        var a:Number = Ball1.x * Ball2.y - Ball1.y * Ball2.x;
        var b:Number = Ball3.x * Ball4.y - Ball3.y * Ball4.x;
        var px:Number = (a * x34 - b * x12) / c;
        var py:Number = (a * y34 - b * y12) / c;

        var Btwn12x:Boolean = (px >= Math.min(Ball1.x, Ball2.x)) && (px <= Math.max(Ball1.x, Ball2.x));
        var Btwn12y:Boolean = (py >= Math.min(Ball1.y, Ball2.y)) && (py <= Math.max(Ball1.y, Ball2.y));
        var Btwn34x:Boolean = (px >= Math.min(Ball3.x, Ball4.x)) && (px <= Math.max(Ball3.x, Ball4.x));
        var Btwn34y:Boolean = (py >= Math.min(Ball3.y, Ball4.y)) && (py <= Math.max(Ball3.y, Ball4.y));

        var Btwn12:Boolean = Btwn12x && Btwn12y;
        var Btwn34:Boolean = Btwn34x && Btwn34y;

        if(Btwn12 && Btwn34)
        {
            Circle.visible = true;
            Circle.x = px;
            Circle.y = py;
        }
        else
        {
            Circle.visible = false;
        }
    }
}