I have a huge rectangular region that I divided up into smaller rectangles. I used a binary space partitioning algorithm to do this task (details can be found at http://doryen.eptalys.net/articles/bsp-dungeon-generation/, up until 'Building the dungeon'). However, after dividing up the space, I want to, for each individual rectangle leaf in the tree, determine all the rectangle leaves that share an edge, or any part of an edge, with it (obviously, this will always include that leaf's sibling, but may also include other nodes that could very well be on the other side of the tree). For example, in the picture http://doryen.eptalys.net/data/articles/dungeon_bsp3-medium.jpg, the rectangle in the upper left corner is neighbored by the rectangles directly east, south, and southeast of it. Assuming that I can use the list of rectangle leaves without considering the structure of the underlying tree or work directly on the tree (possibly as it's being built?), whichever works best, does anyone have any ideas as to an efficient algorithm to perform this task faster than simply checking all pairs of rectangles?
Algorithm to find neighboring rectangles?
You can query neighbors from the tree in average O(log n) time where n is the number of rectangles in your world, assuming the tree is built as specified in the link, by starting at the root node and recursing down a child if and only if the child's bounding box touches your rectangle (this is basically asking the tree for all leaves which intersect/touch your rectangle, and since all the leaves are disjoint by construction this'll give you the neighbors). You can then iterate over every rectangle using the above to build an adjacency data structure. I would imagine there is a clever method for doing this more efficiently at the same time as building the tree, but I cannot think of anything at the moment.
I am assuming your data is static, so that all that stuff can be precomputed once per level and the precomputation step just needs to be reasonably fast. If your data is dynamic and you have a medium amount of rectangles, say, up to a few thousand or so, I would recommend to either use optimized brute force (good cache coherency, SIMD rect-rect intersections are your best friend) or at least flatten your tree into a cache-friendly array as following pointers all over the heap is sure to destroy your performance. If you have way more rectangles than that, you'll probably need something special.
I am assuming your data is static, so that all that stuff can be precomputed once per level and the precomputation step just needs to be reasonably fast. If your data is dynamic and you have a medium amount of rectangles, say, up to a few thousand or so, I would recommend to either use optimized brute force (good cache coherency, SIMD rect-rect intersections are your best friend) or at least flatten your tree into a cache-friendly array as following pointers all over the heap is sure to destroy your performance. If you have way more rectangles than that, you'll probably need something special.
Author
Hmm, that's a pretty good idea. I was trying to tackle the problem from the approach of using a sweep line method, but couldn't figure out if I could use the BSP tree structure to improve the performance. The rectangle data is indeed static, and never changes, so I guess I'd agree that it wouldn't be too bad if this step takes a bit longer than the next step in the process. I'll try out what you suggested, thanks!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
