C++ procedure for determining whether two segments intersect

Question

I'm working a bit with computational geometry lately, and I am trying to find a way of checking whether two line segments intersect. I thought that I can use counterclockwise direction (CCW for short) to determine that. Here is my code so far:

struct point { double x, y };

double CCW(point a, point b, point c)
{ return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x); }

int intersect(point a, point b, point c, point d)
{ return (CCW(a,b,c)*CCW(a,b,d)<0 && CCW(c,d,b)*CCW(c,d,a)<0); }

The above code worked for the test cases I entered, and it's pretty readable and very easy to implement. But after searching on the web, I found an other way of solving the segment intersection problem. The code is similar to mine, but it has some more if statements that my implementation omits. Here is the code:

struct line { point s, e; };

int middle(int a, int b, int c) {
  int t;    
  if ( a > b ) {
    t = a;
    a = b;
    b = t;
  }
  if ( a <= c && c <= b ) return 1;
  return 0;
}

int intersect(line a, line b) {
  if ( ( CCW(a.s, a.e, b.s) * CCW(a.s, a.e, b.e) < 0 ) &&
     ( CCW(b.s, b.e, a.s) * CCW(b.s, b.e, a.e) < 0 ) ) return 1;

  if ( CCW(a.s, a.e, b.s) == 0 && middle(a.s.x, a.e.x, b.s.x) && middle(a.s.y, a.e.y, b.s.y) ) return 1;
  if ( CCW(a.s, a.e, b.e) == 0 && middle(a.s.x, a.e.x, b.e.x) && middle(a.s.y, a.e.y, b.e.y) ) return 1;
  if ( CCW(b.s, b.e, a.s) == 0 && middle(b.s.x, b.e.x, a.s.x) && middle(b.s.y, b.e.y, a.s.y) ) return 1;
  if ( CCW(b.s, b.e, a.e) == 0 && middle(b.s.x, b.e.x, a.e.x) && middle(b.s.y, b.e.y, a.e.y) ) return 1;

    return 0;
}

Could someone explain which is the difference between the two implementations, and which is safer to use? Thanks in advance.

Mede

Answer 1

The function that you found is also checking the case where the line segments lie within the same line. In that case, it becomes a one-dimensional problem of finding whether the two line segments overlap. Your code would return false in this case. Whether this is preferred or not depends on the application.

Example:

point a={1,0}, b={3,0}, c={2,0}, d={4,0};

intersect(a,b,c,d); // your function will return false, 
                    // but the one you found will return true

The function you found also looks at cases where the endpoint of one line-segment lies along the other line segment:

Example:

point a={1,0}, b={3,0}, c={2,0}, d={2,3};

intersect(a,b,c,d); // your function will return false, 
                    // but the one you found will return true

Ultramontanism