OpenEuphoria

Re: sorting points or rectangles

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