A type of [[Binary Spatial Partitioning Tree]].
## Structure
- Internal Nodes store splitplanes geometry (part of object)
- Leaf Nodes store $E$ or $S$.
- Branches marked as $+,-$ indicating "outside" or "inside"
## Application
### [[Point]] Query
$\huge \mathcal O(\log n) $
Boolean [[Binary Spatial Partitioning Tree|BSP Point Query]]
```cpp
bool BSPPointQuery(BSPNode* bsp_mode, Point Q) {
if (bsp_node->leaf()) return (bsp_node == 'E') ? F : T;
auto side = point_plane(Q, bsp_node->splitting_plane, epsilon);
if (side != "front") // side == ("back" or "coplanar")
right = BSPPointQuery(bsp_node->right, Q);
if (side != "back") // side == ("front" or "coplanar")
left = BSPPointQuery(bsp_node->left, Q);
return (right or left);
}
```