# Hurricane Documentation

# Hurricane VLSI Database

List of all members | Public Member Functions
Hurricane::QuadTree Class Reference

QuadTree description (API) More...

## Public Member Functions

| QuadTree ()
| ~QuadTree ()
const Box & | getBoundingBox () const
Gos | getGos () const
Gos | getGosUnder (const Box &area, DbU::Unit threshold=0) const
bool | isEmpty () const
void | insert (Go *go)
void | remove (Go *go)

## Detailed Description

QuadTree description (API)

# Introduction

Quadtrees are efficient hierarchical data structures for the geometrical access of gos.

Important: You must not change the bounding box of an object already
  present in the quadtree, because its localization within the tree depends on it. Therefore, if an object is modified, you must in a firts time remove it from the quadtree, apply the changes then re-insert it in the quadtree, at the right place which depends of its new bounding box.

## Constructor & Destructor Documentation

## ◆ QuadTree()

Hurricane::QuadTree::QuadTree | ( |  | ) |

Default constructor : the quadtree is initially empty (objects will be inserted or removed on demand).

## ◆ ~QuadTree()

Hurricane::QuadTree::~QuadTree | ( |  | ) |

Destroys the quadtree and its sub-quadtrees but doesn't touch to the contained objects, they will ibe only detached from their respective quadtree nodes.

## Member Function Documentation

## ◆ getBoundingBox()

Box Hurricane::QuadTree::getBoundingBox | ( |  | ) | const

Returns: the quadtree bounding box, that is the minimal bounding box including all objects of the quad tree (this bounding box is updated dynamically).

Referenced by Hurricane::Slice::getBoundingBox().

## ◆ getGos()

Gos Hurricane::QuadTree::getGos | ( |  | ) | const

Returns: the collection of graphical objects contained in the quadtree.

Referenced by Hurricane::Slice::getGos().

## ◆ getGosUnder()

Gos Hurricane::QuadTree::getGosUnder | ( | const Box & | area,
|  | DbU::Unit | threshold = `0`
| ) |  | const

Returns: the collection of graphical objects contained in the quadtree and whose bounding box intersects the rectangular region defined by `<area>`.

## ◆ isEmpty()

bool Hurricane::QuadTree::isEmpty | ( |  | ) | const

inline

Returns: true if the quadtree doesn't contain any object, else false.

## ◆ insert()

void Hurricane::QuadTree::insert | ( | Go * | go | ) |

inserts the graphic object within the quadtree (if not yet inserted).

Caution: If the graphic object pointer is NULL an exception is thrown.

Remarks
  When the number of objects contained in a quadtree leaf is greater than some threshold, this leaf is split into four balanced sub-quadtrees. This recursive division provides a faster access even for very large quadtrees (to the detriment of some memory loss).

## ◆ remove()

void Hurricane::QuadTree::remove | ( | Go * | go | ) |

removes the object from the quadtree.

Caution: If the graphic object is NULL an exception is thrown.

Remarks
  When the number of objects included in the quadtree goes below an other threshold, the inverse behaviour happens : the sub-quadtrees are deleted and the contained objects are taken in charge by this quadtree node (and memory is released to the system).

The documentation for this class was generated from the following files:

- QuadTree.h
- QuadTree.dox