OpenEuphoria

Re: sorting points or rectangles

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

Tone,

Ok, no tilted rectangles.

But let me get this straight:  is it only rectangles *wholly* inside another
rectangle you're concerned with, or is it any rectangle that is even
*partly* inside another that concerns you?  And do you need to know how much
of one is inside the other, perhaps for clipping purposes?

Dan

----- Original Message -----
From: <tone.skoda at siol.net>
To: "EUforum" <EUforum at topica.com>
Sent: Thursday, February 21, 2002 3:53 PM
Subject: Re: sorting points or rectangles


>
> 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>
> To: "EUforum" <EUforum at topica.com>
> Sent: Friday, February 22, 2002 3:44 AM
> Subject: Re: sorting points or rectangles
>
>
> > 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>
> > Sent: Thursday, February 21, 2002 4:31 PM
> > 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.
> > >
> > >
>
>
>