1. sorting points or rectangles
- Posted by tone.skoda at siol.net
Feb 20, 2002
This is a multi-part message in MIME format.
------=_NextPart_000_0015_01C1BA67.089AE010
charset="iso-8859-2"
does anybody have any idea how could i sort rectangles or points, same problem.
i need it sorted so that when i have a lot of rectangles, i can quickly get the
ones which are inside some given big
rectangle.
------=_NextPart_000_0015_01C1BA67.089AE010
charset="iso-8859-2"
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-2">
<META content="MSHTML 5.50.4522.1800" name=GENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=#ffffff>
<DIV><FONT face=Arial size=2>does anybody have any idea how could i sort
rectangles or points, same problem.</FONT></DIV>
<DIV><FONT face=Arial size=2>i need it sorted so that when i have a lot of
rectangles, i can quickly get the ones which are inside some given big
------=_NextPart_000_0015_01C1BA67.089AE010--
2. Re: sorting points or rectangles
- Posted by gwalters at sc.rr.com
Feb 20, 2002
This is a multi-part message in MIME format.
------=_NextPart_000_0084_01C1BA37.1DF44580
charset="Windows-1252"
if your rectangles are all horizontal then it is easy. you just use > and < on
x's and y's. if the rectangles are at randon
angles then you'll have to rotate the point in question to the coordinate system
of each of the rectangles one at a time
then use the > and < with x's and y's to see if it's inside. not difficult if
you know your trig, impossible if you don't.
george
----- Original Message -----
From: tone.skoda at siol.net
To: EUforum
Sent: Wednesday, February 20, 2002 5:33 PM
Subject: sorting points or rectangles
does anybody have any idea how could i sort rectangles or points, same
problem.
i need it sorted so that when i have a lot of rectangles, i can quickly get
the ones which are inside some given big
rectangle.
------=_NextPart_000_0084_01C1BA37.1DF44580
Content-Type: text/html;
charset="Windows-1252"
Content-Transfer-Encoding: 8bit
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META content="text/html; charset=windows-1252" http-equiv=Content-Type>
<META content="MSHTML 5.00.3105.105" name=GENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=#ffffff>
<DIV><FONT size=2>if your rectangles are all horizontal then it is easy. you
just use > and < on x's and y's. if the rectangles are at randon angles
then you'll have to rotate the point in question to the coordinate system of
each of the rectangles one at a time then use the > and < with x's and
y's to see if it's inside. not difficult if you know your trig, impossible if
you don't.</FONT></DIV>
<DIV> </DIV>
<DIV>george</DIV>
<BLOCKQUOTE
style="BORDER-LEFT: #000000 2px solid; MARGIN-LEFT: 5px; MARGIN-RIGHT: 0px;
PADDING-LEFT: 5px; PADDING-RIGHT: 0px">
<DIV style="FONT: 10pt arial">----- Original Message ----- </DIV>
<DIV
style="BACKGROUND: #e4e4e4; FONT: 10pt arial; font-color: black"><B>From:</B>
<A href="mailto:tone.skoda at siol.net"
title=tone.skoda at siol.net>tone.skoda at siol.net</A> </DIV>
<DIV style="FONT: 10pt arial"><B>To:</B> <A href="mailto:EUforum at
topica.com"
title=EUforum at topica.com>EUforum</A> </DIV>
<DIV style="FONT: 10pt arial"><B>Sent:</B> Wednesday, February 20, 2002 5:33
PM</DIV>
<DIV style="FONT: 10pt arial"><B>Subject:</B> sorting points or
rectangles</DIV>
<DIV><BR></DIV><PRE>============ The Euphoria Mailing List ============
</PRE>
<DIV><FONT face=Arial size=2>does anybody have any idea how could i sort
rectangles or points, same problem.</FONT></DIV>
<DIV><FONT face=Arial size=2>i need it sorted so that when i have a lot of
rectangles, i can quickly get the ones which are inside some given big
rectangle.</FONT></DIV><PRE>==^================================================================
This email was sent to: gwalters at sc.rr.com
EASY UNSUBSCRIBE click here: <A
href="http://topica.com/u/?b1dd66.b2QlpX">http://topica.com/u/?b1dd66.b2QlpX</A>
Or send an email to: EUforum-unsubscribe at topica.com
T O P I C A -- Register now to manage your mail!
<A
href="http://www.topica.com/partner/tag02/register">http://www.topica.com/partner/tag02/register</A>
------=_NextPart_000_0084_01C1BA37.1DF44580--
3. Re: sorting points or rectangles
Haven't tested it out, but in principle this seems reasonable,
IF THE AXES OF THE RECTANGLES ARE PARALLEL!:
-- for rectangles each defined by 4 corner points in this order:
-- left-upper xy, right-upper xy, right-lower xy, left-lower xy:
-- {{lux,luy}, {rux, ruy}, {rlx,rly},{llx,lly}}
function IsInside(sequence OuterRectangle, sequence PossibleInnerRectangle)
if OuterRectangle[1][1] < PossibleInnerRectangle[1][1] and -- left
upper x outside
OuterRectangle[1][2] < PossibleInnerRectangle[1][2] and -- left
upper y outside
OuterRectangle[3][1] > PossibleInnerRectangle[3][1] and -- right
lower x outside
OuterRectangle[3][2] > PossibleInnerRectangle[3][2] and -- right
lower y outside
then return 1 -- for true
else return 0 -- for false
end if
end function
Dan Moyer
----- Original Message -----
From: <tone.skoda at siol.net>
To: "EUforum" <EUforum at topica.com>
Sent: Wednesday, February 20, 2002 2:33 PM
Subject: sorting points or rectangles
does anybody have any idea how could i sort rectangles or points, same
problem.
i need it sorted so that when i have a lot of rectangles, i can quickly get
the ones which are inside some given big
rectangle.
4. Re: sorting points or rectangles
21/02/2002 9:33:43 AM, tone.skoda at siol.net wrote:
>
> does anybody have any idea how could i sort rectangles or points, same
> problem.
> i need it sorted so that when i have a lot of rectangles, i can quickly get
>
> the ones which are inside some given big rectangle.
>
>
Assuming that the rectangles are not rotated with respect to the screen, that
is, the edges are all
vertical and horizontal, and that the edges meet at 90 degrees you might like to
explore this
attempt. It examines two rectangles and returns one of four possiblities- the
two rectangles do not
overlap at any point, the first rectangle is completely inside the second, the
second rectangle is
completely in the first, or that they overlap.
global constant kNoOverlap = 0,
kOverlap = 1,
kAinB = 2,
kBinA = 3,
kLeft = 1,
kTop = 2,
kRight = 3,
kBottom = 4
global function RectHit(sequence RectA, sequence RectB)
-- The sequence has four elements:
-- 1 = Left edge coordinate
-- 2 = Top edge coordinate
-- 3 = Width
-- 4 = Height
-- Convert to right and bottom edges
RectA[kRight] += RectA[kLeft] - 1
RectA[kBottom] += RectA[kTop] - 1
RectB[kRight] += RectB[kLeft] - 1
RectB[kBottom] += RectB[kTop] - 1
if RectB[kTop] > RectA[kBottom] or
RectB[kBottom] < RectA[kTop] or
RectB[kLeft] > RectA[kRight] or
RectB[kRight] < RectA[kLeft] then
return kNoOverlap
end if
-- At this point, they either overlap or one is totally inside
-- the other.
if RectB[kTop] >= RectA[kTop] and
RectB[kBottom] <= RectA[kBottom] and
RectB[kLeft] >= RectA[kLeft] and
RectB[kRight] <= RectA[kRight] then
return kBinA
end if
if RectB[kTop] < RectA[kTop] and
RectB[kBottom] > RectA[kBottom] and
RectB[kLeft] < RectA[kLeft] and
RectB[kRight] > RectA[kRight] then
return kAinB
end if
-- At this point, neither is completely enclosed so they must overlap.
return kOverlap
end function
---------
cheers,
Derek
5. Re: sorting points or rectangles
CORRECTION:
oops. my previous post works only if, as Derek and George correctly stated,
the edges of the rectangles are all vertical and horizontal with respect to
the coordinate system (the screen). Do you need to handle conditions other
than that?
Dan Moyer
6. Re: sorting points or rectangles
- Posted by tone.skoda at siol.net
Feb 21, 2002
----- Original Message -----
From: "Dan Moyer" <DANIELMOYER at prodigy.net>
> ... if the edges of the rectangles are all vertical and horizontal with
respect to
> the coordinate system (the screen).
I don't understand this quite. Rectangles allways have two horizontal and
two vertical edges. If edges are not horizontal or vertical then that would
be paralelogram or whatever, no?
> Do you need to handle conditions other
> than that?
No. You all responded with functions how to find out if (and how) rectangle
is inside rectangle.
I have around 10.000 rectangles and I have to get all rectangles which have
at least one of their four points inside a big rectangle.
I want to be able to use binary search on sorted rectangles for speed.
If I do it like this it is too slow:
function get_rects_inside_rect (sequence rectangles, sequence big_rect)
sequence rects_inside
sequence rect
rects_inside = {}
for int i = 0 to length (rects) do
rect = rects [i]
if is_rect_partially_inside_rect (rect, big_rect) then
rects_inside = append (rects_inside, rect)
end if
end for
return rects_inside
end function
A little faster it would be if I woluld somehow sort them by their left-x,
or something similar. Unclear to me right now.
7. Re: sorting points or rectangles
- Posted by gwalters at sc.rr.com
Feb 21, 2002
a rectangle has opposite sides with equal lengths and are parallel and
perpendicular... not always vertical or horizontal. a trapezoid has 2 sides
parallel but not equal in length. a parallelogram has sides that parallel
but are not perpendicular.
there is no way to do a binary search here. if you're looking for a single
point of the four that is inside then you'll have to do the > and < on each
point of the rectangle and drop out the loop if you get a hit.
george
----- Original Message -----
From: <tone.skoda at siol.net>
To: "EUforum" <EUforum at topica.com>
Subject: Re: sorting points or rectangles
>
> ----- Original Message -----
> From: "Dan Moyer" <DANIELMOYER at prodigy.net>
>
> > ... if the edges of the rectangles are all vertical and horizontal with
> respect to
> > the coordinate system (the screen).
>
> I don't understand this quite. Rectangles allways have two horizontal and
> two vertical edges. If edges are not horizontal or vertical then that
would
> be paralelogram or whatever, no?
>
> > Do you need to handle conditions other
> > than that?
>
> No. You all responded with functions how to find out if (and how)
rectangle
> is inside rectangle.
> I have around 10.000 rectangles and I have to get all rectangles which
have
> at least one of their four points inside a big rectangle.
> I want to be able to use binary search on sorted rectangles for speed.
>
> If I do it like this it is too slow:
>
> function get_rects_inside_rect (sequence rectangles, sequence big_rect)
> sequence rects_inside
> sequence rect
> rects_inside = {}
> for int i = 0 to length (rects) do
> rect = rects [i]
> if is_rect_partially_inside_rect (rect, big_rect) then
> rects_inside = append (rects_inside, rect)
> end if
> end for
> return rects_inside
> end function
>
> A little faster it would be if I woluld somehow sort them by their left-x,
> or something similar. Unclear to me right now.
>
>
>
>
8. Re: sorting points or rectangles
- Posted by euman at bellsouth.net
Feb 21, 2002
Hey Tone/all
My question is how you might fit 10,000 rectangles on screen
at the same time....and expect some kind of interaction.
Are these rectangle going to be pushbuttons or have mouse
function that could occur while a pointer is over them?
Or is this an elaborate way to paint a screen?
What is it?
Euman
euman at bellsouth.net
Q: Are we monetarily insane?
A: YES
----- Original Message -----
From: <tone.skoda at siol.net>
To: "EUforum" <EUforum at topica.com>
Sent: Thursday, February 21, 2002 7:31 PM
Subject: Re: sorting points or rectangles
>
> ----- Original Message -----
> From: "Dan Moyer" <DANIELMOYER at prodigy.net>
>
> > ... if the edges of the rectangles are all vertical and horizontal with
> respect to
> > the coordinate system (the screen).
>
> I don't understand this quite. Rectangles allways have two horizontal and
> two vertical edges. If edges are not horizontal or vertical then that would
> be paralelogram or whatever, no?
>
> > Do you need to handle conditions other
> > than that?
>
> No. You all responded with functions how to find out if (and how) rectangle
> is inside rectangle.
> I have around 10.000 rectangles and I have to get all rectangles which have
> at least one of their four points inside a big rectangle.
> I want to be able to use binary search on sorted rectangles for speed.
>
> If I do it like this it is too slow:
>
> function get_rects_inside_rect (sequence rectangles, sequence big_rect)
> sequence rects_inside
> sequence rect
> rects_inside = {}
> for int i = 0 to length (rects) do
> rect = rects [i]
> if is_rect_partially_inside_rect (rect, big_rect) then
> rects_inside = append (rects_inside, rect)
> end if
> end for
> return rects_inside
> end function
>
> A little faster it would be if I woluld somehow sort them by their left-x,
> or something similar. Unclear to me right now.
>
>
>
>
9. Re: sorting points or rectangles
tone,
A rectangle could be *tilted* with respect to the screen, but still have 4
90 degree corners. Do you have any situations like that to consider?
Dan Moyer
----- Original Message -----
From: <tone.skoda at siol.net>
To: "EUforum" <EUforum at topica.com>
Subject: Re: sorting points or rectangles
>
> ----- Original Message -----
> From: "Dan Moyer" <DANIELMOYER at prodigy.net>
>
> > ... if the edges of the rectangles are all vertical and horizontal with
> respect to
> > the coordinate system (the screen).
>
> I don't understand this quite. Rectangles allways have two horizontal and
> two vertical edges. If edges are not horizontal or vertical then that
would
> be paralelogram or whatever, no?
>
> > Do you need to handle conditions other
> > than that?
>
> No. You all responded with functions how to find out if (and how)
rectangle
> is inside rectangle.
> I have around 10.000 rectangles and I have to get all rectangles which
have
> at least one of their four points inside a big rectangle.
> I want to be able to use binary search on sorted rectangles for speed.
>
> If I do it like this it is too slow:
>
> function get_rects_inside_rect (sequence rectangles, sequence big_rect)
> sequence rects_inside
> sequence rect
> rects_inside = {}
> for int i = 0 to length (rects) do
> rect = rects [i]
> if is_rect_partially_inside_rect (rect, big_rect) then
> rects_inside = append (rects_inside, rect)
> end if
> end for
> return rects_inside
> end function
>
> A little faster it would be if I woluld somehow sort them by their left-x,
> or something similar. Unclear to me right now.
>
>
>
>
10. Re: sorting points or rectangles
This is a multi-part message in MIME format.
--------------090605070803030201070102
The opposite sides of a rectangle are always parallel to each other and
90 degrees to their adjacent sides. The rectangle could be at an angle
though.
>
>I don't understand this quite. Rectangles allways have two horizontal and
>two vertical edges. If edges are not horizontal or vertical then that would
>be paralelogram or whatever, no?
>
--------------090605070803030201070102
Content-Type: image/bmp;
name="RECTS.BMP"
11. Re: sorting points or rectangles
22/02/2002 11:31:18 AM, tone.skoda at siol.net wrote:
>
>----- Original Message -----
>From: "Dan Moyer" <DANIELMOYER at prodigy.net>
>
>> ... if the edges of the rectangles are all vertical and horizontal with
>respect to
>> the coordinate system (the screen).
>
>I don't understand this quite. Rectangles allways have two horizontal and
>two vertical edges. If edges are not horizontal or vertical then that would
>be paralelogram or whatever, no?
Not all rectangles are vertical/horizontal. Some are rotated like a diamond
shape.
/\
\/
>> Do you need to handle conditions other
>> than that?
>
>No. You all responded with functions how to find out if (and how) rectangle
>is inside rectangle.
>I have around 10.000 rectangles and I have to get all rectangles which have
>at least one of their four points inside a big rectangle.
>I want to be able to use binary search on sorted rectangles for speed.
>
>If I do it like this it is too slow:
>
>function get_rects_inside_rect (sequence rectangles, sequence big_rect)
> sequence rects_inside
> sequence rect
> rects_inside = {}
> for int i = 0 to length (rects) do
> rect = rects [i]
> if is_rect_partially_inside_rect (rect, big_rect) then
> rects_inside = append (rects_inside, rect)
> end if
> end for
> return rects_inside
>end function
>
>A little faster it would be if I woluld somehow sort them by their left-x,
>or something similar. Unclear to me right now.
I tried a variation of the algorithm you've got here and it was fairly fast on
my machine. I'm
getting 200,000 hits in 0.28 seconds.
------------
sequence testdata
-- Generate some test data.
function randrange(object range)
if atom(range) then
return rand(range)
end if
return rand(range[2]-range[1]+1) + range[1] - 1
end function
testdata = repeat({0,0,0,0}, 200000)
for i = 1 to length(testdata) do
testdata[i][1] = randrange({50,950})
testdata[i][2] = randrange({50,950})
testdata[i][3] = testdata[i][1] + randrange(100)
testdata[i][4] = testdata[i][2] + randrange(100)
end for
-- See how many hits I make
integer hi
sequence BigRectangle
sequence hits
atom startt
startt = time()
hits = repeat(0, length(testdata))
hi = 0
BigRectangle = {200,200,699,699}
for i = 1 to length(testdata) do
if testdata[i][1] <= BigRectangle[3] and
testdata[i][2] <= BigRectangle[4] and
testdata[i][3] >= BigRectangle[1] and
testdata[i][4] >= BigRectangle[2] then
hi += 1
hits[hi] = i
end if
end for
hits = hits[1..hi]
printf(1, "Number of hits: %d in %g seconds \n", {length(hits), time()-startt})
------------
---------
Cheers,
Derek Parnell
12. Re: sorting points or rectangles
- Posted by tone.skoda at siol.net
Feb 22, 2002
I get it.
No, I don't have any situations like that.
My rectangles are all about same size and don't have whole numbers for
coordinates, like this 100000.321.
Something like that:
Please view in a fixed-width font such as
Courier.
+--------+------+-----+---------+
| | | | +-+-------+
| | | ++-------+-+--+ |
| +---+------+----++-+ | | | |
+----+---+------+----++-+-----+-+ | |
| | | | | |
|+--------+ | | +----+----+
|| | | | |
++--------+-----+--+ |
| | | |
| | +-------------+
+--------+
----- Original Message -----
From: "Dan Moyer" <DANIELMOYER at prodigy.net>
To: "EUforum" <EUforum at topica.com>
Sent: Friday, February 22, 2002 3:44 AM
Subject: Re: sorting points or rectangles
>
> tone,
>
> A rectangle could be *tilted* with respect to the screen, but still have 4
> 90 degree corners. Do you have any situations like that to consider?
>
> Dan Moyer
>
> ----- Original Message -----
> From: <tone.skoda at siol.net>
> To: "EUforum" <EUforum at topica.com>
> Sent: Thursday, February 21, 2002 4:31 PM
> Subject: Re: sorting points or rectangles
>
>
> > ----- Original Message -----
> > From: "Dan Moyer" <DANIELMOYER at prodigy.net>
> >
> > > ... if the edges of the rectangles are all vertical and horizontal
with
> > respect to
> > > the coordinate system (the screen).
> >
> > I don't understand this quite. Rectangles allways have two horizontal
and
> > two vertical edges. If edges are not horizontal or vertical then that
> would
> > be paralelogram or whatever, no?
> >
> > > Do you need to handle conditions other
> > > than that?
> >
> > No. You all responded with functions how to find out if (and how)
> rectangle
> > is inside rectangle.
> > I have around 10.000 rectangles and I have to get all rectangles which
> have
> > at least one of their four points inside a big rectangle.
> > I want to be able to use binary search on sorted rectangles for speed.
> >
> > If I do it like this it is too slow:
> >
> > function get_rects_inside_rect (sequence rectangles, sequence big_rect)
> > sequence rects_inside
> > sequence rect
> > rects_inside = {}
> > for int i = 0 to length (rects) do
> > rect = rects [i]
> > if is_rect_partially_inside_rect (rect, big_rect) then
> > rects_inside = append (rects_inside, rect)
> > end if
> > end for
> > return rects_inside
> > end function
> >
> > A little faster it would be if I woluld somehow sort them by their
left-x,
> > or something similar. Unclear to me right now.
> >
> >
>
>
>
13. Re: sorting points or rectangles
- Posted by tone.skoda at siol.net
Feb 22, 2002
They are rectangles of image files which I then put together to get
"composed" image.
----- Original Message -----
From: <euman at bellsouth.net>
To: "EUforum" <EUforum at topica.com>
Subject: Re: sorting points or rectangles
>
> Hey Tone/all
>
> My question is how you might fit 10,000 rectangles on screen
> at the same time....and expect some kind of interaction.
>
> Are these rectangle going to be pushbuttons or have mouse
> function that could occur while a pointer is over them?
>
> Or is this an elaborate way to paint a screen?
>
> What is it?
>
> Euman
> euman at bellsouth.net
>
> Q: Are we monetarily insane?
> A: YES
> ----- Original Message -----
> From: <tone.skoda at siol.net>
> To: "EUforum" <EUforum at topica.com>
> Sent: Thursday, February 21, 2002 7:31 PM
> Subject: Re: sorting points or rectangles
>
>
> > ----- Original Message -----
> > From: "Dan Moyer" <DANIELMOYER at prodigy.net>
> >
> > > ... if the edges of the rectangles are all vertical and horizontal
with
> > respect to
> > > the coordinate system (the screen).
> >
> > I don't understand this quite. Rectangles allways have two horizontal
and
> > two vertical edges. If edges are not horizontal or vertical then that
would
> > be paralelogram or whatever, no?
> >
> > > Do you need to handle conditions other
> > > than that?
> >
> > No. You all responded with functions how to find out if (and how)
rectangle
> > is inside rectangle.
> > I have around 10.000 rectangles and I have to get all rectangles which
have
> > at least one of their four points inside a big rectangle.
> > I want to be able to use binary search on sorted rectangles for speed.
> >
> > If I do it like this it is too slow:
> >
> > function get_rects_inside_rect (sequence rectangles, sequence big_rect)
> > sequence rects_inside
> > sequence rect
> > rects_inside = {}
> > for int i = 0 to length (rects) do
> > rect = rects [i]
> > if is_rect_partially_inside_rect (rect, big_rect) then
> > rects_inside = append (rects_inside, rect)
> > end if
> > end for
> > return rects_inside
> > end function
> >
> > A little faster it would be if I woluld somehow sort them by their
left-x,
> > or something similar. Unclear to me right now.
> >
> >
>
>
>
14. Re: sorting points or rectangles
Tone,
Ok, no tilted rectangles.
But let me get this straight: is it only rectangles *wholly* inside another
rectangle you're concerned with, or is it any rectangle that is even
*partly* inside another that concerns you? And do you need to know how much
of one is inside the other, perhaps for clipping purposes?
Dan
----- Original Message -----
From: <tone.skoda at siol.net>
To: "EUforum" <EUforum at topica.com>
Sent: Thursday, February 21, 2002 3:53 PM
Subject: Re: sorting points or rectangles
>
> I get it.
> No, I don't have any situations like that.
> My rectangles are all about same size and don't have whole numbers for
> coordinates, like this 100000.321.
>
> Something like that:
>
> Please view in a fixed-width font such as
> Courier.
>
> +--------+------+-----+---------+
> | | | | +-+-------+
> | | | ++-------+-+--+ |
> | +---+------+----++-+ | | | |
> +----+---+------+----++-+-----+-+ | |
> | | | | | |
> |+--------+ | | +----+----+
> || | | | |
> ++--------+-----+--+ |
> | | | |
> | | +-------------+
> +--------+
>
>
> ----- Original Message -----
> From: "Dan Moyer" <DANIELMOYER at prodigy.net>
> To: "EUforum" <EUforum at topica.com>
> Sent: Friday, February 22, 2002 3:44 AM
> Subject: Re: sorting points or rectangles
>
>
> > tone,
> >
> > A rectangle could be *tilted* with respect to the screen, but still have
4
> > 90 degree corners. Do you have any situations like that to consider?
> >
> > Dan Moyer
> >
> > ----- Original Message -----
> > From: <tone.skoda at siol.net>
> > To: "EUforum" <EUforum at topica.com>
> > Sent: Thursday, February 21, 2002 4:31 PM
> > Subject: Re: sorting points or rectangles
> >
> >
> > > ----- Original Message -----
> > > From: "Dan Moyer" <DANIELMOYER at prodigy.net>
> > >
> > > > ... if the edges of the rectangles are all vertical and horizontal
> with
> > > respect to
> > > > the coordinate system (the screen).
> > >
> > > I don't understand this quite. Rectangles allways have two horizontal
> and
> > > two vertical edges. If edges are not horizontal or vertical then that
> > would
> > > be paralelogram or whatever, no?
> > >
> > > > Do you need to handle conditions other
> > > > than that?
> > >
> > > No. You all responded with functions how to find out if (and how)
> > rectangle
> > > is inside rectangle.
> > > I have around 10.000 rectangles and I have to get all rectangles which
> > have
> > > at least one of their four points inside a big rectangle.
> > > I want to be able to use binary search on sorted rectangles for speed.
> > >
> > > If I do it like this it is too slow:
> > >
> > > function get_rects_inside_rect (sequence rectangles, sequence
big_rect)
> > > sequence rects_inside
> > > sequence rect
> > > rects_inside = {}
> > > for int i = 0 to length (rects) do
> > > rect = rects [i]
> > > if is_rect_partially_inside_rect (rect, big_rect) then
> > > rects_inside = append (rects_inside, rect)
> > > end if
> > > end for
> > > return rects_inside
> > > end function
> > >
> > > A little faster it would be if I woluld somehow sort them by their
> left-x,
> > > or something similar. Unclear to me right now.
> > >
> > >
>
>
>
15. Re: sorting points or rectangles
Tone,
Ok, on the assumption that you *do* want to find any rectangle that is even
partly within another (all oriented parallel to x-y axes), the following
should do it, I think even with decimal coordinates, though I didn't test
that. It finds approx. 7000 hits from 20000 possibles in about .11 seconds.
And it saves all hits (full coords.) in a sequence. I don't know if you
want to "clip" portions of the intersecting rectangles of not, nor if you
did, which (portion of big or portion of small) you might want to clip.
A note on the displayed output: I made one hit per trial display, so I
could check to see if it was actually finding ones that were not wholly
inside the big rectangle; but the coordinates of the upper left corner of
the big one, {200,200}, display as some printer characters instead of
numbers when using print.e
Dan Moyer
-- CODE FOLLOWS:
-- TEST TO SEE IF ANY RECTANGLE IS AT LEAST PARTLY INSIDE A BIGGER ONE:
-- for rectangles each defined by 4 corner points in this order:
-- left-upper xy, right-upper xy, right-lower xy, left-lower xy:
-- {{lux,luy}, {rux, ruy}, {rlx,rly},{llx,lly}}
include misc.e -- to use sprint
include print.e -- to allow "pretty print" of whole sequences
-- lu = left upper corner, ru = right upper corner,
-- rl = right lower, ll = left lower
constant lu = 1, ru = 2, rl= 3, ll = 4, x = 1, y = 2
sequence testRects
testRects = repeat({{0,0},{0,0},{0,0},{0,0}}, 20000)
sequence BigRectangle
BigRectangle = {{200,200},{699,200},{699,699},{200,699}}
sequence aHit -- to store corner coords of rectangles partly in big one
aHit = {}
integer hit
hit = 0
atom TotHits, TotTime -- used to get averages
TotHits = 0
TotTime = 0
atom stime, etime -- start and end times of tests
-- borrowed following two from Derek, & then altered 2nd:
-- Generate some test data.
function randrange(object range)
if atom(range) then
return rand(range)
end if
return rand(range[2]-range[1]+1) + range[1] - 1
end function
procedure makeTestData()
for i = 1 to length(testRects) do
testRects[i][lu][x] = randrange({50,950})
testRects[i][lu][y] = randrange({50,950})
testRects[i][ru][x] = testRects[i][lu][x] + randrange(100)
testRects[i][ru][y] = testRects[i][lu][y]
testRects[i][rl][x] = testRects[i][ru][x]
testRects[i][rl][y] = testRects[i][lu][y] + randrange(100)
testRects[i][ll][x] = testRects[i][lu][x]
testRects[i][ll][y] = testRects[i][rl][y]
end for
end procedure
-- determines if a rectangle is at least partly inside the big one:
function IsPartlyInside(sequence OuterRect, sequence PossPrtlyInside)
if (PossPrtlyInside[lu][x] > OuterRect[lu][x] and --
PossPrtlyInside[lu][x] < OuterRect[ru][x] and --left upper in big
PossPrtlyInside[lu][y] > OuterRect[lu][y] and --
PossPrtlyInside[lu][y] < OuterRect[ll][y])
or
(PossPrtlyInside[ru][x] > OuterRect[lu][x] and --
PossPrtlyInside[ru][x] < OuterRect[ru][x] and --right upper in big
PossPrtlyInside[ru][y] > OuterRect[lu][y] and --
PossPrtlyInside[ru][y] < OuterRect[ll][y])
or
(PossPrtlyInside[rl][x] > OuterRect[lu][x] and --
PossPrtlyInside[rl][x] < OuterRect[ru][x] and --right lower in big
PossPrtlyInside[rl][y] > OuterRect[lu][y] and --
PossPrtlyInside[rl][y] < OuterRect[ll][y])
or
(PossPrtlyInside[ll][x] > OuterRect[lu][x] and --
PossPrtlyInside[ll][x] < OuterRect[ru][x] and --left lower in big
PossPrtlyInside[ll][y] > OuterRect[lu][y] and --
PossPrtlyInside[ll][y] < OuterRect[ll][y])
then return 1 -- for true
else return 0 -- for false
end if
end function
procedure doAtest()
makeTestData() -- make new test rectangles each test
hit = 0
aHit = {}
stime = time()
for n = 1 to length(testRects) do
if IsPartlyInside(BigRectangle, testRects[n]) then
hit += 1
aHit &= {testRects[n]} -- save coords of partly inside rectangle
end if
end for
etime = time() - stime
puts(1, "\nhits= " & sprint(hit) & " in " & sprint(etime) & " seconds\n")
puts(1, "length of hits sequence: " & sprint(length(aHit)) & "\n")
puts(1, "big rectangle: ")
print(1, BigRectangle)
puts(1, "\na smaller rectangle: ")
print(1, aHit[1]) -- just show one of them
puts(1, "\n")
TotTime += etime
TotHits += hit
end procedure
for m = 1 to 10 do
doAtest()
end for
puts(1, "\naverage of " & sprint(floor(TotHits/10)) & " hits in average of "
& sprint(TotTime/10) & " seconds,\nout of 10 trials of 20,000 rectangles
each trial.")
-- CODE ENDS
----- Original Message -----
From: <tone.skoda at siol.net>
>
> I get it.
> No, I don't have any situations like that.
> My rectangles are all about same size and don't have whole numbers for
> coordinates, like this 100000.321.
>
> Something like that:
>
> Please view in a fixed-width font such as
> Courier.
>
> +--------+------+-----+---------+
> | | | | +-+-------+
> | | | ++-------+-+--+ |
> | +---+------+----++-+ | | | |
> +----+---+------+----++-+-----+-+ | |
> | | | | | |
> |+--------+ | | +----+----+
> || | | | |
> ++--------+-----+--+ |
> | | | |
> | | +-------------+
> +--------+
>
>
> ----- Original Message -----
> From: "Dan Moyer" <DANIELMOYER at prodigy.net>
>
>
> > tone,
> >
> > A rectangle could be *tilted* with respect to the screen, but still have
4
> > 90 degree corners. Do you have any situations like that to consider?
> >
> > Dan Moyer
> >
16. Re: sorting points or rectangles
Rectangles oriented parallel to the x-y axes are normally defined by only 2
points {upper-left xy, lower-right xy}. To determine if a rectangle falls
within another, it is quicker to eliminate those that aren't inside, as
shown below:
Colin Taylor
-- start code:
-- TEST TO SEE IF ANY RECTANGLE IS AT LEAST PARTLY INSIDE A BIGGER ONE:
-- for rectangles each defined by 2 corner points in this order:
-- upper-left xy, lower-right xy: {{ulx,uly}, {lrx,lry}}
include misc.e
constant ul = 1, lr = 2, x = 1, y = 2
sequence BigRectangle, testRects, aHit
integer hit
atom TotHits, TotTime, stime, etime
BigRectangle = {{200,200},{699,699}}
testRects = repeat({{0,0},{0,0}}, 20000)
aHit = {}
hit = 0
TotHits = 0
TotTime = 0
function randrange(object range)
-- borrowed following two from Derek, & then altered 2nd:
if atom(range) then
return rand(range)
end if
return rand(range[2]-range[1]+1) + range[1] - 1
end function
procedure makeTestData()
-- generate some test data.
for i = 1 to length(testRects) do
testRects[i][ul] = {randrange({50,950}), randrange({50,950})}
testRects[i][lr][x] = testRects[i][ul][x] + randrange(100)
testRects[i][lr][y] = testRects[i][ul][y] + randrange(100)
end for
end procedure
function IsPartlyInside(sequence OuterRect, sequence PossPrtlyInside)
-- determines if a rectangle is at least partly inside the big one:
if PossPrtlyInside[lr][x] <= OuterRect[ul][x] then -- to left
return 0
elsif PossPrtlyInside[ul][x] >= OuterRect[lr][x] then -- to right
return 0
elsif PossPrtlyInside[lr][y] <= OuterRect[ul][y] then -- above
return 0
elsif PossPrtlyInside[ul][y] >= OuterRect[lr][y] then -- below
return 0
else
return 1
end if
end function
procedure doAtest()
makeTestData() -- make new test rectangles each test
hit = 0
aHit = {}
stime = time()
for n = 1 to length(testRects) do
if IsPartlyInside(BigRectangle, testRects[n]) then
hit += 1
aHit &= {testRects[n]} -- save coords of partly inside
rectangle
end if
end for
etime = time() - stime
puts(1, "\nhits= " & sprint(hit) & " in " & sprint(etime) & "
seconds\n")
puts(1, "length of hits sequence: " & sprint(length(aHit)) & "\n")
puts(1, "big rectangle: ")
print(1, BigRectangle)
puts(1, "\na smaller rectangle: ")
print(1, aHit[1]) -- just show one of them
puts(1, "\n")
TotTime += etime
TotHits += hit
end procedure
for m = 1 to 10 do
doAtest()
end for
puts(1, "\naverage of " & sprint(floor(TotHits/10)) & " hits in average of "
& sprint(TotTime/10) & " seconds,\nout of 10 trials of 20,000 rectangles
each trial.")
-- end code
----- Original Message -----
Subject: Re: sorting points or rectangles
> Tone,
>
> Ok, on the assumption that you *do* want to find any rectangle that is
even
> partly within another (all oriented parallel to x-y axes), the following
> should do it ...
17. Re: sorting points or rectangles
- Posted by tone.skoda at siol.net
Feb 23, 2002
It's any rectangle that is partly inside the specified big rectangle.
I do need to know how much it is inside for clipping, but that is not a
problem.
----- Original Message -----
From: "Dan Moyer" <DANIELMOYER at prodigy.net>
To: "EUforum" <EUforum at topica.com>
Subject: Re: sorting points or rectangles
>
> Tone,
>
> Ok, no tilted rectangles.
>
> But let me get this straight: is it only rectangles *wholly* inside
another
> rectangle you're concerned with, or is it any rectangle that is even
> *partly* inside another that concerns you? And do you need to know how
much
> of one is inside the other, perhaps for clipping purposes?
>
> Dan
>
> ----- Original Message -----
> From: <tone.skoda at siol.net>
> To: "EUforum" <EUforum at topica.com>
> Sent: Thursday, February 21, 2002 3:53 PM
> Subject: Re: sorting points or rectangles
>
>
> > I get it.
> > No, I don't have any situations like that.
> > My rectangles are all about same size and don't have whole numbers for
> > coordinates, like this 100000.321.
> >
> > Something like that:
> >
> > Please view in a fixed-width font such as
> > Courier.
> >
> > +--------+------+-----+---------+
> > | | | | +-+-------+
> > | | | ++-------+-+--+ |
> > | +---+------+----++-+ | | | |
> > +----+---+------+----++-+-----+-+ | |
> > | | | | | |
> > |+--------+ | | +----+----+
> > || | | | |
> > ++--------+-----+--+ |
> > | | | |
> > | | +-------------+
> > +--------+
> >
> >
> > ----- Original Message -----
> > From: "Dan Moyer" <DANIELMOYER at prodigy.net>
> > To: "EUforum" <EUforum at topica.com>
> > Sent: Friday, February 22, 2002 3:44 AM
> > Subject: Re: sorting points or rectangles
> >
> >
> > > tone,
> > >
> > > A rectangle could be *tilted* with respect to the screen, but still
have
> 4
> > > 90 degree corners. Do you have any situations like that to consider?
> > >
> > > Dan Moyer
> > >
> > > ----- Original Message -----
> > > From: <tone.skoda at siol.net>
> > > To: "EUforum" <EUforum at topica.com>
> > > Sent: Thursday, February 21, 2002 4:31 PM
> > > Subject: Re: sorting points or rectangles
> > >
> > >
> > > > ----- Original Message -----
> > > > From: "Dan Moyer" <DANIELMOYER at prodigy.net>
> > > >
> > > > > ... if the edges of the rectangles are all vertical and horizontal
> > with
> > > > respect to
> > > > > the coordinate system (the screen).
> > > >
> > > > I don't understand this quite. Rectangles allways have two
horizontal
> > and
> > > > two vertical edges. If edges are not horizontal or vertical then
that
> > > would
> > > > be paralelogram or whatever, no?
> > > >
> > > > > Do you need to handle conditions other
> > > > > than that?
> > > >
> > > > No. You all responded with functions how to find out if (and how)
> > > rectangle
> > > > is inside rectangle.
> > > > I have around 10.000 rectangles and I have to get all rectangles
which
> > > have
> > > > at least one of their four points inside a big rectangle.
> > > > I want to be able to use binary search on sorted rectangles for
speed.
> > > >
> > > > If I do it like this it is too slow:
> > > >
> > > > function get_rects_inside_rect (sequence rectangles, sequence
> big_rect)
> > > > sequence rects_inside
> > > > sequence rect
> > > > rects_inside = {}
> > > > for int i = 0 to length (rects) do
> > > > rect = rects [i]
> > > > if is_rect_partially_inside_rect (rect, big_rect) then
> > > > rects_inside = append (rects_inside, rect)
> > > > end if
> > > > end for
> > > > return rects_inside
> > > > end function
> > > >
> > > > A little faster it would be if I woluld somehow sort them by their
> > left-x,
> > > > or something similar. Unclear to me right now.
> > > >
> > > >
>
>
>
18. Re: sorting points or rectangles
If you want to search only part of the list of rectangles, and
assuming you are prepared to initially sort/keep your list of
rectangles in order, the best I can think of is distance from (0,0).
I know it's root(x^2+y^2) but you don't need to calculate that root.
If your list of rectangles is built such that if top left=(x,y) then
x^2+y^2 is ascending for each entry in the table, then for a rectangle
(tx,ty) to (bx,by) you use a binary chop to find any entry in the
table with tx^2+ty^2<=x^2+y^2<=bx^2+by^2 & then run backwards and
forwards in the table to process any other possibles. Obviously you
need to repeat that check on the next/prior table entries to see if
you should continue or not, then check tx<=x<=bx and ty<=y<=by to see
if you actually want to do anything with it.
The advantage is only really there for small rectangles (which I
assume you have a fair few of) as they would only need to check a
small percentage of the rectangles in the table. The cost of course is
keeping that list in ascending order.
Pete
19. Re: sorting points or rectangles
Oops! That will only get those with the top right corner inside the
bigger rectangle. Back to the drawing board.
Pete
20. Re: sorting points or rectangles
Colin,
Looking at your revision of my code quickly, I can't be sure if it handles
small rectangles to the upper right of the big rectangle. I can see that
the coords. of the lower left point of the small rectangle can in fact be
expressed in terms of the two defining points/corners, but I can't be sure
your code tests for the possible presence of lower left corner of small (and
upper right corner, too) in big. I'll look at it more later, but maybe you
can verify sooner. (That kind of question was why I output samples of the
test rectangles coords., to compare against the big rectangles coords. &
make sure all that were at least partly inside were found, not just those
wholly inside.)
Dan Moyer
----- Original Message -----
From: <cetaylor at compuserve.com>
To: "EUforum" <EUforum at topica.com>
Sent: Saturday, February 23, 2002 7:55 PM
Subject: Re: sorting points or rectangles
>
> Rectangles oriented parallel to the x-y axes are normally defined by only
2
> points {upper-left xy, lower-right xy}. To determine if a rectangle falls
> within another, it is quicker to eliminate those that aren't inside, as
> shown below:
>
> Colin Taylor
>
> -- start code:
>
> -- TEST TO SEE IF ANY RECTANGLE IS AT LEAST PARTLY INSIDE A BIGGER ONE:
> -- for rectangles each defined by 2 corner points in this order:
> -- upper-left xy, lower-right xy: {{ulx,uly}, {lrx,lry}}
>
> include misc.e
>
> constant ul = 1, lr = 2, x = 1, y = 2
>
> sequence BigRectangle, testRects, aHit
> integer hit
> atom TotHits, TotTime, stime, etime
> BigRectangle = {{200,200},{699,699}}
> testRects = repeat({{0,0},{0,0}}, 20000)
> aHit = {}
> hit = 0
> TotHits = 0
> TotTime = 0
>
> function randrange(object range)
> -- borrowed following two from Derek, & then altered 2nd:
> if atom(range) then
> return rand(range)
> end if
> return rand(range[2]-range[1]+1) + range[1] - 1
> end function
>
> procedure makeTestData()
> -- generate some test data.
> for i = 1 to length(testRects) do
> testRects[i][ul] = {randrange({50,950}), randrange({50,950})}
> testRects[i][lr][x] = testRects[i][ul][x] + randrange(100)
> testRects[i][lr][y] = testRects[i][ul][y] + randrange(100)
> end for
> end procedure
>
> function IsPartlyInside(sequence OuterRect, sequence PossPrtlyInside)
> -- determines if a rectangle is at least partly inside the big one:
> if PossPrtlyInside[lr][x] <= OuterRect[ul][x] then -- to left
> return 0
> elsif PossPrtlyInside[ul][x] >= OuterRect[lr][x] then -- to right
> return 0
> elsif PossPrtlyInside[lr][y] <= OuterRect[ul][y] then -- above
> return 0
> elsif PossPrtlyInside[ul][y] >= OuterRect[lr][y] then -- below
> return 0
> else
> return 1
> end if
> end function
>
> procedure doAtest()
> makeTestData() -- make new test rectangles each test
> hit = 0
> aHit = {}
>
> stime = time()
> for n = 1 to length(testRects) do
> if IsPartlyInside(BigRectangle, testRects[n]) then
> hit += 1
> aHit &= {testRects[n]} -- save coords of partly inside
> rectangle
> end if
> end for
> etime = time() - stime
>
> puts(1, "\nhits= " & sprint(hit) & " in " & sprint(etime) & "
> seconds\n")
> puts(1, "length of hits sequence: " & sprint(length(aHit)) & "\n")
> puts(1, "big rectangle: ")
> print(1, BigRectangle)
> puts(1, "\na smaller rectangle: ")
> print(1, aHit[1]) -- just show one of them
> puts(1, "\n")
>
> TotTime += etime
> TotHits += hit
> end procedure
>
> for m = 1 to 10 do
> doAtest()
> end for
>
> puts(1, "\naverage of " & sprint(floor(TotHits/10)) & " hits in average of
"
> & sprint(TotTime/10) & " seconds,\nout of 10 trials of 20,000
rectangles
> each trial.")
>
> -- end code
>
> ----- Original Message -----
> Subject: Re: sorting points or rectangles
>
>
> > Tone,
> >
> > Ok, on the assumption that you *do* want to find any rectangle that is
> even
> > partly within another (all oriented parallel to x-y axes), the following
> > should do it ...
>
>
>
>
21. Re: sorting points or rectangles
Colin,
I now see that you are in fact finding *all* corners that could be inside
the target rectangle, using the "negative" logic of excluding any that
*can't* be inside. Nice! Should be faster, which is what Tone needs.
Dan
----- Original Message -----
From: <cetaylor at compuserve.com>
To: "EUforum" <EUforum at topica.com>
Subject: Re: sorting points or rectangles
>
> Rectangles oriented parallel to the x-y axes are normally defined by only
2
> points {upper-left xy, lower-right xy}. To determine if a rectangle falls
> within another, it is quicker to eliminate those that aren't inside, as
> shown below:
>
> Colin Taylor
>
> -- start code:
>
> -- TEST TO SEE IF ANY RECTANGLE IS AT LEAST PARTLY INSIDE A BIGGER ONE:
> -- for rectangles each defined by 2 corner points in this order:
> -- upper-left xy, lower-right xy: {{ulx,uly}, {lrx,lry}}
>
> include misc.e
>
> constant ul = 1, lr = 2, x = 1, y = 2
>
> sequence BigRectangle, testRects, aHit
> integer hit
> atom TotHits, TotTime, stime, etime
> BigRectangle = {{200,200},{699,699}}
> testRects = repeat({{0,0},{0,0}}, 20000)
> aHit = {}
> hit = 0
> TotHits = 0
> TotTime = 0
>
> function randrange(object range)
> -- borrowed following two from Derek, & then altered 2nd:
> if atom(range) then
> return rand(range)
> end if
> return rand(range[2]-range[1]+1) + range[1] - 1
> end function
>
> procedure makeTestData()
> -- generate some test data.
> for i = 1 to length(testRects) do
> testRects[i][ul] = {randrange({50,950}), randrange({50,950})}
> testRects[i][lr][x] = testRects[i][ul][x] + randrange(100)
> testRects[i][lr][y] = testRects[i][ul][y] + randrange(100)
> end for
> end procedure
>
> function IsPartlyInside(sequence OuterRect, sequence PossPrtlyInside)
> -- determines if a rectangle is at least partly inside the big one:
> if PossPrtlyInside[lr][x] <= OuterRect[ul][x] then -- to left
> return 0
> elsif PossPrtlyInside[ul][x] >= OuterRect[lr][x] then -- to right
> return 0
> elsif PossPrtlyInside[lr][y] <= OuterRect[ul][y] then -- above
> return 0
> elsif PossPrtlyInside[ul][y] >= OuterRect[lr][y] then -- below
> return 0
> else
> return 1
> end if
> end function
>
> procedure doAtest()
> makeTestData() -- make new test rectangles each test
> hit = 0
> aHit = {}
>
> stime = time()
> for n = 1 to length(testRects) do
> if IsPartlyInside(BigRectangle, testRects[n]) then
> hit += 1
> aHit &= {testRects[n]} -- save coords of partly inside
> rectangle
> end if
> end for
> etime = time() - stime
>
> puts(1, "\nhits= " & sprint(hit) & " in " & sprint(etime) & "
> seconds\n")
> puts(1, "length of hits sequence: " & sprint(length(aHit)) & "\n")
> puts(1, "big rectangle: ")
> print(1, BigRectangle)
> puts(1, "\na smaller rectangle: ")
> print(1, aHit[1]) -- just show one of them
> puts(1, "\n")
>
> TotTime += etime
> TotHits += hit
> end procedure
>
> for m = 1 to 10 do
> doAtest()
> end for
>
> puts(1, "\naverage of " & sprint(floor(TotHits/10)) & " hits in average of
"
> & sprint(TotTime/10) & " seconds,\nout of 10 trials of 20,000
rectangles
> each trial.")
>
> -- end code
>
> ----- Original Message -----
> Subject: Re: sorting points or rectangles
>
>
> > Tone,
> >
> > Ok, on the assumption that you *do* want to find any rectangle that is
> even
> > partly within another (all oriented parallel to x-y axes), the following
> > should do it ...
>
>
>
>
22. Re: sorting points or rectangles
Dan,
It will work for all cases of overlap. Here is another version of the same
algorithm which graphically demonstrates that it works correctly.
Colin Taylor
-- begin code
-- detects overlap between 2 rectangles
function min(atom a, atom b)
if b < a then return b
else return a
end if
end function
function max(atom a, atom b)
if a < b then return b
else return a
end if
end function
function overlap(sequence r1,sequence r2)
-- returns overlap rectangle or 0
if r1[2][1] <= r2[1][1] or r1[1][1] >= r2[2][1] or
r1[2][2] <= r2[1][2] or r1[1][2] >= r2[2][2] then
return 0 -- no overlap
end if
return {{max(r1[1][1], r2[1][1]), max(r1[1][2], r2[1][2])},
{min(r1[2][1], r2[2][1]), min(r1[2][2], r2[2][2])}}
end function
-- test code
include graphics.e
include get.e
if graphics_mode(261) then
end if
function randrect()
atom a, b, c, d
a = rand(1000)/10+300
b = a + rand(3000)/10
c = rand(1000)/10+200
d = c + rand(3000)/10
return {{a, c}, {b, d}}
end function
procedure drawrect(integer c, integer f, sequence xy1, sequence xy2)
polygon(c, f, {xy1, {xy2[1], xy1[2]}, xy2, {xy1[1], xy2[2]}})
end procedure
sequence r1, r2
object r3
while 1 do
r1 = randrect()
r2 = randrect()
r3 = overlap(r1, r2)
drawrect(RED, 0, r1[1], r1[2])
drawrect(GREEN, 0, r2[1], r2[2])
if sequence(r3) then
drawrect(WHITE, 1, r3[1], r3[2])
end if
puts(1, "rectangle 1 (red) = ")
? r1
puts(1, "rectangle 2 (green) = ")
? r2
puts(1, "overlap = ")
? r3
puts(1, "\nPress spacebar for next or any other key to exit.\n")
if wait_key() = 32 then
clear_screen()
else
exit
end if
end while
-- end code
----- Original Message -----
>
> Colin,
>
> Looking at your revision of my code quickly, I can't be sure if it handles
> small rectangles to the upper right of the big rectangle. I can see that
> the coords. of the lower left point of the small rectangle can in fact be
> expressed in terms of the two defining points/corners, but I can't be sure
> your code tests for the possible presence of lower left corner of small
(and
> upper right corner, too) in big. I'll look at it more later, but maybe
you
> can verify sooner. (That kind of question was why I output samples of the
> test rectangles coords., to compare against the big rectangles coords. &
> make sure all that were at least partly inside were found, not just those
> wholly inside.)
>
> Dan Moyer
>
> >
> > Rectangles oriented parallel to the x-y axes are normally defined by
only
> 2
> > points {upper-left xy, lower-right xy}. To determine if a rectangle
falls
> > within another, it is quicker to eliminate those that aren't inside, as
> > shown below:
> >
> > Colin Taylor
> >
> > -- start code:
> >
> > -- TEST TO SEE IF ANY RECTANGLE IS AT LEAST PARTLY INSIDE A BIGGER ONE:
> > -- for rectangles each defined by 2 corner points in this order:
> > -- upper-left xy, lower-right xy: {{ulx,uly}, {lrx,lry}}
> >
> > include misc.e
> >
> > constant ul = 1, lr = 2, x = 1, y = 2
> >
> > sequence BigRectangle, testRects, aHit
> > integer hit
> > atom TotHits, TotTime, stime, etime
> > BigRectangle = {{200,200},{699,699}}
> > testRects = repeat({{0,0},{0,0}}, 20000)
> > aHit = {}
> > hit = 0
> > TotHits = 0
> > TotTime = 0
> >
> > function randrange(object range)
> > -- borrowed following two from Derek, & then altered 2nd:
> > if atom(range) then
> > return rand(range)
> > end if
> > return rand(range[2]-range[1]+1) + range[1] - 1
> > end function
> >
> > procedure makeTestData()
> > -- generate some test data.
> > for i = 1 to length(testRects) do
> > testRects[i][ul] = {randrange({50,950}), randrange({50,950})}
> > testRects[i][lr][x] = testRects[i][ul][x] + randrange(100)
> > testRects[i][lr][y] = testRects[i][ul][y] + randrange(100)
> > end for
> > end procedure
> >
> > function IsPartlyInside(sequence OuterRect, sequence PossPrtlyInside)
> > -- determines if a rectangle is at least partly inside the big one:
> > if PossPrtlyInside[lr][x] <= OuterRect[ul][x] then -- to left
> > return 0
> > elsif PossPrtlyInside[ul][x] >= OuterRect[lr][x] then -- to right
> > return 0
> > elsif PossPrtlyInside[lr][y] <= OuterRect[ul][y] then -- above
> > return 0
> > elsif PossPrtlyInside[ul][y] >= OuterRect[lr][y] then -- below
> > return 0
> > else
> > return 1
> > end if
> > end function
> >
> > procedure doAtest()
> > makeTestData() -- make new test rectangles each test
> > hit = 0
> > aHit = {}
> >
> > stime = time()
> > for n = 1 to length(testRects) do
> > if IsPartlyInside(BigRectangle, testRects[n]) then
> > hit += 1
> > aHit &= {testRects[n]} -- save coords of partly inside
> > rectangle
> > end if
> > end for
> > etime = time() - stime
> >
> > puts(1, "\nhits= " & sprint(hit) & " in " & sprint(etime) & "
> > seconds\n")
> > puts(1, "length of hits sequence: " & sprint(length(aHit)) & "\n")
> > puts(1, "big rectangle: ")
> > print(1, BigRectangle)
> > puts(1, "\na smaller rectangle: ")
> > print(1, aHit[1]) -- just show one of them
> > puts(1, "\n")
> >
> > TotTime += etime
> > TotHits += hit
> > end procedure
> >
> > for m = 1 to 10 do
> > doAtest()
> > end for
> >
> > puts(1, "\naverage of " & sprint(floor(TotHits/10)) & " hits in average
of
> "
> > & sprint(TotTime/10) & " seconds,\nout of 10 trials of 20,000
> rectangles
> > each trial.")
> >
> > -- end code
> >
> > ----- Original Message -----
> > Subject: Re: sorting points or rectangles
> >
> >
> > > Tone,
> > >
> > > Ok, on the assumption that you *do* want to find any rectangle that is
> > even
> > > partly within another (all oriented parallel to x-y axes), the
following
> > > should do it ...
> >
> >
