   2d Rectangle searching and filtering rountine
  HiI am updating some 20 year old code in Autocad lisp that takes rectangles thatsurround text items and searches for text rectangles that overlap and filters out text based on a third elevation criteria.The raw data comes from scans of the sea floor and there can be 1000's of text rectangles. The existing rountine is just a loop that takes hours to run for large datasets.I found this discussion in this forum from a couple of years ago where an r-tree is suggested as a good solution for a similar problem. Is this still the case and does anyone have some vb.net code they are will to share. http://www.gamedev.net/community/forums/topic.asp?topic_id=445256RegardsJustin Ralston   
  You probably know how to test for rectangle to rectangle intersection at a conceptual level? It is just a few comparisons of coordinates.As you know, the brute force approach is to test all the rectangles against each other. However, this is very inefficient since the number of comparisons is n*n, that is, the number of calculations rises to 2nd power with the number of rectangles.A good approach to optimizing the search would be to divide the search space to recursively smaller rectangles (r-tree), and store the data rectangles by their containing search space rectangle. This way, you only need to test the intersections of rectangles that you know are near each other. In case a data rectangle crosses the boundary of a search space rectangle, just consider the adjacent search space rectangle too.The code is tedious to write, so I won't do it here. However, the concept outlined above should get you started.A common spatial partitioning scheme used in games, "quadtree", is very similar to what you want. There is plenty of literature about it on the net. Usually, quadtrees are used to store triangle mesh partitions but there is really no reason why it wouldn't work on rectangle lists just as well.The elevation comparing is very simple, once you've found the 2d overlaps. I think that in your case, the 3rd dimension is so sparse that it needn't be optimized by a tree (the tree logic would take longer than just comparing the values directly).   ;  You can also try a kd-tree for the nearest-neighbour-search. Take a look into the Wikipedia-page regarding kd-trees.With best regards,Kimmi   