OpenEuphoria

Re: sorting points or rectangles

• Posted by tone.skoda at siol.net Feb 22, 2002
• 559 views

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