#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 : https://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, 12/28/20

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
	Get Dimension of the partition. More...

void	setDimension (const int &dim)
	Set partitioning dimension to "dim". More...

float	getThickness () const
	Get thickness of the partition. More...

void	setThickness (const float &th)
	Set partitioning dimension to "dim". More...

K	getPartitioner () const
	Get partitioner value. More...

void	setPartitioner (const K &p)
	Set partitioning dimension to "dim". More...

virtual KdTreeElement *	getLeft () override
	Get left child. More...

virtual const KdTreeElement *	getLeft () const override
	Get left child - constant version. More...

void	setLeft (KdTreeElement *l)
	Sets left child to "l". More...

virtual KdTreeElement *	getRight () override
	Get right child. More...

virtual const KdTreeElement *	getRight () const override
	Get right child - Constant version. More...

void	setRight (KdTreeElement *r)
	Sets right child to "r". More...

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())
	Construct a TreeElement from given values. More...

vector< TreeElement * > &	getChildren ()
	Get the children of this node. More...

const vector< TreeElement * > &	getChildren () const
	Get the children of this node. More...

TreeElement *	getChild (const int &n)
	Gets the nth child of this node. More...

const TreeElement *	getChild (const int &n) const
	Gets the nth child of this node - constant version. More...

void	addChild (TreeElement *child)
	Adds a child to children. More...

void	setChild (const size_t &index, TreeElement *kid)
	Sets child at index to "kid". More...

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 ()
	Get the element visualizer object. More...

const ElementVisualizer *	getVisualizer () const
	Get the element visualizer object - constant version. More...

LinkVisualizer *	getLinkVisualizer (const Element *el)
	Returns the LinkVisualizer of element. More...

LinkVisualizer *	getLinkVisualizer (const Element *el) const
	Returns the LinkVisualizer of element. More...

string const &	getLabel () const
	Gets the label of this element. More...

void	setLabel (const string &lab)
	Sets label of this element. More...

E const &	getValue () const
	Gets the object held in the generic object E. More...

E &	getValue ()
	Gets the object held in the generic object E. More...

void	setValue (const E &val)
	Sets generic object to "val". More...

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

double	getSize () const
	Get element size. More...

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)
	Set opacity of element - use the 4th color component. More...

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)
	Sets the location attributes of an element. More...

double	getLocationX () const
	Gets the X coordinate of the location. More...

double	getLocationY () const
	Gets the Y coordinate of the location. More...

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

Protected Member Functions
virtual const string	getElementRepresentation () const override
	get kd tree element representation as JSON string More...

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

get kd tree element representation as JSON string

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

◆ getLeft() [1/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 >.

◆ getLeft() [2/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 >.

◆ 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 const KdTreeElement* bridges::datastructure::KdTreeElement< K, E >::getRight ( ) const

inlineoverridevirtual

Get right child - Constant version.

Returns: The right child

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

◆ getRight() [2/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 >.

◆ 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

p	The partitioning dimension value 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 child 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

th	The thickness of the partitioner to set

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 >