Hello,

I am trying to calculate the intersection point of 2 lines in a plane. The equation given as 21.4.5 on page 1117 isn't giving me the correct result.

for example the following 2 segments really do intersect but the calculation (as I've implemented it, anyway!) implies that they don't :

x0 -3652495.766 y0 4004186.837
x1 -3652495.737 y1 4004179.856
a0 -3652500.429 b0 4004184.409
a1 -3652492.380 b1 4004184.330


eqn 21.4.5 is
s = ((x0-y0)*(a1-x1) - (x1-y1)*(a0-x0)) / denom
t = ((a0-x0)*(b1-a1) - (a1-x1)*(b0-a0)) / denom
denom = (b0-a0)*(x1-y1) - (b1-a1)*(x0-y0)
where s is the fractional distance along ab
and t is the fractional distance along xy.
Both must be between 0 and 1 for an intersection to occur.

I've implemented this in excel and c++ and got the same (wrong) results either way:
denom = -8563218
s=7.1714
t=7.1714

I found another derivation of the same equation here: Marina Gavrilova "Reliable line segment intersection testing" (http://www.cpsc.ucalgary.ca/~marina/papers/Segment_intersection.ps.).

Of course she uses a different nomenclature, but after simplification her equation comes to:
denom = (b0-b1)*(x0-x1)+(a1-a0) = 56.1953
S =- (ao*(b1-y1) + a1*(y1-b0) + x1*(b0-b1)) / denom = 0.645
T =( y1*(x0-a1) + b1*(x1-x0) +y0*(a1-x1)) / denom =0.419
, which is quite different and correctly determines that the line segments do in fact intersect.

In this case, the scaling factor to determine the actual intersection points are actually (1-s) and (1-t).

Can anyone explain the difference to me?

Thanks

Marc Pelletier

Dear Marc,

I think you have misunderstood the notation in NR. The point a has coordinates (a0,a1). You have assigned it the coordinates (a0,b0). Similarly for the other points: b should be (b0,b1), not (a1,b1) etc.

Best,
Saul Teukolsky

Hello Saul,

Thanks for that. One of those situations where a fresh set of eyes is required.

Cheers,

Marc