Efficient maths algorithm to calculate intersectio

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

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 2

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;
        }
    }
}

Answer 3

(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 4

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 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

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.