OpenEuphoria

Re: sorting points or rectangles

• Posted by cetaylor at compuserve.com Feb 23, 2002
• 488 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 ...