OpenEuphoria

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 ...
> >
> >