A simple Erlang quadtree implementation.
erlquad is a straightforward implementation of
quadtrees, supporting both
bounding-box outlines and precise coordinates for small enough objects.
It exposes functions for fetching, folding and testing (with a boolean predicate) particular areas of interest, as well as all contained objects. Deep-list variants of the fetching functions are also provided for when there is no need to concatenate the intermediate results.
Buckets have unlimited capacity and depth is fixed on initialization. See the README for an overview and examples.
Summary
Functions
Returns the objects that may fall within the rectangle delimited by Left,
Bottom, Right and Top.
Returns true if Predicate holds for any object that may fall within the
rectangle delimited by Left, Bottom, Right and Top, false otherwise.
Like area_query/5, but returns a nested list mirroring the tree structure,
avoiding the cost of concatenating the intermediate results.
Folds FoldFun over the objects that may fall within the rectangle delimited by
Left, Bottom, Right and Top, starting from FoldAcc0.
Creates an empty quadtree covering the rectangle delimited by Left, Bottom,
Right and Top, recursively subdivided Depth levels deep.
Adds Objects to the tree, using GetOutlineFun to obtain each object's
outline — either precise coordinates/0 or a bounding box/0.
Returns every object in the tree as a flat list.
Returns true if Predicate holds for any object in the tree, false
otherwise.
Like objects_all/1, but returns a nested list mirroring the tree structure,
avoiding the cost of concatenating the intermediate results.
Folds FoldFun over every object in the tree, starting from FoldAcc0.
Types
Functions
-spec area_query(Left :: number(), Bottom :: number(), Right :: number(), Top :: number(), QNode :: erlquad_node()) -> Objects :: [term()].
Returns the objects that may fall within the rectangle delimited by Left,
Bottom, Right and Top.
The result is a conservative superset: no matching object is ever omitted, but objects sharing a tree node with the queried area may also be included, so callers that need exact results should apply their own filtering.
-spec area_query_any(Predicate :: predicate(), Left :: number(), Bottom :: number(), Right :: number(), Top :: number(), QNode :: erlquad_node()) -> boolean().
Returns true if Predicate holds for any object that may fall within the
rectangle delimited by Left, Bottom, Right and Top, false otherwise.
As with area_query/5, the tested objects are a conservative superset of those
strictly within the area.
-spec area_query_deep(Left :: number(), Bottom :: number(), Right :: number(), Top :: number(), QNode :: erlquad_node()) -> DeepObjectList :: [term(), ...].
Like area_query/5, but returns a nested list mirroring the tree structure,
avoiding the cost of concatenating the intermediate results.
-spec area_query_fold(FoldFun :: fold_fun(), FoldAcc0 :: term(), Left :: number(), Bottom :: number(), Right :: number(), Top :: number(), QNode :: erlquad_node()) -> FoldAccN :: term().
Folds FoldFun over the objects that may fall within the rectangle delimited by
Left, Bottom, Right and Top, starting from FoldAcc0.
As with area_query/5, the visited objects are a conservative superset of those
strictly within the area.
-spec new(Left :: number(), Bottom :: number(), Right :: number(), Top :: number(), Depth :: non_neg_integer()) -> erlquad_node().
Creates an empty quadtree covering the rectangle delimited by Left, Bottom,
Right and Top, recursively subdivided Depth levels deep.
-spec objects_add(Objects :: [term()], GetOutlineFun :: object_outline_fun(), QNode :: erlquad_node()) -> erlquad_node().
Adds Objects to the tree, using GetOutlineFun to obtain each object's
outline — either precise coordinates/0 or a bounding box/0.
-spec objects_all(QNode :: erlquad_node()) -> Objects :: [term()].
Returns every object in the tree as a flat list.
-spec objects_any(Precicate :: predicate(), QNode :: erlquad_node()) -> boolean().
Returns true if Predicate holds for any object in the tree, false
otherwise.
-spec objects_deep_all(QNode :: erlquad_node()) -> ObjectsDeepList :: [term(), ...].
Like objects_all/1, but returns a nested list mirroring the tree structure,
avoiding the cost of concatenating the intermediate results.
-spec objects_fold(FoldFun :: fold_fun(), FoldAcc0 :: term(), QNode :: erlquad_node()) -> FoldAccN :: term().
Folds FoldFun over every object in the tree, starting from FoldAcc0.