geos::index::bintree::Bintree Class Reference

A BinTree (or "Binary Interval Tree") is a 1-dimensional version of a quadtree. More...

#include <Bintree.h>

Collaboration diagram for geos::index::bintree::Bintree:

Public Member Functions
	Bintree ()
	~Bintree ()
int	depth ()
int	size ()
int	nodeSize ()
void	insert (Interval *itemInterval, void *item)
std::vector< void * > *	iterator ()
std::vector< void * > *	query (double x)
std::vector< void * > *	query (Interval *interval)
void	query (Interval *interval, std::vector< void * > *foundItems)

Static Public Member Functions
static Interval *	ensureExtent (const Interval *itemInterval, double minExtent)
	Ensure that the Interval for the inserted item has non-zero extents. More...

Private Member Functions
void	collectStats (Interval *interval)
	Bintree (const Bintree &)=delete
Bintree &	operator= (const Bintree &)=delete

Private Attributes
std::vector< Interval * >	newIntervals
Root *	root
double	minExtent

Detailed Description

A BinTree (or "Binary Interval Tree") is a 1-dimensional version of a quadtree.

It indexes 1-dimensional intervals (which of course may be the projection of 2-D objects on an axis). It supports range searching (where the range may be a single point).

This implementation does not require specifying the extent of the inserted items beforehand. It will automatically expand to accomodate any extent of dataset.

This index is different to the "Interval Tree of Edelsbrunner" or the "Segment Tree of Bentley".

Definition at line 54 of file Bintree.h.

Constructor & Destructor Documentation

geos::index::bintree::Bintree::Bintree

(

)

geos::index::bintree::Bintree::~Bintree

(

)

geos::index::bintree::Bintree::Bintree ( const Bintree &  )

privatedelete

Member Function Documentation

void geos::index::bintree::Bintree::collectStats ( Interval *  interval )

private

int geos::index::bintree::Bintree::depth

(

)

static Interval* geos::index::bintree::Bintree::ensureExtent ( const Interval *  itemInterval, double  minExtent  )

static

Ensure that the Interval for the inserted item has non-zero extents.

Use the current minExtent to pad it, if necessary.

Note

In GEOS this function always return a newly allocated object with ownership transferred to caller. TODO: change this ?

Parameters

itemInterval	source interval, ownership left to caller, no references hold
minExtent	minimal extent

void geos::index::bintree::Bintree::insert	(	Interval *	itemInterval,
		void *	item
	)

Parameters

itemInterval	Ownership left to caller, NO reference hold by this class.
item	Ownership left to caller, reference kept by this class.

std::vector<void*>* geos::index::bintree::Bintree::iterator

(

)

int geos::index::bintree::Bintree::nodeSize

(

)

Bintree& geos::index::bintree::Bintree::operator= ( const Bintree &  )

privatedelete

std::vector<void*>* geos::index::bintree::Bintree::query

(

double

x

)

std::vector<void*>* geos::index::bintree::Bintree::query

(

Interval *

interval

)

void geos::index::bintree::Bintree::query	(	Interval *	interval,
		std::vector< void * > *	foundItems
	)

int geos::index::bintree::Bintree::size

(

)

Member Data Documentation

double geos::index::bintree::Bintree::minExtent

private

Statistics

minExtent is the minimum extent of all items inserted into the tree so far. It is used as a heuristic value to construct non-zero extents for features with zero extent. Start with a non-zero extent, in case the first feature inserted has a zero extent in both directions. This value may be non-optimal, but only one feature will be inserted with this value.

Definition at line 115 of file Bintree.h.

std::vector<Interval*> geos::index::bintree::Bintree::newIntervals

private

Definition at line 101 of file Bintree.h.

Root* geos::index::bintree::Bintree::root

private

Definition at line 103 of file Bintree.h.

---

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

• Bintree.h