Class AABBtree

Class Documentation

class G2lib::AABBtree

Class to build and manage an AABB tree (Axis-Aligned Bounding Box Trees)

The class provides 2-dimensional aabb-tree construction and search for arbitrary collections of spatial objects. These tree-based indexing structures are useful when seeking to implement efficient spatial queries, reducing the complexity of intersection tests between collections of objects.

Public Types

typedef BBox const *PtrBBox
typedef AABBtree *PtrAABB
typedef pair<PtrBBox, PtrBBox> PairPtrBBox
typedef vector<PtrBBox> VecPtrBBox
typedef vector<PairPtrBBox> VecPairPtrBBox

Public Functions

AABBtree()

Create an empty AABB tree.

~AABBtree()

destroy the stored AABB tree.

void clear()

Initialized AABB tree.

bool empty() const

Check if AABB tree is empty.

inline void bbox(real_type &xmin, real_type &ymin, real_type &xmax, real_type &ymax) const

Get the Bounding Box of the whole AABB tree

Parameters

  • xmin – [in] x-minimimum box coordinate

  • ymin – [in] y-minimimum box coordinate

  • xmax – [in] x-maximum box coordinate

  • ymax – [in] y-maximum box coordinate

void build(vector<PtrBBox> const &bboxes)

Build AABB tree given a list of bbox

void print(ostream_type &stream, int level = 0) const

Pretty print the AABB tree

template<typename COLLISION_fun>
inline bool collision(AABBtree const &tree, COLLISION_fun ifun, bool swap_tree = false) const

Check if two AABB tree collide

Parameters

  • tree – [in] an AABB tree that is used to check collision

  • ifun – [in] function the check if the contents of two bbox (curve) collide

  • swap_tree – [in] if true exchange the tree in computation

Returns

true if the two tree collides

void intersect(AABBtree const &tree, VecPairPtrBBox &intersectionList, bool swap_tree = false) const

Compute all the intersection of AABB trees.

Parameters

  • tree – [in] an AABB tree that is used to check collision

  • intersectionList – [out] list of pair bbox that overlaps

  • swap_tree – [in] if true exchange the tree in computation

void min_distance(real_type x, real_type y, VecPtrBBox &candidateList) const

Select all the bboxes candidate to be at minimum distance.

Parameters

  • x – [in] x-coordinate of the point

  • y – [in] y-coordinate of the point

  • candidateList – [out] candidate list