## [REBOL] Re: Detecting Intersection of Line Segments

### From: joel::neely::fedex::com at: 2-Apr-2003 6:57

Hi, Oldes, Yes. Below. rebOldes wrote:> i'm still alive but too busy. >I can relate.> I just Want to ask you if someone don't have some algorithm > for detecting intersection of line segments in Rebol. >1) Represent each line in projective coordinates (AKA homogeneous coordinates), using appropriate values for a, b, and c in the equation: ax + by + c = 0 If you have the lines in some other form, this will take a tiny bit of algebra. E.g., if you have slope-intercept form for lines such as x = y and y = 1/2 x + 1 you convert them to x - y + 0 = 0 and 1/2 x - 1 + 1 = 0 Take the coefficients of the above equation form (a, b, c) as the projective coordinates of each line. 2) For two lines (a, b, c) and (p, q, r), compute the following values: (b*r - c*q, c*p - a*r, a*q - b*p) to obtain the projective coordinates of their intersection. (See footnotes at end. Please.) 3) If the third value a*q - b*p is zero, the lines are parallel. Otherwise, divide that third value into the other two, and the results will be the "plain" (Euclidean plane, that is ;-) coordinates of the intersection. To illustrate with the two lines given above, (a, b, c) = (1, -1, 0) (p, q, r) = (1/2, -1, 1) therefore, b*r - c*q = -1*1 - 0*-1 = -1 - 0 = -1 c*p - a*r = 0*1/2 - 1*1 = 0 - 1 = -1 a*q - b*p = 1*-1 - -1*1/2 = -1 - -1/2 = -1/2 and, as the last expression is non-zero, this means that the two lines intersect at (2,2). Therefore, we have interjoin: func [line1 [block!] line2 [block!]] [ reduce [ (line1/2 * line2/3) - (line1/3 * line2/2) (line1/3 * line2/1) - (line1/1 * line2/3) (line1/1 * line2/2) - (line1/2 * line2/1) ] ] intersect-point: func [line1 [block!] line2 [block!] /local p] [ either zero? third p: interjoin line1 line2 [ print "*** parallel lines don't intersect in Euclid!" ][ reduce [p/1 / p/3 p/2 / p/3] ] ] which behave as>> intersect-point [1 -1 0] [.5 -1 1]== [2 2] FOOTNOTE 0: The sharp-eyed reader will have noticed that we're actually just computing three determinants, which can be remembered by this little typographic trick: a b c a b p q r p q ---- ---- ---- leading to the resulting triple of values, |b c| |c a| |a b| ( | | , | | , | | ) |q r| |r p| |p q| or, in plain algebra, (b*r - c*q, c*p - a*r, a*p - b*p) FOOTNOTE 1: The lovely thing about projective coordinates is that points and lines are dual concepts. Just as a line is a collection of points that lie on it, a point is a collection of lines that pass through it. Given two distinct lines, they have one point in common; given two points, they have one line in common. If a line passes through a point, then that point lies on that line. To apply this duality, recall that the formula above computes the coordinates of the (unique) point that lies on two distinct lines. THE SAME FORMULA COMPUTES THE COORDINATES OF THE (UNIQUE) LINE THAT JOINS TWO DISTINCT POINTS! To illustrate, we can represent the points (0, 1) and (2, 0) in projective/homogeneous coordinates as (0, 1, 1) and (2, 0, 1) (or any other triple proportional to the above!) and then determine the line containing both of them by applying the formula above: 0 1 1 0 1 x x x 2 0 1 2 0 ----- ----- ----- 1 2 -2 which tells us that the line is represented by the equation: x + 2y - 2 = 0 or, in slope-intercept form: y = -1/2 x + 1 Now you know the reason for the name INTERJOIN , which lets us also define joining-line: func [pt1 [block!] pt2 [block!]] [ interjoin join pt1 1 join pt2 1 ] which behave as>> joining-line [0 1] [2 0]== [1 2 -2] This leaves me feeling that INTERJOIN is a highly practical little function, even if it *is* based on theory! ;-) -jn- -- Polonius: ... What do you read, my lord? Hamlet: Words, words, words. _Hamlet_, Act II, Scene 2