I had some talk on this topic lately and thought it might come handy in to put it here. So, when two line segments in euclidean plane intersects each other? Definition: the two given line segments AB and CD intersect each other if points A and B are from the different sides of the line determined with CD as well as the points C and D are from the different sides of the line determined with AB. Or if one of points A and B belong to CD and other not; The same for points C and D and AB. Both C and D may both belong to AB (or A and B belong CD) too.
In example, two points in euclidean plane, A and B, are from different sides of the line determined with CD, if the following works:
sgn((CD x CA)*(0,0,1)) != sgn((CD x CB)*(0,0,1))
If all the signums are nulls, it is the special case that both segments lie on the same line. In that case the distance of two most distant points on the line must be less or equal with summ of lengths of segments. Otherwise AB and CD do not intersect.
So now I will give an simple and non-optimizes piece of code that represents on solution of this problem. Piece of code is wrote in pure C and not optimized for fastest working, but for best showing what is going on in there. As well, for those who aren't quite sure about the concept of structures or classes, arguments are eight real numbers which are coordinates of four points. Function returns 0 when there is no intersection and 1 when there is.
There will be written four more helping functions. The signum, taking an real number and returning an integer. Function that quadriple value, i.e. f(x) = x*x, taking one real number and returning another. Function that calculates the third coordinate of vector porduct of two given vectors in plane, taking four real values and returning one. Function that calculates distance between two points in euclidean plane.
 | | |
| Code: int signum(float x) { if(x > 0) return 1; if(x < 0) return -1; return 0; } float qua(float x) { return x*x; } float vectorproductz(float px,float py,float qx,float qy) { return px*qy - py*qx; } float distance(float px,float py,float qx,float qy) { return (float) sqrt(qua(qx-px)+qua(qy-py)); } int segmeninplanetintersect( float ax,float ay, float bx,float by, float cx,float cy, float dx,float dy ) { // vector AB float abx = bx - ax, aby = by - ay; // vector CD float cdx = dx - cx, cdy = dy - cy; // sgn (AB x AC) * (0,0,1) int abac = signum( vectorproductz(abx,aby,cx-ax,cy-ay) ); // sgn (AB x AD) * (0,0,1) int abad = signum( vectorproductz(abx,aby,dx-ax,dy-ay) ); // sgn (CD x CA) * (0,0,1) int cdca = signum( vectorproductz(cdx,cdy,ax-cx,ay-cy) ); // sgn (CD x CB) * (0,0,1) int cdcb = signum( vectorproductz(cdx,cdy,bx-cx,by-cy) ); // buffers for the maximal and current distance float distmax,dist; if(abac == 0 && abad == 0 && cdca == 0 && cdcb == 0) { distmax = distance(ax,ay,cx,cy); dist = distance(ax,ay,dx,dy); if(dist > distmax) distmax = dist; dist = distance(bx,by,cx,cy); if(dist > distmax) distmax = dist; dist = distance(bx,by,dx,dy); if(dist > distmax) distmax = dist; return distance(0,0,abx,aby) + distance(0,0,cdx,cdy) >= distmax; } return abac != abad && cdca != cdcb; } | |
| | |
Note: the signum can be written in few more ways.
| | |
| Code: int signum(float x) { return x<0?-1:x>0?1:0; } | |
| | |
| | |
| Code: int signum(float x) { return x<0?-1:!!x; } | |
| | |
The first one is universal model for all the programming languages that root from C. The second is C/C++ specific.
The condition abac == 0 && abad == 0 && cdca == 0 && cdcb == 0 in C/C++ can be writen in the following way too:
| | |
| Code: !(abac|abad|cdca|cdcb) | |
| | |