1. sorting points or rectangles
- Posted by tone.skoda at siol.net Feb 20, 2002
- 582 views
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
- 528 views
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
- Posted by Dan Moyer <DANIELMOYER at prodigy.net> Feb 20, 2002
- 533 views
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
- Posted by Derek Parnell <ddparnell at bigpond.com> Feb 20, 2002
- 548 views
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
- Posted by Dan Moyer <DANIELMOYER at prodigy.net> Feb 21, 2002
- 525 views
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
- 530 views
----- 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
- 543 views
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
- 565 views
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
- Posted by Dan Moyer <DANIELMOYER at prodigy.net> Feb 21, 2002
- 556 views
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
- Posted by Evan Marshall <evan at net-link.net> Feb 21, 2002
- 538 views
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
- Posted by Derek Parnell <ddparnell at bigpond.com> Feb 21, 2002
- 539 views
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
- 560 views
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
- 544 views
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
- Posted by Dan Moyer <DANIELMOYER at prodigy.net> Feb 22, 2002
- 547 views
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
- Posted by Dan Moyer <DANIELMOYER at prodigy.net> Feb 23, 2002
- 517 views
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
- Posted by cetaylor at compuserve.com Feb 23, 2002
- 512 views
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
- 512 views
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
- Posted by petelomax at blueyonder.co.uk Feb 23, 2002
- 516 views
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
- Posted by petelomax at blueyonder.co.uk Feb 23, 2002
- 563 views
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
- Posted by Dan Moyer <DANIELMOYER at prodigy.net> Feb 23, 2002
- 516 views
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
- Posted by Dan Moyer <DANIELMOYER at prodigy.net> Feb 23, 2002
- 533 views
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
- Posted by cetaylor at compuserve.com Feb 23, 2002
- 525 views
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 ... > > > >