#include <KdTreeElement.h>

Inheritance diagram for bridges::datastructure::KdTreeElement< K, E >:

Detailed Description

template<typename K, typename E>
class bridges::datastructure::KdTreeElement< K, E >

This class can be used to create K-d Tree elements, derived from BSTElement. K-D trees can be thought of as the spatial equivalent binary search trees and operate on multiple dimensions (2D and 3D are most common). These trees serve as a representation of the underlying geometrically defined spaces. Specialized versions of these trees include quadtrees and octrees, which subdivide into equal sized quadrants octants at each level, respectively.

This class extends the BSTElement class by adding a dimension property. It also includes a thickness property for displaying the partitioning lines generated by the convex decomposition.

convenient to generate visual representation to allow for use in a binary search tree implementation.

See also

There is a tutorial about K-d Trees : http://bridgesuncc.github.io/tutorials/KdTree.html

 @param K that is the search key type - this is usually a number, integer
    or float
 @param E the application data type

Author: Kalpathi Subramanian

Date: 6/18/15, 7/17/16

Public Member Functions
	KdTreeElement (const K &k, int dim, int th, const KdTreeElement l, const KdTreeElement r, const E &val=E(), const string &lab=string())

	KdTreeElement (const K &k, int dim, int th=0, const E &val=E(), const string &lab=string())

virtual const string	getDStype () const override

int	getDimension () const

void	setDimension (const int &dim)

float	getThickness () const

void	setThickness (const float &th)

K	getPartitioner () const

void	setPartitioner (const K &p)

virtual KdTreeElement *	getLeft () override

virtual const KdTreeElement *	getLeft () const override

void	setLeft (KdTreeElement *l)

virtual KdTreeElement *	getRight () override

virtual const KdTreeElement *	getRight () const override

void	setRight (KdTreeElement *r)

Public Member Functions inherited from bridges::datastructure::BSTElement< K, E >
	BSTElement (const K &k, BSTElement l, BSTElement r, const E &val=E(), const string &lab=string())

	BSTElement (const K &k, const E &val=E(), const string &lab=string())

K	getKey () const

void	setKey (const K &k)

void	setLeft (BSTElement *l)

void	setRight (BSTElement *r)

Public Member Functions inherited from bridges::datastructure::BinTreeElement< E >
	BinTreeElement (BinTreeElement l, BinTreeElement r, const E &e=E(), const string &lab=string())

	BinTreeElement (const E &e=E(), const string &lab=string())

void	setLeft (BinTreeElement *l)

void	setRight (BinTreeElement *r)

Public Member Functions inherited from bridges::datastructure::TreeElement< E >
	TreeElement (const E &e=E(), const string &lab=string())

vector< TreeElement * > &	getChildren ()

const vector< TreeElement * > &	getChildren () const

TreeElement *	getChild (const int &n)

const TreeElement *	getChild (const int &n) const

void	addChild (TreeElement *child)

void	setChild (const size_t &index, TreeElement *kid)

Public Member Functions inherited from bridges::datastructure::Element< E >
	Element (const E &val=E(), const string &lab=string())

	Element (const Element &e)

Element &	operator= (const Element &e)

E &	operator= (E const &e)

virtual	~Element ()

ElementVisualizer *	getVisualizer ()

const ElementVisualizer *	getVisualizer () const

LinkVisualizer *	getLinkVisualizer (const Element *el)

LinkVisualizer *	getLinkVisualizer (const Element *el) const

string const &	getLabel () const

void	setLabel (const string &lab)

E const &	getValue () const

E &	getValue ()

void	setValue (const E &val)

void	setSize (const double &sz)
	Sets size of the element. More...

double	getSize () const

void	setColor (const Color &col)
	Set the color of the Element. More...

void	setColor (const string col)
	Set the color by name. More...

Color	getColor () const
	Get the current color of the element. More...

void	setOpacity (double opacity)

double	getOpacity ()

void	setShape (const Shape &shp)
	Set the shape of the element. More...

Shape	getShape () const
	Returns the shape of the element. More...

void	setLocation (const double &locX, const double &locY)

double	getLocationX () const

double	getLocationY () const

Public Member Functions inherited from bridges::datastructure::DataStructure
virtual	~DataStructure ()=default

Protected Member Functions
virtual const string	getElementRepresentation () const override

Additional Inherited Members
Static Protected Member Functions inherited from bridges::datastructure::Element< E >
static const string	getLinkRepresentation (const LinkVisualizer &lv, const string &src, const string &dest)

Protected Attributes inherited from bridges::datastructure::BSTElement< K, E >
K	key = K()

Protected Attributes inherited from bridges::datastructure::Element< E >
unordered_map< Element *, LinkVisualizer >	links

Constructor & Destructor Documentation

◆ KdTreeElement() [1/2]

template<typename K , typename E >

bridges::datastructure::KdTreeElement< K, E >::KdTreeElement	(	const K &	k,
		int	dim,
		int	th,
		const KdTreeElement< K, E > *	l,
		const KdTreeElement< K, E > *	r,
		const E &	val = `E()`,
		const string &	lab = `string()`
	)

inline

Constructs a KdTreeElement with the provided value, label, key, left and right KdTree elements. The defaults will be used if not provided.

Parameters

k	The key for ordering
dim	number of dimension to be partitioned
th	thickness of the line showing the partition
l	The left KdTree Element
r	The right KdTree Element
val	The data to hold
lab	The label to show

◆ KdTreeElement() [2/2]

template<typename K , typename E >

bridges::datastructure::KdTreeElement< K, E >::KdTreeElement	(	const K &	k,
		int	dim,
		int	th = `0`,
		const E &	val = `E()`,
		const string &	lab = `string()`
	)

inline

Constructs a KdTreeElement with the provided value, label, key, setting the left and right KdTreeElement to NULL. The defaults will be used if not provided.

Parameters

k	The key for ordering
dim	number of dimensions being partitioned
th	thickness of the line showing the partition
val	The data to hold
lab	The label to show

Member Function Documentation

◆ getDimension()

template<typename K , typename E >

int bridges::datastructure::KdTreeElement< K, E >::getDimension ( ) const

inline

Get Dimension of the partition

Returns: return the partitioning of this node

◆ getDStype()

template<typename K , typename E >

virtual const string bridges::datastructure::KdTreeElement< K, E >::getDStype ( ) const

inlineoverridevirtual

Returns: the data structure type

Reimplemented from bridges::datastructure::BSTElement< K, E >.

◆ getElementRepresentation()

template<typename K , typename E >

virtual const string bridges::datastructure::KdTreeElement< K, E >::getElementRepresentation ( ) const

inlineoverrideprotectedvirtual

Gets the JSON representation of this element

Reimplemented from bridges::datastructure::BSTElement< K, E >.

◆ getLeft() [1/2]

template<typename K , typename E >

virtual KdTreeElement* bridges::datastructure::KdTreeElement< K, E >::getLeft ( )

inlineoverridevirtual

Get left child

Returns: The left child

Reimplemented from bridges::datastructure::BSTElement< K, E >.

◆ getLeft() [2/2]

template<typename K , typename E >

virtual const KdTreeElement* bridges::datastructure::KdTreeElement< K, E >::getLeft ( ) const

inlineoverridevirtual

Get left child - constant version

Returns: The left child

Reimplemented from bridges::datastructure::BSTElement< K, E >.

◆ getPartitioner()

template<typename K , typename E >

K bridges::datastructure::KdTreeElement< K, E >::getPartitioner ( ) const

inline

Get partitioner value

Returns: return the partitioner value

◆ getRight() [1/2]

template<typename K , typename E >

virtual KdTreeElement* bridges::datastructure::KdTreeElement< K, E >::getRight ( )

inlineoverridevirtual

Get right child

Returns: The right child

Reimplemented from bridges::datastructure::BSTElement< K, E >.

◆ getRight() [2/2]

template<typename K , typename E >

virtual const KdTreeElement* bridges::datastructure::KdTreeElement< K, E >::getRight ( ) const

inlineoverridevirtual

Constant version

Returns: The right child

Reimplemented from bridges::datastructure::BSTElement< K, E >.

◆ getThickness()

template<typename K , typename E >

float bridges::datastructure::KdTreeElement< K, E >::getThickness ( ) const

inline

Get thickness of the partition

Returns: return the partitioner thickness

◆ setDimension()

template<typename K , typename E >

void bridges::datastructure::KdTreeElement< K, E >::setDimension ( const int & dim )

inline

Set partitioning dimension to "dim"

Parameters

dim	The partitioning dimension of this Kd tree element

◆ setLeft()

template<typename K , typename E >

void bridges::datastructure::KdTreeElement< K, E >::setLeft ( KdTreeElement< K, E > * l )

inline

Sets left child to "l"

Parameters

l	The left child

◆ setPartitioner()

template<typename K , typename E >

void bridges::datastructure::KdTreeElement< K, E >::setPartitioner ( const K & p )

inline

Set partitioning dimension to "dim"

Parameters

dim	The partitioning dimension of this Kd tree element

◆ setRight()

template<typename K , typename E >

void bridges::datastructure::KdTreeElement< K, E >::setRight ( KdTreeElement< K, E > * r )

inline

Sets right to "r"

Parameters

r	The right BSTElement

◆ setThickness()

template<typename K , typename E >

void bridges::datastructure::KdTreeElement< K, E >::setThickness ( const float & th )

inline

Set partitioning dimension to "dim"

Parameters

dim	The partitioning dimension of this Kd tree element

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

/home/erik/work/bridges/bridges-cxx/src/KdTreeElement.h

Detailed Description

template<typename K, typename E> class bridges::datastructure::KdTreeElement< K, E >

Public Member Functions

Protected Member Functions

Additional Inherited Members

Constructor & Destructor Documentation

◆ KdTreeElement() [1/2]

◆ KdTreeElement() [2/2]

Member Function Documentation

◆ getDimension()

◆ getDStype()

◆ getElementRepresentation()

◆ getLeft() [1/2]

◆ getLeft() [2/2]

◆ getPartitioner()

◆ getRight() [1/2]

◆ getRight() [2/2]

◆ getThickness()

◆ setDimension()

◆ setLeft()

◆ setPartitioner()

◆ setRight()

◆ setThickness()

template<typename K, typename E>
class bridges::datastructure::KdTreeElement< K, E >