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

#include <KdTree.h>

Collaboration diagram for geos::index::kdtree::KdTree:

Classes
class	AccumulatingVisitor
class	BestMatchVisitor

Public Member Functions
	KdTree ()
	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)

Private Member Functions
KdNode *	findBestMatchNode (const geom::Coordinate &p)
KdNode *	insertExact (const geom::Coordinate &p, void *data)
void	queryNode (KdNode *currentNode, const geom::Envelope &queryEnv, bool odd, KdNodeVisitor &visitor)
KdNode *	queryNodePoint (KdNode *currentNode, const geom::Coordinate &queryPt, bool odd)
KdNode *	createNode (const geom::Coordinate &p, void *data)

Private Attributes
std::deque< KdNode >	nodeQue
KdNode *	root
size_t	numberOfNodes
double	tolerance

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

Definition at line 55 of file KdTree.h.

Constructor & Destructor Documentation

geos::index::kdtree::KdTree::KdTree ( )

inline

Definition at line 142 of file KdTree.h.

geos::index::kdtree::KdTree::KdTree ( double  p_tolerance )

inline

Definition at line 148 of file KdTree.h.

Member Function Documentation

KdNode* geos::index::kdtree::KdTree::createNode ( const geom::Coordinate &  p, void *  data  )

private

Create a node on a locally managed deque to allow easy disposal and hopefully faster allocation as well.

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

private

KdNode* geos::index::kdtree::KdTree::insert

(

const geom::Coordinate &

p

)

Inserts a new point in the kd-tree.

KdNode* geos::index::kdtree::KdTree::insert	(	const geom::Coordinate &	p,
		void *	data
	)

KdNode* geos::index::kdtree::KdTree::insertExact ( const geom::Coordinate &  p, void *  data  )

private

bool geos::index::kdtree::KdTree::isEmpty ( )

inline

Definition at line 154 of file KdTree.h.

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.

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.

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

Performs a range search of the points in the index.

KdNode* geos::index::kdtree::KdTree::query

(

const geom::Coordinate &

queryPt

)

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

void geos::index::kdtree::KdTree::queryNode ( KdNode *  currentNode, const geom::Envelope &  queryEnv, bool  odd, KdNodeVisitor &  visitor  )

private

KdNode* geos::index::kdtree::KdTree::queryNodePoint ( KdNode *  currentNode, const geom::Coordinate &  queryPt, bool  odd  )

private

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

kdnodes

a collection of nodes

Returns

an vector of the coordinates represented by the nodes

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

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

Member Data Documentation

std::deque<KdNode> geos::index::kdtree::KdTree::nodeQue

private

Definition at line 59 of file KdTree.h.

size_t geos::index::kdtree::KdTree::numberOfNodes

private

Definition at line 61 of file KdTree.h.

KdNode* geos::index::kdtree::KdTree::root

private

Definition at line 60 of file KdTree.h.

double geos::index::kdtree::KdTree::tolerance

private

Definition at line 62 of file KdTree.h.

---

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

• KdTree.h