OpenEuphoria

Re: sorting points or rectangles

• Posted by Derek Parnell <ddparnell at bigpond.com> Feb 20, 2002
• 548 views

21/02/2002 9:33:43 AM, tone.skoda at siol.net wrote:

>
>  does anybody have any idea how could i sort rectangles or points, same
>  problem.
>  i need it sorted so that when i have a lot of rectangles, i can quickly get
>
>  the ones which are inside some given big rectangle.
>
>

Assuming that the rectangles are not rotated with respect to the screen, that
is, the edges are all
vertical and horizontal, and that the edges meet at 90 degrees you might like to
explore this
attempt. It examines two rectangles and returns one of four possiblities- the
two rectangles do not
overlap at any point, the first rectangle is completely inside the second, the
second rectangle is
completely in the first, or that they overlap.

   global constant kNoOverlap = 0,
            kOverlap = 1,
            kAinB = 2,
            kBinA = 3,
            kLeft = 1,
            kTop = 2,
            kRight = 3,
            kBottom = 4
   global function RectHit(sequence RectA, sequence RectB)
     -- The sequence has four elements:
     --   1 = Left edge coordinate
     --   2 = Top edge coordinate
     --   3 = Width
     --   4 = Height

     -- Convert to right and bottom edges
     RectA[kRight] += RectA[kLeft] - 1
     RectA[kBottom] += RectA[kTop] - 1

     RectB[kRight] += RectB[kLeft] - 1
     RectB[kBottom] += RectB[kTop] - 1

     if RectB[kTop]    > RectA[kBottom] or
        RectB[kBottom] < RectA[kTop]    or
        RectB[kLeft]   > RectA[kRight]  or
        RectB[kRight]  < RectA[kLeft]   then 
         return kNoOverlap 
     end if

     -- At this point, they either overlap or one is totally inside
     -- the other.

     if RectB[kTop]    >= RectA[kTop]    and
        RectB[kBottom] <= RectA[kBottom] and
        RectB[kLeft]   >= RectA[kLeft]   and
        RectB[kRight]  <= RectA[kRight]  then 
         return kBinA 
     end if

     if RectB[kTop]    < RectA[kTop]    and
        RectB[kBottom] > RectA[kBottom] and
        RectB[kLeft]   < RectA[kLeft]   and
        RectB[kRight]  > RectA[kRight]  then 
         return kAinB 
     end if

     -- At this point, neither is completely enclosed so they must overlap.
     return kOverlap
  end function

---------
cheers,
Derek