OpenEuphoria

Re: sorting points or rectangles

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