line intersection (again)

Hi all,

Hopefully someone can point me in the right direction. I posted sometime ago ago querying code for the intersection of a line (http://cboard.cprogramming.com/c-pro...intersect.html). I am using the solution proposed by iMalc and repeated again below. The problem is it only detects an intersection sometimes (so worked in my initial debugs).

For example, I now have a line with points (958.8677, 572.6056)(823.539, 541.3208) and a second line (850.84, 539.98)(911.33, 563.75). The algorithm is not detecting the line intersection though I've plotted both lines in excel to double check and they do intersect (its late, im tired and apologise if I'm doing something blatantly stupid).

I am very stuck with this so help as to how to modify the code below to take the above case into account would be very much appreciated.

Thanks in advance.

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);
    sd = -s2_x * s1_y + s1_x * s2_y;
    tn =  s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x);
    td = -s2_x * s1_y + s1_x * s2_y;
 
    if (sn >= 0 && sn <= sd && tn >= 0 && 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
}

---

From post number 8 on the previous thread. I fixed a problem and applied further early-out optimisations, but in any case I've failed to account for the fact that the divide had been cancelling out two negatives, when doing the original optimisation.
The fix:

Code:

---

int 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 s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t;
    s10_x = p1_x - p0_x;
    s10_y = p1_y - p0_y;
    s32_x = p3_x - p2_x;
    s32_y = p3_y - p2_y;

    denom = s10_x * s32_y - s32_x * s10_y;
    if (denom == 0)
        return 0; // Collinear
    bool denomPositive = denom > 0;

    s02_x = p0_x - p2_x;
    s02_y = p0_y - p2_y;
    s_numer = s10_x * s02_y - s10_y * s02_x;
    if ((s_numer < 0) == denomPositive)
        return 0; // No collision

    t_numer = s32_x * s02_y - s32_y * s02_x;
    if ((t_numer < 0) == denomPositive)
        return 0; // No collision

    if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive))
        return 0; // No collision
    // Collision detected
    t = t_numer / denom;
    if (i_x != NULL)
        *i_x = p0_x + (t * s10_x);
    if (i_y != NULL)
        *i_y = p0_y + (t * s10_y);

    return 1;
}

---

Thanks iMalc