Point Quad Tree

API Reference

template<typename _Key, typename _Value>
class point_quad_tree

Public Types

typedef _Key key_type

typedef _Value value_type

typedef size_t size_type

typedef ::std::vector<value_type> data_array_type

Public Functions

point_quad_tree()

point_quad_tree(const point_quad_tree &r)

~point_quad_tree()

void insert(key_type x, key_type y, value_type data)

Insert a new data at specified coordinates. It overwrites existing data in case one exists at the specified coordinates.

Parameters:

• x – x coordinate of new data position

• y – y coordinate of new data position

• data – data being inserted at the specified coordinates.

void search_region(key_type x1, key_type y1, key_type x2, key_type y2, data_array_type &result) const

Perform region search (aka window search), that is, find all points that fall within specified rectangular region. The boundaries are inclusive.

Parameters:

• x1 – left coordinate of the search region

• y1 – top coordinate of the search region

• x2 – right coordinate of the search region

• y2 – bottom coordinate of the search region

• result – this array will contain all data found without specified region.

search_results search_region(key_type x1, key_type y1, key_type x2, key_type y2) const

Perform region search (aka window search), that is, find all points that fall within specified rectangular region. The boundaries are inclusive.

Parameters:

• x1 – left coordinate of the search region

• y1 – top coordinate of the search region

• x2 – right coordinate of the search region

• y2 – bottom coordinate of the search region

Returns:

search result object containing all data found within the specified region.

value_type find(key_type x, key_type y) const

Find data at specified coordinates. If no data exists at the specified coordinates, this method throws a point_quad_tree::data_not_found exception.

Parameters:

• x – x coordinate

• y – y coordinate

Returns:

data found at the specified coordinates.

void remove(key_type x, key_type y)

Remove data from specified coordinates. This method does nothing if no data exists at the specified coordinates.

Parameters:

• x – x coordinate

• y – y coordinate

void swap(point_quad_tree &r)

Swap the internal state with another instance.

Parameters:

r – another instance to swap internals with.

void clear()

Remove all stored data.

bool empty() const

Check whether or not the container is empty.

Returns:

bool true if empty, false otherwise.

size_t size() const

Get the number of stored data.

Returns:

the number of data currently stored in the container.

node_access get_node_access() const

Get read-only access to the internal quad node tree.

Returns:

root node

point_quad_tree &operator=(const point_quad_tree &r)

bool operator==(const point_quad_tree &r) const

inline bool operator!=(const point_quad_tree &r) const

class data_not_found : public std::exception

class node_access

Node wrapper to allow read-only access to the internal quad node structure.

Public Functions

inline node_access northeast() const

inline node_access northwest() const

inline node_access southeast() const

inline node_access southwest() const

inline value_type data() const

inline key_type x() const

inline key_type y() const

inline operator bool() const

inline bool operator==(const node_access &r) const

inline node_access()

inline ~node_access()

struct point

Public Functions

inline point(key_type _x, key_type _y)

inline point()

Public Members

key_type x

key_type y

class search_results

Public Functions

inline search_results()

inline search_results(const search_results &r)

inline search_results::const_iterator begin()

inline search_results::const_iterator end()

class const_iterator

Public Types

typedef std::pair<point, parent_value_type> value_type

typedef value_type *pointer

typedef value_type &reference

typedef ptrdiff_t difference_type

typedef ::std::bidirectional_iterator_tag iterator_category

Public Functions

inline const_iterator(res_nodes_ptr &ptr)

inline const_iterator(const const_iterator &r)

inline const_iterator &operator=(const const_iterator &r)

inline bool operator==(const const_iterator &r) const

inline bool operator!=(const const_iterator &r) const

inline const value_type &operator*() const

inline const value_type *operator->() const

inline const value_type *operator++()

inline const value_type *operator--()

Friends

friend class point_quad_tree< _Key, _Value >::search_results