Spatial Data Structures - Computer Graphics: Principles and Practice - page 1086

Spatial partitioning

g

b

(16, 6)

(3, 6)

(1, 4)

a

(12, 3)

e

c

d

(13, 1)

(7.5, 2.5)

(8, 2)

f

Pointer structure

a b

g

e f

c d

Figure 37.9: A depiction of a 2D binary space partition tree (BSP) as partitions (black
lines) of values with associated keys (red disks). The thickness of the partition line repre-
sents the tree depth of that partition node in the tree; the root is the thickest.

Listing 37.12: A C++ implementation of a binary space partition tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

template < class Value, class Bounds = PrimitiveKeyTrait<Value> >
class BSPTree {
class Node {
public :
Plane partition;

/ * Values at this node * /
List<Value, Bounds> valueArray;

Node * negativeHalfSpace;
Node * positiveHalfSpace;

};

Node * root;

...

};