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

Question

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;   
}

Lines or line segments cross? You mention both. You can define a line with just 2 points, or you can define the end points of a line segment with 2 points. — franji1, Sep 13 '12 at 23:52
Move The second if inside the first else. It won't change the result but it will be clearer. Also, to ease that people helps explain your algorithm. — Picarus, Sep 13 '12 at 23:53
The basic idea to calculate this is finding out if each segment intercepts the rectangle defined by the other segment. — Picarus, Sep 13 '12 at 23:59
Would it help if you had the whole code so that you could understand it in context with the entire program? — mkjo0617, Sep 14 '12 at 00:28

lhf · Answer 1 · 2012-09-14T00:07:13.610

3

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 .

edited Sep 14 '12 at 00:07

answered Sep 13 '12 at 23:57

lhf

70,581
9
108
149

score 2 · Accepted Answer · edited Sep 14 '12 at 00:03

2

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

edited Sep 14 '12 at 00:03

Jonathan Leffler

730,956
141
904
1,278

answered Sep 14 '12 at 00:01

David Robinow

36
1

I wondered about those too. The absolute value of `uA` is never negative; does 0 (or 0.0) count as an intersection? Would it mean that the segments touch? Similarly with the comparisons with 1.0? – Jonathan Leffler Sep 14 '12 at 00:04
I am still not getting any output. I am just so frustrated. I am a fairly novice program and this assignment is a bit over my head. – mkjo0617 Sep 14 '12 at 00:05

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

2 Answers2