OpenEuphoria

Re: sorting points or rectangles

• Posted by tone.skoda at siol.net Feb 21, 2002
• 533 views

----- Original Message -----
From: "Dan Moyer" <DANIELMOYER at prodigy.net>

> ... if the edges of the rectangles are all vertical and horizontal with
respect to
> the coordinate system (the screen).

I don't understand this quite. Rectangles allways have two horizontal and
two vertical edges. If edges are not horizontal or vertical then that would
be paralelogram or whatever, no?

> Do you need to handle conditions other
> than that?

No. You all responded with functions how to find out if (and how) rectangle
is inside rectangle.
I have around 10.000 rectangles and I have to get all rectangles which have
at least one of their four points inside a big rectangle.
I want to be able to use binary search on sorted rectangles for speed.

If I do it like this it is too slow:

function get_rects_inside_rect (sequence rectangles, sequence big_rect)
    sequence rects_inside
    sequence rect
    rects_inside = {}
    for int i = 0 to length (rects) do
        rect = rects [i]
        if is_rect_partially_inside_rect (rect, big_rect)  then
            rects_inside = append (rects_inside, rect)
        end if
   end for
   return rects_inside
end function

A little faster it would be if I woluld somehow sort them by their left-x,
or something similar. Unclear to me right now.