line intersection (again)

This is a discussion on line intersection (again) within the C Programming forums, part of the General Programming Boards category; Hi all, Hopefully someone can point me in the right direction. I posted sometime ago ago querying code for the ...

  1. #1
    Registered User
    Join Date
    May 2010
    Posts
    29

    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 (Check if two line segments intersect). 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
    }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    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;
    }
    Last edited by iMalc; 04-01-2013 at 10:52 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    May 2010
    Posts
    29
    Thanks iMalc

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Line segment intersection code issues.
    By ~Kyo~ in forum Game Programming
    Replies: 6
    Last Post: 03-19-2012, 01:28 AM
  2. Replies: 3
    Last Post: 07-08-2009, 10:13 AM
  3. Replies: 2
    Last Post: 05-21-2008, 10:40 PM
  4. Triangle and Line Segment Intersection
    By hebali in forum C Programming
    Replies: 40
    Last Post: 04-09-2008, 10:31 AM
  5. Line Intersection
    By Highland Laddie in forum C++ Programming
    Replies: 13
    Last Post: 10-13-2005, 04:14 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21