GEOS  3.13.0dev
Public Member Functions | Static Public Member Functions | List of all members
geos::index::kdtree::KdTree Class Reference

#include <KdTree.h>

Public Member Functions

 KdTree (double p_tolerance)
 
bool isEmpty ()
 
KdNodeinsert (const geom::Coordinate &p)
 
KdNodeinsert (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)
 
KdNodequery (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.

◆ 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]

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

Converts a collection of KdNodes to an vector of geom::Coordinates.

Parameters
kdnodesa collection of nodes
Returns
an vector of the coordinates represented by the nodes

◆ toCoordinates() [2/2]

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

Converts a collection of KdNodes to an vector of geom::Coordinates, specifying whether repeated nodes should be represented by multiple coordinates.

Parameters
kdnodesa collection of nodes
includeRepeatedtrue 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: