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

In reply to Re: line segment intersection (math) by tye
in thread line segment intersection by bobdeath

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.