CODEWITHSUNDEEP
c++mathlineintersectionalgebra
mkjo0617
mkjo0617

Reputation: 33

What's wrong with this code to determine if two lines segments intersect?

I can't for the life of me figure out how to get it to return true if the segments cross. Any help would be greatly appreciated.

bool doCross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4)
{
    bool cross = true;
    double denom, uA, uB;

    denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);

    if(denom == 0)
    {
        cross = false;
    }
    else
    {
        uA = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3) / denom;
        uB = (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3) / denom;
    }
    if (abs(0 < uA) && abs(uA < 1) && abs(0 < uB) && abs(uB < 1))
    {
        cross = true;
    }
    else
    {
        cross = false;
    }       
    return cross;   
}

Upvotes: 0

Views: 986

Answers (2)

lhf
lhf

Reputation: 72412

Two line segments AB and CD cross iff A and B are on different sides of CD and vice-versa. To test whether a point X is to the left of an oriented segment PQ, use the ccw primitive. For some code, see Line segment intersection in http://algs4.cs.princeton.edu/91primitives/ and some slides at http://www.cs.princeton.edu/~rs/AlgsDS07/16Geometric.pdf .

Upvotes: 3

David Robinow
David Robinow

Reputation: 36

you said:

uA = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3) / denom;
uB = (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3) / denom;

I think you want:

uA = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denom;
uB = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denom;

you said:

if (abs(0 < uA) && abs(uA < 1) && abs(0 < uB) && abs(uB < 1))

you're taking the absolute value of comparisons, which makes no sense at all. Did you want:

if ((0 < abs(uA)) && (abs(uA) < 1) && (0 < abs(uB)) && abs(uB) < 1))

It's bad form, though not necessarily an error, to use integer constants when comparing floats/doubles

Upvotes: 2

Related Questions