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]

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]

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]

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]

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

I found the necessary module on CPAN. It's called Imager::Graph::Util. Here's an example script:

#!/usr/bin/perl -w
use strict;
use Imager::Graph::Util;

my ($ax, $ay, $bx, $by, $cx, $cy, $dx, $dy) = GetLines(); # you have t
+o write that subroutine

my @line1 = line_from_points($ax, $ay, $bx, $by);
my @line2 = line_from_points($cx, $cy, $dx, $dy);

# @p will contain the (x, y) point of intersection if it exists
my @p = intersect_lines(@line1, @line2);
[download]

I took a look at Imager::Graph::Util and the math does not look so good. It doesn't use parametric equations like tye has, so it will be more prone to overflow and roundoff errors. Also, it solves line intersections only, not segments.

An alternative to simplify this type of equation is to use Math::VectorReal. There's a neat formula with vector cross products to solve this problem. It tests for being outside the segment as early as it can.

Read more... (1379 Bytes)

• Calculation of Line intersections

I'm no expert on the subject myself, but I think you need to look up "matrix algebra" on Google.

----
I wanted to explore how Perl's closures can be manipulated, and ended up creating an object system by accident.
-- Schemer

Note: All code is untested, unless otherwise stated

It looks like a gold mine of functions including polygon area (with holes), interfacing to gpc for general polygon clipping, translation, rotation, and scaling, etc. I haven't tried it yet but it looks quite interesting.

sub intersectLines {
#working subroutine. thanks to the original poster.
    my( $ax, $ay, $bx, $by, $cx, $cy, $dx, $dy )= @_;
    my @rval=0;
    
    my $d1=($ax-$bx)*($cy-$dy);
    my $d2=($ay-$by)*($cx-$dx);
    
    my $dp = $d1 - $d2;
    my $dq = $d2 - $d1;
    
    if($dp!=0 && $dq!=0) {    
       my $p = ( ($by-$dy)*($cx-$dx) - ($bx-$dx)*($cy-$dy) ) / $dp;   
+ 
       my $q = ( ($dy-$by)*($ax-$bx) - ($dx-$bx)*($ay-$by) ) / $dq;
      if($p>0 && $p<=1 && $q>0 && $q<=1) {    
         my $px= $p*$ax + (1-$p)*$bx;
         my $py= $p*$ay + (1-$p)*$by;
         @rval=($px, $py);
      }
   }
    
   return(@rval);
}
[download]