OpenEuphoria

Re: sorting points or rectangles

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

22/02/2002 11:31:18 AM, tone.skoda at siol.net wrote:

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

Not all rectangles are vertical/horizontal. Some are rotated like a diamond
shape.

     /\
     \/


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

I tried a variation of the algorithm you've got here and it was fairly fast on
my machine. I'm
getting 200,000 hits in 0.28 seconds. 

 ------------
 sequence testdata
 -- Generate some test data.
 function randrange(object range)
    if atom(range) then
        return rand(range)
    end if

    return rand(range[2]-range[1]+1) + range[1] - 1
 end function

 testdata = repeat({0,0,0,0}, 200000)

 for i = 1 to length(testdata) do
     testdata[i][1] = randrange({50,950})
     testdata[i][2] = randrange({50,950})
     testdata[i][3] = testdata[i][1] + randrange(100)
     testdata[i][4] = testdata[i][2] + randrange(100)
 end for


 -- See how many hits I make
 integer hi
 sequence BigRectangle 
 sequence hits
 atom startt

 startt = time()
 hits = repeat(0, length(testdata))
 hi = 0
 BigRectangle = {200,200,699,699}

 for i = 1 to length(testdata) do
    if testdata[i][1] <= BigRectangle[3] and
       testdata[i][2] <= BigRectangle[4] and
       testdata[i][3] >= BigRectangle[1] and
       testdata[i][4] >= BigRectangle[2] then
       hi += 1
       hits[hi] = i
    end if
 end for
 hits = hits[1..hi]
 printf(1, "Number of hits: %d in %g seconds \n", {length(hits), time()-startt})

 ------------


---------
Cheers,
Derek Parnell