Fwd: RE: rectangle intersection
- To: mathgroup at smc.vnet.net
- Subject: [mg36140] Fwd: [mg36124] RE: [mg36093] rectangle intersection
- From: Garry Helzer <gah at math.umd.edu>
- Date: Fri, 23 Aug 2002 00:25:13 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Begin forwarded message:
Dear colleagues,
any hints on how to implement a very fast routine in Mathematica for
testing if two rectangles have an intersection area?
Thanks in advance
Frank Brand
Here is one approach.
Given three points {x1,y1},{x2,y2},{x3,y3}, switch to homogenous
coordinates a={1,x1,y1}, b={1,x2,y2}, c={1,x3,y3}. Then
Sign[Det[{a,b,c}]] is +1 if and only if the point a lies on your left as
you walk along the line though b and c in the direction from b to c.
( If the result is zero, then a lies on the line.)
The value of the determinant is x2y3-x3y2-x1y3+x3y1+x1y2-x2y1, and the
speed of the algorithm depends essentially on how fast this quantity can
be computed. Suppose we write a function LeftSide[a,{b,c}] that computes
the sign of the determinant.
Now let {p1,p2, . . ., pn} be a list of vertices (pi={xi,yi}) of a
convex polygon traced counterclockwise. Then a lies within or on the
boundary of the polygon if and only if none of the numbers
LeftSide[a,{pi,p(i+1)}] are -1. That is, if -1 does not appear in the
list LeftSide[a,#]&/@Partition[{p1,p2,. . .,pn,p1},2,1].
Now use the fact that if two convex polynomials overlap, then some
vertex of one of them must lie inside or on the boundary of the other.
If an overlap of positive area is required, then the check is that only
+1 appears--not that -1 does not appear.
For two rectangles ( or parallelograms) this approach requires the
evaluation of 16 determinants, so it may be a bit expensive. If the
points have rational coordinates, then (positive) denominators may be
cleared in the homogeneous coordinates and the computations can be done
in integer arithmetic, at the cost of at least three more
multiplications per determinant.
Garry Helzer
Department of Mathematics
University of Maryland
College Park, MD 20742
301-405-5176
gah at math.umd.edu