geos::index::kdtree::KdTree Class Reference

`#include <KdTree.h>`

## Public Member Functions

| KdTree (double p_tolerance)
bool | isEmpty ()
KdNode * | insert (const geom::Coordinate &p)
KdNode * | insert (const geom::Coordinate &p, void *data)
void | query (const geom::Envelope &queryEnv, KdNodeVisitor &visitor)
std::unique_ptr< std::vector< KdNode * > > | query (const geom::Envelope &queryEnv)
void | query (const geom::Envelope &queryEnv, std::vector< KdNode * > &result)
KdNode * | query (const geom::Coordinate &queryPt)

## Static Public Member Functions

static std::unique_ptr< std::vector< geom::Coordinate > > | toCoordinates (std::vector< KdNode * > &kdnodes)
static std::unique_ptr< std::vector< geom::Coordinate > > | toCoordinates (std::vector< KdNode * > &kdnodes, bool includeRepeated)

## Detailed Description

An implementation of a 2-D KD-Tree. KD-trees provide fast range searching on point data.

This implementation supports detecting and snapping points which are closer than a given distance tolerance. If the same point (up to tolerance) is inserted more than once, it is snapped to the existing node. In other words, if a point is inserted which lies within the tolerance of a node already in the index, it is snapped to that node. When a point is snapped to a node then a new node is not created but the count of the existing node is incremented. If more than one node in the tree is within tolerance of an inserted point, the closest and then lowest node is snapped to.

Author
  David Skea
  Martin Davis

## Member Function Documentation

## insert()

KdNode * geos::index::kdtree::KdTree::insert | ( | const geom::Coordinate & | p | ) |

Inserts a new point in the kd-tree.

References insert().

Referenced by insert().

## query() [1/4]

KdNode * geos::index::kdtree::KdTree::query | ( | const geom::Coordinate & | queryPt | ) |

Searches for a given point in the index and returns its node if found.

## query() [2/4]

std::unique_ptr< std::vector< KdNode * > > geos::index::kdtree::KdTree::query | ( | const geom::Envelope & | queryEnv | ) |

Performs a range search of the points in the index.

## query() [3/4]

void geos::index::kdtree::KdTree::query | ( | const geom::Envelope & | queryEnv,
|  | KdNodeVisitor & | visitor )

Performs a range search of the points in the index and visits all nodes found.

## query() [4/4]

void geos::index::kdtree::KdTree::query | ( | const geom::Envelope & | queryEnv,
|  | std::vector< KdNode * > & | result )

Performs a range search of the points in the index.

## toCoordinates() [1/2]

std::unique_ptr< std::vector< geom::Coordinate > > geos::index::kdtree::KdTree::toCoordinates | ( | std::vector< KdNode * > & | kdnodes | ) |

static

Converts a collection of `KdNode`s to an vector of `geom::Coordinate`s.

Parameters

  kdnodes | a collection of nodes

Returns
  an vector of the coordinates represented by the nodes

## toCoordinates() [2/2]

std::unique_ptr< std::vector< geom::Coordinate > > geos::index::kdtree::KdTree::toCoordinates | ( | std::vector< KdNode * > & | kdnodes,
|  | bool | includeRepeated )

static

Converts a collection of `KdNode`s to an vector of `geom::Coordinate`s, specifying whether repeated nodes should be represented by multiple coordinates.

Parameters

  kdnodes | a collection of nodes
  includeRepeated | true if repeated nodes should be included multiple times

Returns
  an vector of the coordinates represented by the nodes

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

- KdTree.h