sub solve{
    my( $a, $b, $c, $d ) = @_;
    my( $x, $y );

    $x = ($b - $a) / ($d - $a - $c + $b);
    $y = ($d - $a) * ($b - $a) / ($d - $a - $c + $b) + $a;
    
    return( $x, $y );
}
[download]

sub solve{
    my( $a, $b, $c, $d ) = @_;

    my $x = ($b - $a) / ($d - $a - $c + $b);
    my $y = ($d - $a) * $x + $a;
    
    return( $x, $y );
}
[download]

formula for line 1:   Y = (D - A) * X + A
formula for line 2:   Y = (C - B) * X + B

intersection: X and Y coordinates of line1 and line2 are equal ...

(D - A) * X + A = (C - B) * X + B

reduces to =>  X = (B - A) / (D - A - C + B)

plug X into equation for line 1 gives ...

Y = (D - A) * (B - A) / (D - A - C + B) + A
[download]

I spend my free time sailing. And despite the fact that GPS's make navigation push-n-click simple, I took an interest in reading through Dutton's Piloting and Navigation cover to cover a couple years ago. I read the 1968 edition, as it came out before GPS, and devotes most of its pages to either Dead Reckoning (deductive reckoning), and Celestial Navigation. BrowserUK's question ignited a lightbulb for me and I flipped open Duttons again to see.

The short answer is that Roger's answer is accurate. And in fact it employs techniques similar to those used in Dead Reckoning. With Dead Reckoning, one takes a bearing to two known points, and triangulates a position. The cool thing about Dead Reckoning is that if you know your direction and rate of travel, you can take a bearing to only one object of known position, twice at a known interval. Thus, if you get a bearing of 45deg at 10:00am, and 70deg at 10:15am, and you know how far you travelled in that time, and in what direction, you can use your previous position as one of the points of the triangle, the known object as one point, and your current position as one point. It's called a running fix.

Sorry for delving into this tangent (a pun?) but the subject just kind of got me thinking again. If this followup has a point it's to confirm Roger's methodology.

Back to your regular scheduled programming, now in progress.




Dave

No trig needed, this is linear algebra. The two lines have the form y = m_Ax + b_A and y = m_Bx + b_B. The point where both are satisfied is the intersection you want.

Solving for x, we get x = (b_B - b_A)/(m_A - m_B). Similarly, y = (m_Bb_A - m_Ab_B) / (m_B - m_A).

That is with the numeric values

1. m_A = (D_y - A) / D_x
2. m_B = (C_y - B) / C_x
3. b_A = A
4. b_B = B

The other answers seem right, so I will just pedant the point a little bit :)

Can you assume that the solution of P is a single point? If not (for example, A=B=C=D=0.5), your solution might be a line. Your calculation may fail with a divide by zero.

Can you assume that the lines definitely do cross? If they don't, at best you will get an answer of (x>1). At worst, they will be parallel lines and you'll get some lovely division by zero error (depending how you calculate the answer).

Can you assume that both lines intersect the same two sides? If not, y=mx+c based calculations will fall apart somewhat with vertical lines, but then I don't think any of the answers given here will hold anyway.

All valid points, but for my application, all your preconditions are met.

---

Examine what is said, not who speaks.

"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
Timing (and a little luck) are everything!

Another gotcha is that the lines might not be parallel, but their intersection might fall outside the unit square. Beware :-) Haroldo

I had that already if you look closely ;o)

It was done in my editor and pasted:)

---

Examine what is said, not who speaks.

"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
Timing (and a little luck) are everything!

I will say, though, I do tend to make problems too hard myself. for instance, the US S.A.T. (that easy test was long long long ago) isn't supposed to require Calculus -- only basic Trig, but I used a few Integrals in random places just because. It's whatever tools that are sharpest that get used, I guess. My trig is kind of rusty. When I try to write OpenGL every now and then, I end up with some very weird physics :)

--FlyingMoose