Binary Space Partitioning Trees
A binary space-partitioning (BSP) tree is used to divide the canvas into sections that can be quickly searched. Every top-level component in a model gets placed into the tree. Then, the tree can be quickly searched to determine what components contain a point, or are within or intersect a rectangle of space.
Figure 66 – Binary space positioning (BSP) class hierarchy
This class provides the interface for the binary space-partitioning tree. It has a pointer to the root level node of the tree and methods to add or remove components from the tree. This class can also be given a section or point of space and it returns all of the top-level components in that space.
This class represents one node in the BSP tree. A node contains pointers to its child nodes that further divide the space represented by the tree. Component information is usually stored on the leaves of the tree, providing an excellent level of granularity.
BSP rectangles are derived from CRect and add the capability to store a pointer to a component. These rectangles are what are actually stored in a BSP tree, and represent a piece of the bounding box of a component.