One of my favorite things I learned in a "higher math" class was that all of the points on a line can be parameterized as linear combination of two points defining the line segment:

    P = (p-1)*A + p*B
[download]

For p=0 we get A, for p=1 we get B, for p between 0 and 1, we get points between A and B. For p < 0, we get points past A. For p > 1, we get points past B. It can simplify lots of calculations.

Anyway, you can then derive the intersection of two lines:

P = p*A + (1-p)*B
Q = q*C + (1-p)*D

Find p,q such that P=Q:

[ p*ax + (1-p)*bx, p*ay + (1-p)*by ] =
[ q*cx + (1-q)*dx, q*cy + (1-q)*dy ]

p*ax + (1-p)*bx = q*cx + (1-q)*dx
p*ay + (1-p)*by = q*cy + (1-q)*dy

p*(ax-bx) + bx = q*(cx-dx) + dx
p*(ay-by) + by = q*(cy-dy) + dy

( p*(ax-bx) + bx-dx ) / (cx-dx) = q
( p*(ay-by) + by-dy ) / (cy-dy) = q

  ( p*(ax-bx) + bx-dx ) / (cx-dx)
= ( p*(ay-by) + by-dy ) / (cy-dy)

  ( p*(ax-bx) + bx-dx ) * (cy-dy)
= ( p*(ay-by) + by-dy ) * (cx-dx)

  p*(ax-bx)*(cy-dy) + (bx-dx)*(cy-dy)
= p*(ay-by)*(cx-dx) + (by-dy)*(cx-dx)

p*( (ax-bx)*(cy-dy) - (ay-by)*(cx-dx) )
  = (by-dy)*(cx-dx) - (bx-dx)*(cy-dy)
[download]

So use the follwing:

p = ( (by-dy)*(cx-dx) - (bx-dx)*(cy-dy) )
  / ( (ax-bx)*(cy-dy) - (ay-by)*(cx-dx) )

px= p*ax + (1-p)*bx
py= p*ay + (1-p)*by
[download]

so you can use:

sub intersectLines {
    my( $ax, $ay, $bx, $by, $cx, $cy, $dx, $dy )= @_;
    my $d= ($ax-$bx)*($cy-$dy) - ($ay-$by)*($cx-$dx);
    die "Parallel lines"   if  0 == $d;
    my $p = ( (by-dy)*(cx-dx) - (bx-dx)*(cy-dy) ) / $d;
    my $px= $p*$ax + (1-$p)*$bx;
    my $py= $p*$ay + (1-$p)*$by;
    return( $px, $py );
}
[download]

Untested, but you have the entire derivation so you can find the mistakes if there were any. (:

Note that we get "for free" whether the intersection is between A and B. If you derive the formula for q, then you can also tell whether the intersection is between C and D. This then tells you whether the line segments intersect (which you didn't ask to know, but is one advantage of using this technique).

                - tye