Re: rectangle intersection
- To: mathgroup at smc.vnet.net
- Subject: [mg36193] Re: rectangle intersection
- From: "Jonathan Rockmann" <MTheory at msn.com>
- Date: Mon, 26 Aug 2002 04:16:17 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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: [mg36193] [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: [mg36193] [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