shapetree.hpp File Reference

Static 2D shape tree over any bounded shape (one exposing bbox()). More...

#include "algorithm/closestpair.hpp"
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <type_traits>
#include <utility>
#include <vector>

Go to the source code of this file.

Classes
class	pgl::ShapeTree< S, WeightFn >
	Static shape tree of bounded shapes. More...

Namespaces
namespace	pgl

Functions
template<class Container>
	pgl::ShapeTree (const Container &) -> ShapeTree< typename Container::value_type >
template<class Container>
	pgl::ShapeTree (const Container &, std::size_t) -> ShapeTree< typename Container::value_type >
template<class Container, class WeightFn>
	pgl::ShapeTree (const Container &, std::size_t, WeightFn) -> ShapeTree< typename Container::value_type, WeightFn >
template<class Container, class WeightFn> requires (!std::is_integral_v<WeightFn>)
	pgl::ShapeTree (const Container &, WeightFn) -> ShapeTree< typename Container::value_type, WeightFn >

Detailed Description

Static 2D shape tree over any bounded shape (one exposing bbox()).

The tree stores shapes by value and is built once from a container. Space is split by a coordinate value. At each node the axis and split value are chosen adaptively to minimize maxChild + straddlers, balancing the children while keeping few elements stuck at the node; a set of long horizontal segments is thus split horizontally rather than uselessly along their length. Elements lying strictly on one side of the split descend into that child; elements whose bounding box straddles the split value stay at the node itself, so every element is stored exactly once. Each node caches the union bounding box of its whole subtree, allowing queries to prune subtrees with exact integer rectangle predicates. Over an arbitrary-precision coordinate type, where that box test is itself a cross multiplication of big integers, every box is shadowed by an outward-rounded double one and the cheap test runs first; a shadow that misses the query proves the exact box does too.