Mailing List Archive: 49091 messages

## [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.

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