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…

Accepted Answer

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

C++ procedure for determining whether two segments intersect

Solution

Problem