Line segment intersection code issues.

This is a discussion on Line segment intersection code issues. within the Game Programming forums, part of the General Programming Boards category; So I have tried two methods that should both work with line segments to determine if they are intersecting. The ...

  1. #1
    Registered User ~Kyo~'s Avatar
    Join Date
    Jun 2004
    Posts
    320

    Line segment intersection code issues.

    So I have tried two methods that should both work with line segments to determine if they are intersecting. The problem is on occasion I get a random false positive, or false negatives.

    The commented code was my first attempt the rest of the code was my second attempt.

    Found the logic at these sites:

    homework - How do you detect where two line segments intersect? - Stack Overflow

    Intersection point of two lines

    Code:
    bool C_Line::Lines_Intersect(C_Line l)
    {
        /*
        C_Point r = p1 - p;
    
        C_Point q = l.Get_Point1();
        C_Point s = l.Get_Point2() - l.Get_Point1();
    
        float RxS = r.Cross_Product(s);
        if(RxS == 0)return false;
        float QPxR = (q-p).Cross_Product(r);
        if(QPxR == 0)return false;
        float t = (q-p).Cross_Product(s)/RxS;
        float u = QPxR/RxS;
    
        if(t <= 1 && t >=0 && u <= 1 && u >= 0)return true;
        else return false;
        */
         C_Point A = p;
         C_Point B = p1;
         C_Point C = l.Get_Point1();
         C_Point D = l.Get_Point2();
    
         int x1 = A.Get_X();
         int x2 = B.Get_X();
         int x3 = C.Get_X();
         int x4 = D.Get_X();
    
         int y1 = A.Get_Y();
         int y2 = B.Get_Y();
         int y3 = C.Get_Y();
         int y4 = D.Get_Y();
    
    
         float denom = ((y4 - y3)*(x2 - x1)) - ((x4 - x3)*(y2 - y1));
         if(denom == 0)return true;
         float ua = ((x4 - x3)*(y1 - y3) - (y4 - y3)*(x1 - x3)) / denom;
         float ub = ((x2 - x1)*(y1 - y3) - (y2 - y1)*(x1 - x3)) / denom;
    
         if(ua <= 1 && ua >= 0 && ub <= 1 && ub >= 0)return true;
         else return false;
    
    
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,832
    > The problem is on occasion I get a random false positive, or false negatives.
    All the time, or only on lines which are near vertical or horizontal?

    > float denom = ((y4 - y3)*(x2 - x1)) - ((x4 - x3)*(y2 - y1));
    > if(denom == 0)return true;
    All sorts of weirdness can come from lines very close to axis. You end up with a large term and a small term in each of the sub-expressions.
    Comparing a float with 0 is bad code. See many previous discussions about comparing floats with equality.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User ~Kyo~'s Avatar
    Join Date
    Jun 2004
    Posts
    320
    It is a little hard to determine, but yes when the mob is directly below the player it blinks out and eventually blinks back in.
    I loose the mob under me and in quadrant 1 usually, like I said it seems odd just tried another bit of code from here Line-Line Intersection Method With C Code Sample again it did not work this problem is starting to really annoy me.


    this is a link to the exe:
    https://ws.onehub.com/files/twjzc9qe

    I guess I should give you the controls too right?

    WASD to move
    left mouse to shoot
    R to reload
    M to spawn a monster offset 100x100 from the player.
    Last edited by ~Kyo~; 03-19-2012 at 01:24 AM.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,832
    There's a "send me an email" link at the bottom of that page - try it.

    Just because you found some free code on the web doesn't mean it's been thoroughly tested against all edge cases.

    Yes it may be a mathematically correct implementation, but that doesn't mean it's computationally correct on real machines with floating point arithmetic with a finite precision.

    1E100 * 1E-100 may be 1 mathematically, but if you try and compute it using floating point numbers, you're going to get a different answer.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User ~Kyo~'s Avatar
    Join Date
    Jun 2004
    Posts
    320
    You mean to the webmaster at cprogramming.com? Do you want all my code or just the exe and supporting files?

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,832
    No, the author of the web page you copy/pasted the code from!

    There's a link at the bottom of THAT page.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    Registered User ~Kyo~'s Avatar
    Join Date
    Jun 2004
    Posts
    320
    Salem, do note I never straight copy and paste code. I thought it looked cleaner by doing those assignments instead of having a bunch of class function calls and ending up with 500 char lines of code.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 07-08-2009, 11:13 AM
  2. Replies: 2
    Last Post: 05-21-2008, 11:40 PM
  3. Triangle and Line Segment Intersection
    By hebali in forum C Programming
    Replies: 40
    Last Post: 04-09-2008, 11:31 AM
  4. Replies: 7
    Last Post: 12-16-2006, 10:30 PM
  5. Line Intersection
    By Highland Laddie in forum C++ Programming
    Replies: 13
    Last Post: 10-13-2005, 05:14 PM

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