Re: rectangle intersection
- To: mathgroup at smc.vnet.net
- Subject: [mg36127] Re: [mg36093] rectangle intersection
- From: Andrzej Kozlowski <andrzej at lineone.net>
- Date: Thu, 22 Aug 2002 04:33:05 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Here is one quick attempt. I have no time to investigate it or write
careful code or test its performance.
We make use of the "Experimental" context.
In[1]:=
<<Experimental`
First we define an auxiliary function funct:
In[2]:=
funct[l_]:=
Module[{f},f[{a_,b_},{c_,d_}]:=(d-b) (x-c)+(a-c) (y-d);
Thread[(f@@@(Partition[Rationalize[l],2,1]))>=0]]
Here is the function that checks if two rectangles represented by lists
of points in anti-clocwise order l1, l2 are disjoint:
In[3]:=
disjoint[l1_,l2_]:=
CylindricalAlgebraicDecomposition[Join[funct[l1],funct[l2]],{x,y}]===False
let's take an example:
l1 = {{0, 1}, {1, 1}, {1, 0}, {0, 0}, {0, 1}};
let's shift it so as to create an intersecting rectangle:
In[4]:=
l1={{0,1},{1,1},{1,0},{0,0},{0,1}};
let's shift it so that it still intersects l1:
In[5]:=
l2=l1/.{x_?NumericQ,y_?NumericQ}->{x+0.8,y}
Out[5]=
{{0.8,1},{1.8,1},{1.8,0},{0.8,0},{0.8,1}}
you can see that the rectangles intersect:
In[6]:=
Show[Graphics[{Line[l1],Line[l2]}],PlotRange->All]
our test confirms this:
In[7]:=
disjoint[l1,l2]
Out[7]=
False
Now shift the rectangle so it no longer intersects the original one:
In[8]:=
l2=l1/.{x_?NumericQ,y_?NumericQ}->{x+1.1,y}
Out[8]=
{{1.1,1},{2.1,1},{2.1,0},{1.1,0},{1.1,1}}
checking graphically:
In[9]:=
Show[Graphics[{Line[l1],Line[l2]}],PlotRange->All]
using our test:
In[10]:=
disjoint[l1,l2]
Out[10]=
True
I have not tested this function carefully. If you find it useful you
should re-write as a single function it and in particular localize the
variables x and y.
Andrzej Kozlowski
Toyama International University
JAPAN
On Wednesday, August 21, 2002, at 10:51 AM, Frank Brand wrote:
> 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
>
>
>
>