Given four points with known coordinates:
Writing the parametric equation for the line :
and the parametric equation for the line :
with and . Notice that if then we get the starting point of line and if then we get the ending point of line . Symmetrically, the same applies to , giving the start point of segment and , giving the end point of segment .
Equating the two equations for lines and , we obtain the system of linear equations:
We determine and from the first two equations:
Note that the denominator, call it :
is the same for both and .
Judging on cases, we can say that:
The vectors A
, B
, C
and D
are given in parametric form, for example:
vector A = <34.517483, 231.703461, 21.108919>; vector B = <34.517483, 222.014297, 21.108919>; vector C = <29.423143, 226.800842, 21.108919>; vector D = <38.186848, 226.800842, 21.108919>;
In order to determine whether the segments and intersect, one would call the function as:
if(wasSegmentIntersect(A, B, C, D) == TRUE) { llOwnerSay("Segments AB and CD intersect."); return; } llOwnerSay("Segments AB and CD do not intersect.");
wasSegmentIntersect
is defined as:
/////////////////////////////////////////////////////////////////////////// // Copyright (C) 2014 Wizardry and Steamworks - License: GNU GPLv3 // /////////////////////////////////////////////////////////////////////////// // determines whether the segment AB intersects the segment CD integer wasSegmentIntersect(vector A, vector B, vector C, vector D) { vector s1 = <B.x - A.x, B.y - A.y, B.z - A.z>; vector s2 = <D.x - C.x, D.y - C.y, D.y - C.z>; float d = (s1.x * s2.y -s2.x * s1.y); if(d == 0) return FALSE; float s = (s1.x * (A.y - C.y) - s1.y * (A.x - C.x)) / d; float t = (s2.x * (A.y - C.y) - s2.y * (A.x - C.x)) / d; // intersection at <A.x + (t * s1.x), A.y + (t * s1.y), A.z + (t * s1.z)>; return (integer)(s >= 0 && s <= 1 && t >= 0 && t <= 1 && A.z + t*(B.z - A.z) == C.z + s*(D.z - C.z)); }