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.

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 data_not_found¶

Inherits from exception

class node_access¶

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

Public Functions

node_access northeast() const¶

node_access northwest() const¶

node_access southeast() const¶

node_access southwest() const¶

value_type data() const¶

key_type x() const¶

key_type y() const¶

operator bool() const¶

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

node_access &operator=(const node_access &r)¶

node_access()¶

node_access(const node_access &r)¶

~node_access()¶

struct point¶

Public Functions

point(key_type _x, key_type _y)¶

point()¶

Public Members

key_type x¶

key_type y¶

class search_results¶

Public Functions

search_results()¶

search_results(const search_results &r)¶

search_results::const_iterator begin()¶

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

const_iterator(res_nodes_ptr &ptr)¶

const_iterator(const const_iterator &r)¶

const_iterator &operator=(const const_iterator &r)¶

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

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

const value_type &operator*() const¶

const value_type *operator->() const¶

const value_type *operator++()¶

const value_type *operator--()¶

Friends

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