Fwd: Fwd: RE: rectangle intersection
- To: mathgroup at smc.vnet.net
- Subject: [mg36162] Fwd: [mg36140] Fwd: [mg36124] RE: [mg36093] rectangle intersection
- From: Garry Helzer <gah at math.umd.edu>
- Date: Fri, 23 Aug 2002 21:34:54 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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: [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
>
>