Re: sorting points or rectangles
If you want to search only part of the list of rectangles, and
assuming you are prepared to initially sort/keep your list of
rectangles in order, the best I can think of is distance from (0,0).
I know it's root(x^2+y^2) but you don't need to calculate that root.
If your list of rectangles is built such that if top left=(x,y) then
x^2+y^2 is ascending for each entry in the table, then for a rectangle
(tx,ty) to (bx,by) you use a binary chop to find any entry in the
table with tx^2+ty^2<=x^2+y^2<=bx^2+by^2 & then run backwards and
forwards in the table to process any other possibles. Obviously you
need to repeat that check on the next/prior table entries to see if
you should continue or not, then check tx<=x<=bx and ty<=y<=by to see
if you actually want to do anything with it.
The advantage is only really there for small rectangles (which I
assume you have a fair few of) as they would only need to check a
small percentage of the rectangles in the table. The cost of course is
keeping that list in ascending order.
Pete
|
Not Categorized, Please Help
|
|
