Re: sorting points or rectangles
- Posted by Dan Moyer <DANIELMOYER at prodigy.net> Feb 23, 2002
- 533 views
Colin, I now see that you are in fact finding *all* corners that could be inside the target rectangle, using the "negative" logic of excluding any that *can't* be inside. Nice! Should be faster, which is what Tone needs. Dan ----- Original Message ----- From: <cetaylor at compuserve.com> To: "EUforum" <EUforum at topica.com> Subject: Re: sorting points or rectangles > > Rectangles oriented parallel to the x-y axes are normally defined by only 2 > points {upper-left xy, lower-right xy}. To determine if a rectangle falls > within another, it is quicker to eliminate those that aren't inside, as > shown below: > > Colin Taylor > > -- start code: > > -- TEST TO SEE IF ANY RECTANGLE IS AT LEAST PARTLY INSIDE A BIGGER ONE: > -- for rectangles each defined by 2 corner points in this order: > -- upper-left xy, lower-right xy: {{ulx,uly}, {lrx,lry}} > > include misc.e > > constant ul = 1, lr = 2, x = 1, y = 2 > > sequence BigRectangle, testRects, aHit > integer hit > atom TotHits, TotTime, stime, etime > BigRectangle = {{200,200},{699,699}} > testRects = repeat({{0,0},{0,0}}, 20000) > aHit = {} > hit = 0 > TotHits = 0 > TotTime = 0 > > function randrange(object range) > -- borrowed following two from Derek, & then altered 2nd: > if atom(range) then > return rand(range) > end if > return rand(range[2]-range[1]+1) + range[1] - 1 > end function > > procedure makeTestData() > -- generate some test data. > for i = 1 to length(testRects) do > testRects[i][ul] = {randrange({50,950}), randrange({50,950})} > testRects[i][lr][x] = testRects[i][ul][x] + randrange(100) > testRects[i][lr][y] = testRects[i][ul][y] + randrange(100) > end for > end procedure > > function IsPartlyInside(sequence OuterRect, sequence PossPrtlyInside) > -- determines if a rectangle is at least partly inside the big one: > if PossPrtlyInside[lr][x] <= OuterRect[ul][x] then -- to left > return 0 > elsif PossPrtlyInside[ul][x] >= OuterRect[lr][x] then -- to right > return 0 > elsif PossPrtlyInside[lr][y] <= OuterRect[ul][y] then -- above > return 0 > elsif PossPrtlyInside[ul][y] >= OuterRect[lr][y] then -- below > return 0 > else > return 1 > end if > end function > > procedure doAtest() > makeTestData() -- make new test rectangles each test > hit = 0 > aHit = {} > > stime = time() > for n = 1 to length(testRects) do > if IsPartlyInside(BigRectangle, testRects[n]) then > hit += 1 > aHit &= {testRects[n]} -- save coords of partly inside > rectangle > end if > end for > etime = time() - stime > > puts(1, "\nhits= " & sprint(hit) & " in " & sprint(etime) & " > seconds\n") > puts(1, "length of hits sequence: " & sprint(length(aHit)) & "\n") > puts(1, "big rectangle: ") > print(1, BigRectangle) > puts(1, "\na smaller rectangle: ") > print(1, aHit[1]) -- just show one of them > puts(1, "\n") > > TotTime += etime > TotHits += hit > end procedure > > for m = 1 to 10 do > doAtest() > end for > > puts(1, "\naverage of " & sprint(floor(TotHits/10)) & " hits in average of " > & sprint(TotTime/10) & " seconds,\nout of 10 trials of 20,000 rectangles > each trial.") > > -- end code > > ----- Original Message ----- > Subject: Re: sorting points or rectangles > > > > Tone, > > > > Ok, on the assumption that you *do* want to find any rectangle that is > even > > partly within another (all oriented parallel to x-y axes), the following > > should do it ... > > > >