MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

RE: Fwd: Fwd: RE: rectangle intersection

  • To: mathgroup at smc.vnet.net
  • Subject: [mg36199] RE: [mg36162] Fwd: [mg36140] Fwd: [mg36124] RE: [mg36093] rectangle intersection
  • From: "DrBob" <majort at cox-internet.com>
  • Date: Mon, 26 Aug 2002 04:16:28 -0400 (EDT)
  • Reply-to: <drbob at bigfoot.com>
  • Sender: owner-wri-mathgroup at wolfram.com

Garry,

Also note your solution requires rectangle points to be in clockwise
order (mine doesn't), but yours works for arbitrary convex polygons as
written.

Bobby

-----Original Message-----
From: DrBob [mailto:majort at cox-internet.com] 
To: mathgroup at smc.vnet.net
Subject: [mg36199] RE: [mg36162] Fwd: [mg36140] Fwd: [mg36124] RE: [mg36093]
rectangle intersection

Garry,

Here's a solution using your "LeftSide" concept; it works perfectly but
takes twice as much time as my solution.  Both solutions look at every
vertex of both rectangles, but mine uses two sides from each and yours
requires looking at all four sides of each rectangle.  I'd think yours
should be a trifle faster than this, though.  There may be efficiencies
I'm missing (in both solutions).

ClearAll[cis, rect, pickRect, extent, cannotIntersect, intersects,
daveRect]
cis[t_] := {Cos@t, Sin@t}
rect[{pt : {_, _}, angle_, {len1_, len2_}}] := Module[{pt2},
    {pt, pt2 =
 pt + len1 cis[angle],
   pt2 - len2 cis[angle - Pi/2], pt - len2 cis[angle - Pi/2]}]
daveRect := {{Random[], Random[]}, Random[] + Pi/2, {Random[],
Random[]}}
pickRect := rect@daveRect
extent[r1_, 
      r2_] := {Min@#, Max@#} & /@ ((Take[r1, 2] - r1[[{2,
3}]]).Transpose@r2)
cannotIntersect[{{min1_, max1_}, {min2_, 
      max2_}}] := max2 < min1 || min2 > max1
intersects[r1_, r2_] := Catch[
    If[cannotIntersect[#], Throw[False]] & /@
Flatten[Transpose[Outer[extent, \
{r1}, {r1, r2}, 1]~Join~Outer[extent, {r2}, {r2, r1}, 1], {1, 3, 2}],
1];
    Throw[True]]

ClearAll[leftSide,leftIntersects,sides]
sides[a_List]:=Partition[Join[a,{First@a}],2,1]
leftSide[{a_,b_},{{c_,d_},{e_,f_}}]:=-b c+a d+b e-d e-a f+c f>0
leftSide[a:{{_,_}..},b:{{_,_},{_,_}}]:=leftSide[#,b]&/@a
leftSide[a_List,b:{{{_,_},{_,_}}..}]:=leftSide[a,#]&/@b
leftIntersects[a_,b_]:=!Or@@(And@@#&/@leftSide[a,sides@b])&&!
      Or@@(And@@#&/@leftSide[b,sides@a])

davePairs={daveRect,daveRect}&/@Range[10000];
rectanglePairs=Map[Reverse@rect[#]&,davePairs,{2}];
Timing[right=intersects[Sequence@@#]&/@rectanglePairs;]
Timing[test=leftIntersects[Sequence@@#]&/@rectanglePairs;]
right\[Equal]test

{3.187999999999999*Second,   Null}
{6.765000000000001*Second,   Null}
True

Bobby Treat

-----Original Message-----
From: Garry Helzer [mailto:gah at math.umd.edu] 
To: mathgroup at smc.vnet.net
Subject: [mg36199] [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: [mg36199] [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
>
>








  • Prev by Date: RE: Fwd: Fwd: RE: rectangle intersection
  • Next by Date: Re: Generate all k-tuples
  • Previous by thread: RE: Fwd: Fwd: RE: rectangle intersection
  • Next by thread: Choose one solution in Mathematica