pgl::ShapeTree< S, WeightFn > Class Template Reference

Static shape tree of bounded shapes. More...

#include <shapetree.hpp>

Public Types
using	ShapeType = S
using	WeightFunction = WeightFn
using	Rect = std::remove_cvref_t<decltype(std::declval<const S&>().bbox())>
using	PointType = typename Rect::PointType
using	NumberType = typename PointType::NumberType
using	WeightType = std::remove_cvref_t<std::invoke_result_t<const WeightFn&, const ShapeType&>>
using	value_type = ShapeType
using	size_type = std::size_t
using	const_iterator = typename std::vector<ShapeType>::const_iterator
using	const_reference = const ShapeType&

Public Member Functions
	ShapeTree ()=default
template<class Container>
	ShapeTree (const Container &shapes, std::size_t leafSize=defaultLeafSize, WeightFn weight=WeightFn{})
	Builds the tree from a container of shapes.
template<class Container>
	ShapeTree (const Container &shapes, WeightFn weight)
	Builds the tree from a container of shapes with a weight function.
std::size_t	size () const
	Returns the number of stored shapes.
bool	empty () const
	Returns whether the tree is empty.
const std::vector< ShapeType > &	shapes () const
	Returns the stored shapes in their internal order.
const_iterator	begin () const
	Returns an iterator to the first stored shape.
const_iterator	end () const
	Returns an iterator past the last stored shape.
const_iterator	cbegin () const
	Returns an iterator to the first stored shape.
const_iterator	cend () const
	Returns an iterator past the last stored shape.
void	insert (const ShapeType &shape)
	Inserts a shape without rebalancing the existing tree.
void	rebuild (std::size_t leafSize=0)
	Rebuilds the tree from the stored shapes, restoring its quality.
bool	erase (const ShapeType &shape)
	Removes one stored shape equal to shape.
template<class Q>
std::size_t	countIntersecting (const Q &q) const
	Counts the stored shapes intersecting a query shape.
template<class Q>
WeightType	sumIntersecting (const Q &q) const
	Sums the weights of the stored shapes intersecting a query shape.
template<class Q>
std::vector< ShapeType >	reportIntersecting (const Q &q) const
	Returns copies of the stored shapes intersecting a query shape.
template<class Q, class Fn>
bool	visitIntersecting (const Q &q, Fn fn) const
	Calls fn on each stored shape intersecting a query shape.
template<class Q>
bool	emptyIntersecting (const Q &q) const
	Returns whether no stored shape intersects a query shape.
template<class Q>
std::size_t	countContainedIn (const Q &q) const
	Counts the stored shapes contained in a query shape.
template<class Q>
WeightType	sumContainedIn (const Q &q) const
	Sums the weights of the stored shapes contained in a query shape.
template<class Q>
std::vector< ShapeType >	reportContainedIn (const Q &q) const
	Returns copies of the stored shapes contained in a query shape.
template<class Q, class Fn>
bool	visitContainedIn (const Q &q, Fn fn) const
	Calls fn on each stored shape contained in a query shape.
template<class Q>
bool	emptyContainedIn (const Q &q) const
	Returns whether no stored shape is contained in a query shape.
bool	has (const ShapeType &shape) const
	Returns whether a shape equal to shape is stored in the tree.
template<class Q>
const ShapeType &	nearestNeighbor (const Q &q) const
	Returns the stored shape nearest to a query shape.
template<class ResultNumber, class Q>
const ShapeType &	nearestNeighbor (const Q &q) const
template<class Q>
std::vector< ShapeType >	kNearestNeighbors (const Q &q, int k) const
	Returns up to k stored shapes nearest to a query shape.
template<class ResultNumber, class Q>
std::vector< ShapeType >	kNearestNeighbors (const Q &q, int k) const
template<class Q>
const ShapeType &	nearestNeighborL1 (const Q &q) const
	Returns the stored shape nearest to a query shape under the L1 (Manhattan) metric.
template<class ResultNumber, class Q>
const ShapeType &	nearestNeighborL1 (const Q &q) const
template<class Q>
const ShapeType &	nearestNeighborLInf (const Q &q) const
	Returns the stored shape nearest to a query shape under the LInf (Chebyshev) metric.
template<class ResultNumber, class Q>
const ShapeType &	nearestNeighborLInf (const Q &q) const
std::vector< Rect >	boundingBoxes () const
	Returns every node's subtree bounding box in pre-order.

Friends
Canvas &	operator<< (Canvas &canvas, const ShapeTree &tree)
	Draws every node's subtree bounding box to a canvas in pre-order.

Detailed Description

template<class S, class WeightFn = detail::EmptyWeightFn>
class pgl::ShapeTree< S, WeightFn >

Static shape tree of bounded shapes.

Template Parameters

S	Any shape type exposing bbox() (Point, Segment, Triangle, Rectangle, Convex, Polygon, ...). Infinite shapes such as Line, Ray and Halfplane have no finite bounding box and are not supported.
WeightFn	Callable mapping a ShapeType to a weight (any type with operator+ whose value-initialization is the additive identity). Defaults to a no-op returning an empty type, so weights are ignored unless a real function is supplied.

Member Typedef Documentation

const_iterator

template<class S, class WeightFn = detail::EmptyWeightFn>

using pgl::ShapeTree< S, WeightFn >::const_iterator = typename std::vector<ShapeType>::const_iterator

const_reference

template<class S, class WeightFn = detail::EmptyWeightFn>

using pgl::ShapeTree< S, WeightFn >::const_reference = const ShapeType&

NumberType

template<class S, class WeightFn = detail::EmptyWeightFn>

using pgl::ShapeTree< S, WeightFn >::NumberType = typename PointType::NumberType

PointType

template<class S, class WeightFn = detail::EmptyWeightFn>

using pgl::ShapeTree< S, WeightFn >::PointType = typename Rect::PointType

Rect

template<class S, class WeightFn = detail::EmptyWeightFn>

using pgl::ShapeTree< S, WeightFn >::Rect = std::remove_cvref_t<decltype(std::declval<const S&>().bbox())>

ShapeType

template<class S, class WeightFn = detail::EmptyWeightFn>

using pgl::ShapeTree< S, WeightFn >::ShapeType = S

size_type

template<class S, class WeightFn = detail::EmptyWeightFn>

using pgl::ShapeTree< S, WeightFn >::size_type = std::size_t

value_type

template<class S, class WeightFn = detail::EmptyWeightFn>

using pgl::ShapeTree< S, WeightFn >::value_type = ShapeType

WeightFunction

template<class S, class WeightFn = detail::EmptyWeightFn>

using pgl::ShapeTree< S, WeightFn >::WeightFunction = WeightFn

WeightType

template<class S, class WeightFn = detail::EmptyWeightFn>

using pgl::ShapeTree< S, WeightFn >::WeightType = std::remove_cvref_t<std::invoke_result_t<const WeightFn&, const ShapeType&>>

Constructor & Destructor Documentation

ShapeTree() [1/3]

template<class S, class WeightFn = detail::EmptyWeightFn>

pgl::ShapeTree< S, WeightFn >::ShapeTree ( )

default

ShapeTree() [2/3]

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Container>

pgl::ShapeTree< S, WeightFn >::ShapeTree ( const Container & shapes, std::size_t leafSize = defaultLeafSize, WeightFn weight = WeightFn{} )

inlineexplicit

Builds the tree from a container of shapes.

Template Parameters

Container

Range whose value type is convertible to ShapeType.

Parameters

shapes	Shapes to store.
leafSize	Maximum elements kept at a leaf before it is split.
weight	Weight function applied to each shape (defaults to a no-op).

ShapeTree() [3/3]

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Container>

pgl::ShapeTree< S, WeightFn >::ShapeTree ( const Container & shapes, WeightFn weight )

inlineexplicit

Builds the tree from a container of shapes with a weight function.

Uses the default leaf size.

Template Parameters

Container

Range whose value type is convertible to ShapeType.

Parameters

shapes	Shapes to store.
weight	Weight function applied to each shape.

Member Function Documentation

begin()

template<class S, class WeightFn = detail::EmptyWeightFn>

const_iterator pgl::ShapeTree< S, WeightFn >::begin ( ) const

inlinenodiscard

Returns an iterator to the first stored shape.

boundingBoxes()

template<class S, class WeightFn = detail::EmptyWeightFn>

std::vector< Rect > pgl::ShapeTree< S, WeightFn >::boundingBoxes ( ) const

inlinenodiscard

Returns every node's subtree bounding box in pre-order.

Visits the root, then the left subtree, then the right subtree, collecting each node's cached bounding box. The result is empty for an empty tree.

Returns

Vector of the node bounding boxes in pre-order.

cbegin()

template<class S, class WeightFn = detail::EmptyWeightFn>

const_iterator pgl::ShapeTree< S, WeightFn >::cbegin ( ) const

inlinenodiscard

Returns an iterator to the first stored shape.

cend()

template<class S, class WeightFn = detail::EmptyWeightFn>

const_iterator pgl::ShapeTree< S, WeightFn >::cend ( ) const

inlinenodiscard

Returns an iterator past the last stored shape.

countContainedIn()

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Q>

std::size_t pgl::ShapeTree< S, WeightFn >::countContainedIn ( const Q & q ) const

inlinenodiscard

Counts the stored shapes contained in a query shape.

A stored shape matches when it lies inside q (q.contains(element)). Note this is directional: q.contains(element) is not the same as element.contains(q).

Template Parameters

Q	Query shape type.

Parameters

q	Query shape.

Returns

Number of stored shapes contained in q.

countIntersecting()

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Q>

std::size_t pgl::ShapeTree< S, WeightFn >::countIntersecting ( const Q & q ) const

inlinenodiscard

Counts the stored shapes intersecting a query shape.

Subtrees whose bounding box does not meet the query are pruned; surviving candidates are tested with the exact intersects predicate.

Template Parameters

Q	Query shape type.

Parameters

q	Query shape.

Returns

Number of stored shapes intersecting q.

empty()

template<class S, class WeightFn = detail::EmptyWeightFn>

bool pgl::ShapeTree< S, WeightFn >::empty ( ) const

inlinenodiscard

Returns whether the tree is empty.

emptyContainedIn()

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Q>

bool pgl::ShapeTree< S, WeightFn >::emptyContainedIn ( const Q & q ) const

inlinenodiscard

Returns whether no stored shape is contained in a query shape.

Stops as soon as a contained shape is found.

Template Parameters

Q	Query shape type.

Parameters

q	Query shape.

Returns

true if no stored shape lies inside q, false otherwise.

emptyIntersecting()

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Q>

bool pgl::ShapeTree< S, WeightFn >::emptyIntersecting ( const Q & q ) const

inlinenodiscard

Returns whether no stored shape intersects a query shape.

Stops as soon as an intersecting shape is found.

Template Parameters

Q	Query shape type.

Parameters

q	Query shape.

Returns

true if no stored shape intersects q, false otherwise.

end()

template<class S, class WeightFn = detail::EmptyWeightFn>

const_iterator pgl::ShapeTree< S, WeightFn >::end ( ) const

inlinenodiscard

Returns an iterator past the last stored shape.

erase()

template<class S, class WeightFn = detail::EmptyWeightFn>

bool pgl::ShapeTree< S, WeightFn >::erase ( const ShapeType & shape )

inline

Removes one stored shape equal to shape.

Descends to the node owning an element equal to shape (pruning by the cached boxes), removes it, and on the way back up decrements each node's count, subtracts the removed weight, and recomputes bounding boxes from the removal point upward until a box is unchanged. A node left empty is detached from its parent and reclaimed. The element is then swap-removed from storage and the moved element's reference is updated, so shapes() stays compact; detached node slots are likewise swap-removed from the node array, so it does not grow under interleaved insert/erase.

Like insert, this does not rebalance, so the structure degrades over many removals; rebuild restores it. Only the element order in shapes() may change.

Parameters

shape

Shape to remove.

Returns

true if a matching shape was found and removed, false otherwise.

has()

template<class S, class WeightFn = detail::EmptyWeightFn>

bool pgl::ShapeTree< S, WeightFn >::has ( const ShapeType & shape ) const

inlinenodiscard

Returns whether a shape equal to shape is stored in the tree.

Tests exact membership with operator==, pruning any subtree whose cached box does not contain the shape's bounding box. This is distinct from the geometric *ContainedIn queries: it matches a stored shape identical to shape, not one geometrically inside a query region.

Parameters

shape

Shape to look for.

Returns

true if an equal shape is stored, false otherwise.

insert()

template<class S, class WeightFn = detail::EmptyWeightFn>

void pgl::ShapeTree< S, WeightFn >::insert ( const ShapeType & shape )

inline

Inserts a shape without rebalancing the existing tree.

The element is routed down the tree, keeping every visited node's box, count and weight sum up to date and preserving the invariant that the two child boxes of a node stay disjoint: a child takes the element only if its grown box remains disjoint from its sibling's; when both qualify the one enlarged least is chosen; when neither does the element is kept at the node. A leaf that overflows the leaf size is split with the best split.

Each insertion is O(height) and never reshapes the existing nodes, so the tree quality degrades over many insertions; rebuild from shapes() to restore it.

Parameters

shape

Shape to insert.

kNearestNeighbors() [1/2]

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class ResultNumber, class Q>

std::vector< ShapeType > pgl::ShapeTree< S, WeightFn >::kNearestNeighbors ( const Q & q, int k ) const

inlinenodiscard

kNearestNeighbors() [2/2]

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Q>

std::vector< ShapeType > pgl::ShapeTree< S, WeightFn >::kNearestNeighbors ( const Q & q, int k ) const

inlinenodiscard

Returns up to k stored shapes nearest to a query shape.

The result contains copies of the stored shapes in nondecreasing squared distance from q. If k exceeds the tree size, every stored shape is returned. A non-positive k or an empty tree produces an empty vector.

Template Parameters

ResultNumber	Explicit coordinate type of the squared distance.
Q	Query shape type.

Parameters

q	Query shape.
k	Maximum number of neighbors to return.

Returns

Up to k nearest stored shapes, nearest first.

nearestNeighbor() [1/2]

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class ResultNumber, class Q>

const ShapeType & pgl::ShapeTree< S, WeightFn >::nearestNeighbor ( const Q & q ) const

inlinenodiscard

nearestNeighbor() [2/2]

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Q>

const ShapeType & pgl::ShapeTree< S, WeightFn >::nearestNeighbor ( const Q & q ) const

inlinenodiscard

Returns the stored shape nearest to a query shape.

Finds the stored shape minimizing squaredDistance to q, using a branch-and-bound traversal: each node's cached bounding box gives a lower bound on the distance from q to anything in that subtree (via q.squaredDistance(Rectangle)), so subtrees that cannot hold a closer shape than the best found are pruned, and the nearer child box is descended first to tighten the bound early.

With no explicit result type, the concrete shape pair chooses its natural type: native arithmetic when the metric uses no division, division_result_t when it may produce a fraction, and double when a Disk makes an irrational result possible. An explicitly requested integral ResultNumber may truncate fractional distances; the box lower bound remains conservative in that case.

If a Disk is involved (as ShapeType or as Q), that leg may be irrational and is computed in double, then converted to the common comparison type. Other legs stay exact.

Precondition

The tree is non-empty. A reference to a default-constructed ShapeType is returned otherwise.

The reference points into the tree's own storage and stays valid until the tree is destroyed or modified (e.g. by insert).

Template Parameters

ResultNumber	Explicit coordinate type of the squared distance.
Q	Query shape type.

Parameters

q	Query shape.

Returns

The nearest stored shape.

nearestNeighborL1() [1/2]

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class ResultNumber, class Q>

const ShapeType & pgl::ShapeTree< S, WeightFn >::nearestNeighborL1 ( const Q & q ) const

inlinenodiscard

nearestNeighborL1() [2/2]

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Q>

const ShapeType & pgl::ShapeTree< S, WeightFn >::nearestNeighborL1 ( const Q & q ) const

inlinenodiscard

Returns the stored shape nearest to a query shape under the L1 (Manhattan) metric.

Same branch-and-bound traversal as nearestNeighbor, but minimizes distanceL1 instead of squaredDistance.

Precondition

The tree is non-empty. A reference to a default-constructed ShapeType is returned otherwise.

Template Parameters

ResultNumber	Explicit coordinate type of the distance.
Q	Query shape type.

Parameters

q	Query shape.

Returns

The stored shape nearest to q under the L1 metric.

nearestNeighborLInf() [1/2]

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class ResultNumber, class Q>

const ShapeType & pgl::ShapeTree< S, WeightFn >::nearestNeighborLInf ( const Q & q ) const

inlinenodiscard

nearestNeighborLInf() [2/2]

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Q>

const ShapeType & pgl::ShapeTree< S, WeightFn >::nearestNeighborLInf ( const Q & q ) const

inlinenodiscard

Returns the stored shape nearest to a query shape under the LInf (Chebyshev) metric.

Same branch-and-bound traversal as nearestNeighbor, but minimizes distanceLInf instead of squaredDistance.

Precondition

The tree is non-empty. A reference to a default-constructed ShapeType is returned otherwise.

Template Parameters

ResultNumber	Explicit coordinate type of the distance.
Q	Query shape type.

Parameters

q	Query shape.

Returns

The stored shape nearest to q under the LInf metric.

rebuild()

template<class S, class WeightFn = detail::EmptyWeightFn>

void pgl::ShapeTree< S, WeightFn >::rebuild ( std::size_t leafSize = 0 )

inline

Rebuilds the tree from the stored shapes, restoring its quality.

insert never reshapes existing nodes, so the structure degrades over many insertions; this discards the node structure and rebuilds it from scratch (the same way the constructor does) over the current shapes, leaving the stored shapes and their order unchanged.

Parameters

leafSize

Maximum elements kept at a leaf before it is split. Pass 0 to keep the current leaf size.

reportContainedIn()

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Q>

std::vector< ShapeType > pgl::ShapeTree< S, WeightFn >::reportContainedIn ( const Q & q ) const

inlinenodiscard

Returns copies of the stored shapes contained in a query shape.

Template Parameters

Q	Query shape type.

Parameters

q	Query shape.

Returns

Vector of the stored shapes contained in q.

reportIntersecting()

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Q>

std::vector< ShapeType > pgl::ShapeTree< S, WeightFn >::reportIntersecting ( const Q & q ) const

inlinenodiscard

Returns copies of the stored shapes intersecting a query shape.

Subtrees whose bounding box does not meet the query are pruned; subtrees fully inside the query are collected without per-element tests.

Template Parameters

Q	Query shape type.

Parameters

q	Query shape.

Returns

Vector of the stored shapes intersecting q.

shapes()

template<class S, class WeightFn = detail::EmptyWeightFn>

const std::vector< ShapeType > & pgl::ShapeTree< S, WeightFn >::shapes ( ) const

inlinenodiscard

Returns the stored shapes in their internal order.

size()

template<class S, class WeightFn = detail::EmptyWeightFn>

std::size_t pgl::ShapeTree< S, WeightFn >::size ( ) const

inlinenodiscard

Returns the number of stored shapes.

sumContainedIn()

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Q>

WeightType pgl::ShapeTree< S, WeightFn >::sumContainedIn ( const Q & q ) const

inlinenodiscard

Sums the weights of the stored shapes contained in a query shape.

Template Parameters

Q	Query shape type.

Parameters

q	Query shape.

Returns

Sum of weights over the stored shapes contained in q.

sumIntersecting()

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Q>

WeightType pgl::ShapeTree< S, WeightFn >::sumIntersecting ( const Q & q ) const

inlinenodiscard

Sums the weights of the stored shapes intersecting a query shape.

Like countIntersecting, but accumulates the weight function instead of counting. Subtrees fully inside the query contribute their cached weight sum without descending.

Template Parameters

Q	Query shape type.

Parameters

q	Query shape.

Returns

Sum of weights over the stored shapes intersecting q.

visitContainedIn()

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Q, class Fn>

bool pgl::ShapeTree< S, WeightFn >::visitContainedIn ( const Q & q, Fn fn ) const

inline

Calls fn on each stored shape contained in a query shape.

If fn returns bool, returning true stops the traversal immediately; a void-returning fn always visits every match.

Template Parameters

Q	Query shape type.
Fn	Callable invocable with const ShapeType&, returning void or bool (return true to stop).

Parameters

q	Query shape.
fn	Function to call on each contained shape.

Returns

true if fn requested an early stop, false otherwise.

visitIntersecting()

template<class S, class WeightFn = detail::EmptyWeightFn>

template<class Q, class Fn>

bool pgl::ShapeTree< S, WeightFn >::visitIntersecting ( const Q & q, Fn fn ) const

inline

Calls fn on each stored shape intersecting a query shape.

Shapes are visited as they are found during traversal. Subtrees disjoint from the query are pruned; subtrees fully inside it are visited without per-element tests.

If fn returns bool, returning true stops the traversal immediately; a void-returning fn always visits every match.

Template Parameters

Q	Query shape type.
Fn	Callable invocable with const ShapeType&, returning void or bool (return true to stop).

Parameters

q	Query shape.
fn	Function to call on each intersecting shape.

Returns

true if fn requested an early stop, false otherwise.

Friends And Related Symbol Documentation

operator<<

template<class S, class WeightFn = detail::EmptyWeightFn>

Canvas & operator<< ( Canvas & canvas, const ShapeTree< S, WeightFn > & tree )

friend

Draws every node's subtree bounding box to a canvas in pre-order.

Sends each box returned by boundingBoxes to the canvas with its current style.

Parameters

canvas	Destination canvas.
tree	Tree whose node boxes are drawn.

Returns

The canvas.