Formula To Determine If An Infinite Line And A Line Segment Intersect?

Given a point on a line and that line's slope how would one determine if the line, extending in each direction infinitely, intersects with a line segment (x1,y1), (x2,y2) and, if s

Solution 1:

Arbitrary point on the first line has parametric equation

dx = Cos(slope)
dy = Sin(Slope)
x = x0 + t * dx     (1)
y = y0 + t * dy

Line containing the second segment

dxx = x2 - x1
dyy = y2 - y1
x = x1 + u * dxx    (2)
y = y1 + u * dyy

Intersection exists if linear system

x0 + t * dx = x1 + u * dxx   (3)    
y0 + t * dy = y1 + u * dyy

has solution for unknowns t and u and u lies in range [0..1]

Intersection point could be calculated with substitution of u found in the equation pair (2)

Solution 2:

Please don't ask me to explain how exactly this is working, I've just extrapolated/rewritten it from some ancient code I've had laying around. (Actionscript 1)

some functions to build the objects for this example:

functionpoint(x, y){ 
    return {x, y} 
}
functionline(x0, y0, x1, y1){
  return {
    start: point(x0, y0), 
    end: point(x1, y1)
  } 
}
functionray(x, y, vx, vy){
  return {
    start: point(x, y), 
    vector: point(vx, vy)
  } 
}
functionray2(x, y, angle){
    var rad = angle * Math.PI / 180;
    return ray(x, y, Math.cos(rad), Math.sin(rad));
}

the intersection-code:

//returns the difference vector between two points (pointB - pointA)
function delta(a, b){ return point( b.x - a.x, b.y - a.y ) }
//kind of a 2D-version of the cross-product
functioncp(a, b){ return a.y * b.x - a.x * b.y } 

function intersection(a, b){
    var d21 = a.vector || delta(a.start, a.end),
        d43 = b.vector || delta(b.start, b.end),
        d13 = delta(b.start, a.start),
        d = cp(d43, d21);

    //rays are paralell, no intersection possible
    if(!d) return null;
    //if(!d) return { a, b, position: null, hitsA: false, hitsB: false };

    var u = cp(d13, d21) / d,
        v = cp(d13, d43) / d;

    return {
        a, b,

        //position of the intersection
        position: point(
            a.start.x + d21.x * v,
            a.start.y + d21.y * v
        ),  
        //is position on lineA?
        hitsA: v >= 0 && v <= 1,
        //is position on lineB?
        hitsB: u >= 0 && u <= 1,

        timeTillIntersection: v,
    };
}

and an example:

var a = line(0, 0, 50, 50);

var b = line(0, 50, 50, 0);             //lines are crossingconsole.log(intersection(a, b));

var c = line(100, 50, 150, 0);          //lines are not crossingconsole.log(intersection(a, c));

var d = line(100, -1000, 100, 1000);    //intersection is only on d, not on aconsole.log(intersection(a, d));

var e = ray(100, 50, -1, -1);           //paralell to aconsole.log(intersection(a, e));

returns information about the intersection point, and wether it is on the passed lines/rays. Doesn't care wether you pass lines or rays.

about timeTillIntersection: if the first argument/ray represents a ball/bullet/whatever with current position and motion-vector, and the second argument represents a wall or so, then v, aka timeTillIntersection determines how much time it takes till this ball intersects/hits the wall (at the current conditions) in the same unit as used for the velocity of the ball. So you basically get some information for free.

Solution 3:

What you search is the dot product. A line can be represented as a vector.

When you have 2 lines they will intersect at some point. Except in the case when they are parallel.

Parallel vectors a,b (both normalized) have a dot product of 1 (dot(a,b) = 1).

If you have the starting and end point of line i, then you can also construct the vector i easily.