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.

point_quad_tree<_Key, _Value>::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.

Return
search result object containing all data found within the specified region.
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

point_quad_tree<_Key, _Value>::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.

Return
data found at the specified coordinates.
Parameters
  • x: x coordinate
  • y: y coordinate

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.

Return
bool true if empty, false otherwise.

size_t size() const

Get the number of stored data.

Return
the number of data currently stored in the container.

point_quad_tree<_Key, _Value>::node_access get_node_access() const

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

Return
root node

point_quad_tree<_Key, _Value> &operator=(const point_quad_tree &r)
bool operator==(const point_quad_tree &r) const
bool operator!=(const point_quad_tree &r) const
class node_access

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

Public Functions

template<>
node_access northeast() const
template<>
node_access northwest() const
template<>
node_access southeast() const
template<>
node_access southwest() const
template<>
value_type data() const
template<>
key_type x() const
template<>
key_type y() const
template<>
operator bool() const
template<>
bool operator==(const node_access &r) const
template<>
node_access &operator=(const node_access &r)
template<>
node_access()
template<>
node_access(const node_access &r)
template<>
~node_access()
struct point

Public Functions

template<>
point(key_type _x, key_type _y)
template<>
point()

Public Members

template<>
key_type x
template<>
key_type y
class search_results

Public Functions

template<>
search_results()
template<>
search_results(const search_results &r)
template<>
search_results::const_iterator begin()
template<>
search_results::const_iterator end()
class const_iterator

Public Types

template<>
typedef std::pair<point, parent_value_type> value_type
template<>
typedef value_type *pointer
template<>
typedef value_type &reference
template<>
typedef ptrdiff_t difference_type
template<>
typedef std::bidirectional_iterator_tag iterator_category

Public Functions

template<>
const_iterator(res_nodes_ptr &ptr)
template<>
const_iterator(const const_iterator &r)
template<>
const_iterator &operator=(const const_iterator &r)
template<>
bool operator==(const const_iterator &r) const
template<>
bool operator!=(const const_iterator &r) const
template<>
const value_type &operator*() const
template<>
const value_type *operator->() const
template<>
const value_type *operator++()
template<>
const value_type *operator--()

Friends

friend mdds::point_quad_tree::point_quad_tree< _Key, _Value >::search_results