Thread: 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;


}

> 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.

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.

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.

You mean to the webmaster at cprogramming.com? Do you want all my code or just the exe and supporting files?

No, the author of the web page you copy/pasted the code from!

There's a link at the bottom of THAT page.

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.