OpenEuphoria

Re: sorting points or rectangles

• Posted by Dan Moyer <DANIELMOYER at prodigy.net> Feb 23, 2002
• 493 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 ...
>
>
>
>