#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.

◆ 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

kdnodes a 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
	)