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