KDTree class: implemented using Points in Dim dimensional space (given by the template parameter). More...

#include <kdtree.h>

Collaboration diagram for KDTree< Dim >:

Classes
struct	KDTreeNode
	Internal structure for a node of KDTree. More...

Public Member Functions
bool	smallerDimVal (const Point< Dim > &first, const Point< Dim > &second, int curDim) const
	Determines if Point a is smaller than Point b in a given dimension d. More...

bool	shouldReplace (const Point< Dim > &target, const Point< Dim > &currentBest, const Point< Dim > &potential) const
	Determines if a Point is closer to the target Point than another reference Point. More...

	KDTree (const vector< Point< Dim >> &newPoints)
	Constructs a KDTree from a vector of Points, each having dimension Dim. More...

	KDTree (const KDTree< Dim > &other)
	Copy constructor for KDTree. More...

KDTree const &	operator= (const KDTree< Dim > &rhs)
	Assignment operator for KDTree. More...

	~KDTree ()
	Destructor for KDTree. More...

Point< Dim >	findNearestNeighbor (const Point< Dim > &query) const
	Finds the closest point to the parameter point in the KDTree. More...

void	printTree (ostream &out=cout, colored_out::enable_t enable_bold=colored_out::COUT, int modWidth=-1) const
	You do not need to modify this function. More...

Private Member Functions
int	getPrintData (KDTreeNode *subroot) const
	Helper function for grading. More...

void	printTree (KDTreeNode *subroot, std::vector< std::string > &output, int left, int top, int width, int currd) const
	Helper function for grading. More...

Private Attributes
KDTreeNode *	root
	Internal representation, root and size. More...

size_t	size

Detailed Description

template<int Dim>
class KDTree< Dim >

KDTree class: implemented using Points in Dim dimensional space (given by the template parameter).

Constructor & Destructor Documentation

◆ KDTree() [1/2]

template<int Dim>

KDTree< Dim >::KDTree ( const vector< Point< Dim >> & newPoints )

Constructs a KDTree from a vector of Points, each having dimension Dim.

You need to handle the case that the vector has no Point in it. It should build the tree using recursive helper functions.

Since we know the size of the KDTree at construction, we can represent the tree as a linear structure and building the tree nodes based off this structure efficiently. For testing, we require the following:

The median node of n nodes is calculated as the cell $\left\lfloor\frac{n-1}{2}\right\rfloor$ . That is, the middle node is selected if there are an odd number, and the item before the middle if there are an even number. If there are ties (two points have equal value along a dimension), they must be decided using Point::operator<(). Although this is arbitrary and doesn't affect the functionality of the KDTree, it is required to be able to grade your code.

KD-trees are created recursively; at any stage of the construction, the median value in the current dimension is selected and a node is created based on it. Then, all the elements in the current subtree are divided up into elements which are less than the median, or greater than the median, and then the subtrees are created recursively. The children pick the median in the next dimension, and repeat until the entire set of inputs has been processed. Successive levels of the tree split on increasing dimensions, modulo the total number: a 3D tree will have levels split by dimension 0, 1, 2, 0, 1, 2, etc.

You will probably want to write a helper function which performs the median selection and partitioning. Maybe you can use a function you already wrote...

See also: Here is a reference that should help you create concise, efficient code: Partition-based General Selection Algorithm. Note that "select pivotIndex between left and right" means that you should choose a midpoint between the left and right indices.

Todo:: This function is required for MP 5.1.

Parameters

newPoints The vector of points to build your KDTree off of.

Todo:: Implement this function!

◆ KDTree() [2/2]

template<int Dim>

KDTree< Dim >::KDTree ( const KDTree< Dim > & other )

Copy constructor for KDTree.

Parameters

other The KDTree to copy.

Todo:: Implement this function!

◆ ~KDTree()

template<int Dim>

KDTree< Dim >::~KDTree ( )

Destructor for KDTree.

Todo:: Implement this function!

Member Function Documentation

◆ findNearestNeighbor()

template<int Dim>

Point< Dim > KDTree< Dim >::findNearestNeighbor ( const Point< Dim > & query ) const

Finds the closest point to the parameter point in the KDTree.

This function takes a reference to a template parameter Point and returns the Point closest to it in the tree. We are defining closest here to be the minimum Euclidean distance between elements. Again, if there are ties (this time in distance), they must be decided using Point::operator<(). Recall that an HSLAPixel is defined by three components: hue, saturation, and luminance.

The findNearestNeighbor() search is done in two steps: a search to find the smallest hyperrectangle that contains the target element, and then a back traversal to see if any other hyperrectangle could contain a closer point, which may be a point with smaller distance or a point with equal distance, but a "smaller" point (as defined by operator< in the point class). In the first step, you must recursively traverse down the tree, at each level choosing the subtree which represents the region containing the search element (another place to save some duplicate code?). When you reach the lowest bounding hyperrectangle, then the corresponding node is effectively the "current best" neighbor.

However, it may be the case that a better match exists outside of the containing hyperrectangle. At then end of first step of the search, we start traversing back up the kdtree to the parent node. The current best distance defines a radius which contains the nearest neighbor. During the back-traversal (i.e., stepping out of the recursive calls), you must first check if the distance to the parent node is less than the current radius. If so, then that distance now defines the radius, and we replace the "current best" match. Next, it is necessary to check to see if the current splitting plane's distance from search node is within the current radius. If so, then the opposite subtree could contain a closer node, and must also be searched recursively.

During the back-traversal, it is important to only check the subtrees that are within the current radius, or else the efficiency of the kdtree is lost. If the distance from the search node to the splitting plane is greater than the current radius, then there cannot possibly be a better nearest neighbor in the subtree, so the subtree can be skipped entirely.

You can assume that findNearestNeighbor will only be called on a valid kd-tree.

See also: Here is a reference we found quite useful in writing our kd-tree: Andrew Moore's KD-Tree Tutorial.; There is an example in the MP instructions.

Todo:: This function is required for MP 5.1.

Parameters

query The point we wish to find the closest neighbor to in the tree.

Returns: The closest point to a in the KDTree.

Todo:: Implement this function!

◆ getPrintData()

template<int Dim>

int KDTree< Dim >::getPrintData ( KDTreeNode * subroot ) const

private

Helper function for grading.

◆ operator=()

template<int Dim>

const KDTree< Dim > & KDTree< Dim >::operator= ( const KDTree< Dim > & rhs )

Assignment operator for KDTree.

Parameters

rhs	The right hand side of the assignment statement.

Returns: A reference for performing chained assignments.

Todo:: Implement this function!

◆ printTree() [1/2]

template<int Dim>

void KDTree< Dim >::printTree	(	ostream &	out = `cout`,
		colored_out::enable_t	enable_bold = `colored_out::COUT`,
		int	modWidth = `-1`
	)		const

You do not need to modify this function.

Its implementation is in kdtree_extras.cpp. Prints the KDTree to the terminal in a pretty way.

◆ printTree() [2/2]

template<int Dim>

void KDTree< Dim >::printTree	(	KDTreeNode *	subroot,
		std::vector< std::string > &	output,
		int	left,
		int	top,
		int	width,
		int	currd
	)		const

private

Helper function for grading.

◆ shouldReplace()

template<int Dim>

bool KDTree< Dim >::shouldReplace	(	const Point< Dim > &	target,
		const Point< Dim > &	currentBest,
		const Point< Dim > &	potential
	)		const

Determines if a Point is closer to the target Point than another reference Point.

Takes three points: target, currentBest, and potential, and returns whether or not potential is closer to target than currentBest.

We are using Euclidean distance to compare k-dimensional points: $\sqrt{(p_1-q_1)^2+(p_2-q_2)^2+\ldots+(p_n-q_n)^2} = \sqrt{\sum_{i=1}^n (p_i-q_i)^2}$ . Note, however, that minimizing distance is the same as minimizing squared distance, so you can avoid invoking the square root and just compare squared distances in your code.

For example:

Point<3> target(1, 3, 5);
Point<3> currentBest1(1, 3, 2);
Point<3> possibleBest1(2, 4, 4);
Point<3> currentBest2(1, 3, 6);
Point<3> possibleBest2(2, 4, 4);
Point<3> currentBest3(0, 2, 4);
Point<3> possibleBest3(2, 4, 6);
cout << shouldReplace(target, currentBest1, possibleBest1) << endl; // true
cout << shouldReplace(target, currentBest2, possibleBest2) << endl; // false
cout << shouldReplace(target, currentBest3, possibleBest3) << endl;
 // based on operator<, this should be false

Todo:: This function is required for MP 5.1.

Parameters

target	The Point we want to be close to.
currentBest	The Point that is currently our closest Point to target.
potential	Our Point that is a candidate to replace currentBest (that is, it may be closer to target than currentBest).

Returns: A boolean value indicating whether potential is closer to target than currentBest. Ties should be broken with Point::operator<().

Todo:: Implement this function!

◆ smallerDimVal()

template<int Dim>

bool KDTree< Dim >::smallerDimVal	(	const Point< Dim > &	first,
		const Point< Dim > &	second,
		int	curDim
	)		const

Determines if Point a is smaller than Point b in a given dimension d.

If there is a tie, break it with Point::operator<().

For example:

Point<3> a(1, 2, 3);
Point<3> b(3, 2, 1);
cout << smallerDimVal(a, b, 0) << endl; // should print true
cout << smallerDimVal(a, b, 2) << endl; // should print false
cout << smallerDimVal(a, b, 1) << endl; // based on operator<, this should be true

Todo:: This function is required for MP 5.1.

Parameters

first	Point to compare.
second	Second point to compare.
curDim	Dimension these points are being compared in.

Returns: A boolean value indicating whether the first Point is smaller than the second Point in the curDim dimension.

Todo:: Implement this function!

Member Data Documentation

◆ root

template<int Dim>

KDTreeNode* KDTree< Dim >::root

private

Internal representation, root and size.

◆ size

template<int Dim>

size_t KDTree< Dim >::size

private

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

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<int Dim> class KDTree< Dim >

Constructor & Destructor Documentation

◆ KDTree() [1/2]

◆ KDTree() [2/2]

◆ ~KDTree()

Member Function Documentation

◆ findNearestNeighbor()

◆ getPrintData()

◆ operator=()

◆ printTree() [1/2]

◆ printTree() [2/2]

◆ shouldReplace()

◆ smallerDimVal()

Member Data Documentation

◆ root

◆ size

template<int Dim>
class KDTree< Dim >