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