I'm having some trouble understanding the ccw (counterclockwise) algorithm:
int ccw (Point P0, Point P1, Point P2) {
dx1 = P1.x - P0.x;
dx2 = P2.x - P0.x;
dy1 = P1.y - P0.y;
dy2 = P1.y - P0.y;
if (dy1 * dx2 > dy2 * dx1) return -1;
if (dx1 * dy2 > dy1 * dx2) return 1;
if ((dx1 * dx2 < 0) || (dy1 * dy2 < 0)) return 1;
if ((dx1 * dx1 + dy1 * dy1) < (dx2 * dx2 + dy2 * dy2)) return -1;
return 0;
}
This code it used to see if two lines intersect:
bool intersect (Vector2D l1, Vector2D l2) {
return (((ccw(l1.start, l1.end, l2.start) * ccw(l1.start, l1.end, l2.end)) <= 0)
&& ((ccw(l2.start, l2.end, l1.start) * ccw(l2.start, l2.end, l1.start)) <= 0))
}
I can understand the code inside the intersect function, but I don't really understand the code inside the ccw function.
Why it isn't used the cross product?
The code inside ccw function is written in a rather ad-hoc way, but it does use what is sometimes very informally referred as 2D-version of cross product. For two vectors (dx1, dy1) and (dx2, dy2) that product is defined as a scalar value equal to
CP = dx1 * dy2 - dx2 * dy1;
(In the formally correct terminology, CP is actually the signed magnitude of the classic 3D cross product of vectors (dx1, dy1, 0) and (dx2, dy2, 0).) Obvoisly, that value is simply a scalar (dot) product, in which one of the vectors was replaced by its perpendicular.
If the value of CP is positive, then the shortest radial sweep from (dx1, dy1) to (dx2, dy2) goes counter-clockwise. Negative CP means clockwise sweep. Zero in CP indicates collinear vectors. (All this assumes that Y axis is directed up and X axis is directed to the right.)
Obviously, CP > 0 condition is equivalent to dx1 * dy2 > dx2 * dy1 condition and CP < 0 is equivalent to dx1 * dy2 < dx2 * dy1. That's exactly what your ccw function checks by the very first two ifs.
The remaining ifs are dealing with the collinear situations.
If the vectors are pointing in opposite directions (which is detected by the third if), i.e. when P0 lies between P1 and P2, the function always returns 1, indicating counter-clockwise ordering. Well, I guess that is just a convention assumed by the code author.
Finally, if two vectors point in the same direction, i.e. when P0 lies outside the P1-P2 segment, the decision is based in the vector lengths (the fourth if). If P1 is closer than P2 to P0, a clockwise ordering is reported. Otherwise, if P2 is closer, a counter-clockwise ordering is reported. This is also just a convention assumed by the code author.
And, judging by the rest of the code, it is not about intersection of two lines. It is about intersection of two segments.