# Documentation on 2D space partitioning

I am looking for documentation that explains the different kinds of (well the major ones anyway) 2D space partitioning algorithms & data structures.

Any pointers besides 'Google it and sift through hundreds of papers'. A book perhaps?

-
Do you have any specific algorithms and data structures you are interested in? What kind of game are you making? – NoobsArePeople2 Dec 28 '11 at 23:18
I simply wanted to digest the main ones and understand the strengths and trade-offs. I am not making a game, but know that this is the right place to ask this question :) – r1x Dec 28 '11 at 23:38

I've got this sort of info spread over many books on my bibliography, but I'm currently away from them. But from what I could gather up from memory and browsing through the table of contents online, I recall the following books:

3D Math Primer for Graphics and Game Development 1st Edition or Mathematics for 3D Game Programming & Computer Graphics

or

Chapter 16 (Visibility Determination) of 3D Math Primer for Graphics and Game Development 1st Edition (strangely the authors seem to have removed this section from the second edition of the book) covers the most common techniques (i.e. grid system, quadtree and octree, bsp trees, portal occlusion). The book is really good, although perhaps not the best of its kind.

I've seen Mathematics for 3D Game Programming & Computer Graphics being mentioned very often, but unfortunately haven't gotten my hands on it yet. From the table of contents, it seems to cover space partitioning algorithms too. Not sure how they compare against each other.

Naturally, the focus of these books is on the math. And although the title says 3D, they are also quite relevant for 2D programming.

Real-time Rendering 3rd Edition

Chapter 14 (Acceleration Algorithms) of Real-time Rendering also covers most of these topics, and this is actually my favorite general graphics programming book ever. Very comprehensive but I don't recall how much it covered this particular subject.

The focus of this book is on the graphics theory, but it covers such a large amount of topics that I could hardly find a better recommendation for anyone interested in the field.

Game Programming Gems

The previous books were mostly theoretical though. For more specific and practical advice, I've read several articles on the subject scattered throughout the Game Programming Gems series. Some that come to mind:

• Octree Construction - Game Programming Gems 1
• Loose Octrees - Game Programming Gems 1
• Sphere Trees for Fast Visibility Culling, Ray Tracing, and Range Searching - Game Programming Gems 2
• A High-Performance Tile-based Line-of-Sight and Search System - Game Programming Gems 2
• Sphere Trees for Speedy BSPs - Game Programming Gems 5
• Spatial Partitioning Using an Adaptive Binary Tree - Game Programming Gems 6
• BSP Techniques - Game Programming Gems 6
-
Theory is actually what I'm after. Hopefully explanations that involve linear algebra & discrete geometry. – r1x Dec 28 '11 at 23:51
Then I believe one of the math books might be the better choice, although you might be disappointed at how little coverage there really is (at least I remember it being rather simple). – David Gouveia Dec 29 '11 at 4:22
Therefore you might benefit from combining that with some practical (and more advanced) examples too. – David Gouveia Dec 29 '11 at 4:29
Thanks for your detailed answer ! – r1x Dec 29 '11 at 7:26