Point Quad Tree

API Reference

template<typename _Key, typename _Value>
class mdds::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

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--()

Public Members

typedef::std::bidirectional_iterator_tag iterator_category

Friends

friend class point_quad_tree< _Key, _Value >::search_results