kdtree.h File Reference

KDTree implementation using Points in k-dimensional space. More...

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

Functions
template<int Dim>
bool	shouldReplace (const Point< Dim > &target, const Point< Dim > &currentBest, const Point< Dim > &potential)
	Determines if a Point is closer to the target Point than another reference Point. More...
template<int Dim>
bool	smallerDimVal (const Point< Dim > &first, const Point< Dim > &second, int curDim)
	Determines if Point a is smaller than Point b in a given dimension d. More...
template<typename RandIter , typename Comparator >
void	select (RandIter begin, RandIter end, RandIter k, Comparator cmp)
	This function uses the quickselect algorithm to partition the given range such that the k-th element is in the k-th position and all elements that compare as less by the provided function are to the left and all larger elements are to the right. More...

Detailed Description

KDTree implementation using Points in k-dimensional space.

Author

Zesheng Wang

Wade Fagen-Ulmschneider

Cinda Heeren

Jack Toole

Sean Massung

Function Documentation

select()

template<typename RandIter , typename Comparator >

void select	(	RandIter	begin,
		RandIter	end,
		RandIter	k,
		Comparator	cmp
	)

This function uses the quickselect algorithm to partition the given range such that the k-th element is in the k-th position and all elements that compare as less by the provided function are to the left and all larger elements are to the right.

Note this does not sort the range and runs in expected O(n) time.

Reference (https://en.wikipedia.org/wiki/Quickselect)

Parameters

begin	iterator to the start of the range inclusive
end	iterator to one past the end of the range
k	iterator to the location in the range to find
cmp	compare function true if arg1 is less than arg2

Todo:

Implement this function!

shouldReplace()

template<int Dim>

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

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: . 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 Part 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 smallerDimVal	(	const Point< Dim > &	first,
		const Point< Dim > &	second,
		int	curDim
	)

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 Part 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!