Segment Intersection
Do two segments have at least one point in common?
segm_intersect(s1, s2)
s1, s2 |
Two segments, represented by their end points; i.e.,
|
First compares the ‘bounding boxes’, and if those intersect looks at whether the other end points lie on different sides of each segment.
Logical, TRUE if these segments intersect.
Should be written without reference to the cross function.
Should also return the intersection point, see the example.
Cormen, Th. H., Ch. E. Leiserson, and R. L. Rivest (2009). Introduction to Algorithms. Third Edition, The MIT Press, Cambridge, MA.
## Not run:
plot(c(0, 1), c(0, 1), type="n",
xlab = "", ylab = "", main = "Segment Intersection")
grid()
for (i in 1:20) {
s1 <- matrix(runif(4), 2, 2)
s2 <- matrix(runif(4), 2, 2)
if (segm_intersect(s1, s2)) {
clr <- "red"
p1 <- s1[1, ]; p2 <- s1[2, ]; p3 <- s2[1, ]; p4 <- s2[2, ]
A <- cbind(p2 - p1, p4 - p3)
b <- (p3 - p1)
a <- solve(A, b)
points((p1 + a[1]*(p2-p1))[1], (p1 + a[1]*(p2-p1))[2], pch = 19, col = "blue")
} else
clr <- "darkred"
lines(s1[,1], s1[, 2], col = clr)
lines(s2[,1], s2[, 2], col = clr)
}
## End(Not run)Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.