RE: Fwd: Fwd: RE: rectangle intersection
- To: mathgroup at smc.vnet.net
- Subject: [mg36202] RE: [mg36162] Fwd: [mg36140] Fwd: [mg36124] RE: [mg36093] rectangle intersection
- From: "DrBob" <majort at cox-internet.com>
- Date: Mon, 26 Aug 2002 04:16:33 -0400 (EDT)
- Reply-to: <drbob at bigfoot.com>
- Sender: owner-wri-mathgroup at wolfram.com
Garry, No, you don't have to compute intersections, and yes, you can test vertices only. I haven't coded it yet, but the "LeftSide" idea seems like a good one. It is sufficient to test whether all vertices of one convex polygon are on the left (out) side of some side of the second polygon (both polygons in clockwise order). If that happens for any side of either polygon, the polygons don't intersect. In the "cross" example, some vertices are to the right for every side you try. Bobby Treat -----Original Message----- From: Garry Helzer [mailto:gah at math.umd.edu] To: mathgroup at smc.vnet.net Subject: [mg36202] [mg36162] Fwd: [mg36140] Fwd: [mg36124] RE: [mg36093] rectangle intersection As Daniel Lichtblau pointed out, the statement below about vertices is nonsense. Consider two overlapping rectangles arranged as a cross. You need to compute intersections and test them instead of vertices. Begin forwarded message: > From: Garry Helzer <gah at math.umd.edu> To: mathgroup at smc.vnet.net > Date: Fri Aug 23, 2002 12:25:13 AM US/Eastern > Subject: [mg36202] [mg36162] [mg36140] Fwd: [mg36124] RE: [mg36093] rectangle intersection > > 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 > >