MathGroup Archive 2002

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

Search the Archive

RE: rectangle intersection

  • To: mathgroup at smc.vnet.net
  • Subject: [mg36124] RE: [mg36093] rectangle intersection
  • From: "David Park" <djmp at earthlink.net>
  • Date: Thu, 22 Aug 2002 04:33:02 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

Frank,

Perhaps the best method is to use the Developer`InequalityInstance routine
that comes with Version 4.1.

I will represent a rectangle by the position of the lower left hand corner,
the angle, theta, that the base makes with the x-axis and the lengths of the
base and side of the rectangle. If base and side are vectors that lie along
the base and side then a point in the rectangle is given by

{x, y} == corner + u base + v side where
0 < u < 1 and 0 < v < 1.

We can then solve for u and v in terms of x and y. For two rectangles, x and
y must be the same and we can write inequalties for u[1], v[1], u[2] and
v[2] in terms of x and y. InequalityInstance will then either find a point
that satisfies the inequalities or return {} if there are no points.

Here is a routine that returns True if the rectangles intersect and False if
they don't. The information for each rectangle is entered as:

{{x0,y0}, theta, {baselength, sidelength}}

RectangleIntersection[r1_, r2_] :=
  Module[{corner, u, v, base, side, lbase, lside, \[Theta], x, y, eqns,
      sols},
    {corner[1], \[Theta][1], {lbase[1], lside[1]}} = r1;
    {corner[2], \[Theta][2], {lbase[2], lside[2]}} = r2;
    base[1] = lbase[1]{Cos[\[Theta][1]], Sin[\[Theta][1]]};
    side[1] = lside[1]{-Sin[\[Theta][1]], Cos[\[Theta][1]]};
    base[2] = lbase[2]{Cos[\[Theta][2]], Sin[\[Theta][2]]};
    side[2] = lside[2]{-Sin[\[Theta][2]], Cos[\[Theta][2]]};
    eqns[1] = {x, y} == corner[1] + u[1]base[1] + v[1]side[1] // Thread;
    eqns[2] = {x, y} == corner[2] + u[2]base[2] + v[2]side[2] // Thread;
    sols[1] = Solve[eqns[1], {u[1], v[1]}];
    sols[2] = Solve[eqns[2], {u[2], v[2]}];
    eqns[3] =
      Flatten[{0 < u[1] < 1, 0 < v[1] < 1, 0 < u[2] < 1, 0 < v[2] < 1} /.
            sols[1] /. sols[2]];
    Developer`InequalityInstance[eqns[3], {x, y}] =!= {}
    ]

Here is a routine that draws the two rectangles:

PlotRectangles[r1_, r2_] :=
  Module[{corner, base, side, \[Theta], lbase, lside},
    {corner[1], \[Theta][1], {lbase[1], lside[1]}} = r1;
    {corner[2], \[Theta][2], {lbase[2], lside[2]}} = r2;
    base[1] = lbase[1]{Cos[\[Theta][1]], Sin[\[Theta][1]]};
    side[1] = lside[1]{-Sin[\[Theta][1]], Cos[\[Theta][1]]};
    base[2] = lbase[2]{Cos[\[Theta][2]], Sin[\[Theta][2]]};
    side[2] = lside[2]{-Sin[\[Theta][2]], Cos[\[Theta][2]]};
    Show[Graphics[
        {Line[{corner[1], corner[1] + base[1], corner[1] + base[1] +
side[1],
              corner[1] + side[1], corner[1]}],
          RGBColor[0, 0, 1],
          Line[{corner[2], corner[2] + base[2], corner[2] + base[2] +
side[2],
               corner[2] + side[2], corner[2]}]}], AspectRatio -> Automatic,
      PlotRange -> All]
    ]

Here are some test cases.

rectangle[1] = {{0, 0}, 0°, {1, 1}};
rectangle[2] = {{1/2, 1/2}, 0°, {1, 1}};
PlotRectangles[rectangle[1], rectangle[2]];
RectangleIntersection[rectangle[1], rectangle[2]]
True

rectangle[1] = {{0, 0}, 0°, {1, 1}};
rectangle[2] = {{1.1, 1.1}, 0°, {1, 1}};
PlotRectangles[rectangle[1], rectangle[2]];
RectangleIntersection[rectangle[1], rectangle[2]]
False

rectangle[1] = {{0, 0}, 0°, {1, 1}};
rectangle[2] = {{1, 1}0.9, 45°, {2, 1}};
PlotRectangles[rectangle[1], rectangle[2]];
RectangleIntersection[rectangle[1], rectangle[2]]
True

For timing on an 800 Mhz machine..

rectangle[1] = {{0, 0}, 0°, {1, 1}};
rectangle[2] = {{1, 1}0.9, 45°, {2, 1}};
Do[RectangleIntersection[rectangle[1], rectangle[2]], {100}] // Timing
{0.66 Second, Null}

I don't know if that is fast enough.

David Park
djmp at earthlink.net
http://home.earthlink.net/~djmp/

From: Frank Brand [mailto:frank.brand at t-online.de]
To: mathgroup at smc.vnet.net

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





  • Prev by Date: Re: LetterQ and DigitQ question
  • Next by Date: Mathematica 4.2: Problem with online help.
  • Previous by thread: Re: rectangle intersection
  • Next by thread: Re: rectangle intersection