OpenEuphoria

Re: sorting points or rectangles

• Posted by Dan Moyer <DANIELMOYER at prodigy.net> Feb 21, 2002
• 555 views

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

----- Original Message -----
From: <tone.skoda at siol.net>
To: "EUforum" <EUforum at topica.com>
Subject: Re: sorting points or rectangles


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