Must be a good book then if he also tries to avoid divisions.
As you would know, the cross-product is a 3D only thing. When using this algorithm in 3D it detemines not necessarily that the lines intersect, but rather finds the points of the closest approach of either line to the other.
When doing this in strictly 2D, the equivalent thing is called the "perp dot product". It just so happens that the code already shown actually does use the perp dot product. So in all liklyhood, it is the same method.
Further early out tests can bone done by noticing that the calculations for tn and td are not required until it is known that sn is between 0 and sd. Even then, until you know that sn >= 0, you don't need to calculate sd, and similar for td.
This gives rise to:
Code:
char get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y,
float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
float s1_x, s1_y, s2_x, s2_y, sn, tn, sd, td, t;
s1_x = p1_x - p0_x; s1_y = p1_y - p0_y;
s2_x = p3_x - p2_x; s2_y = p3_y - p2_y;
sn = -s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y);
if (sn >= 0)
{
sd = -s2_x * s1_y + s1_x * s2_y;
if (sn <= sd)
{
tn = s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x);
if (tn >= 0)
{
td = -s2_x * s1_y + s1_x * s2_y;
if (tn <= td)
{
// Collision detected
t = tn / td;
if (i_x != NULL)
*i_x = p0_x + (tn * s1_x);
if (i_y != NULL)
*i_y = p0_y + (tn * s1_y);
return 1;
}
}
}
}
return 0; // No collision
}
Which if you modify from using deeply-nested statement to using early returns, becomes this:
Code:
char get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y,
float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
float s1_x, s1_y, s2_x, s2_y, sn, tn, sd, td, t;
s1_x = p1_x - p0_x; s1_y = p1_y - p0_y;
s2_x = p3_x - p2_x; s2_y = p3_y - p2_y;
sn = -s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y);
if (sn < 0)
return 0; // No collision
sd = -s2_x * s1_y + s1_x * s2_y;
if (sn > sd)
return 0; // No collision
tn = s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x);
if (tn < 0)
return 0; // No collision
td = -s2_x * s1_y + s1_x * s2_y;
if (tn > td)
return 0; // No collision
// Collision detected
t = tn / td;
if (i_x != NULL)
*i_x = p0_x + (tn * s1_x);
if (i_y != NULL)
*i_y = p0_y + (tn * s1_y);
return 1;
}
Look much closer to your pseudocode yet?
Hmm, wasn't that fun