This takes a single parameter, a reference to a constant STL vector of Point<Dim

Question

This takes a single parameter, a reference to a constant STL vector of Point<Dim>. You may assume that the vector has at least one point in it. The constructor should build the tree using recursive helper function(s).

A rooted binary tree T is a kd-tree if:

T is empty, OR
T consists of a k-dimensional point r called the root, a splitting dimension d, and subtrees T_L and T_R, so that if v is an element in T_L, then v_d <= r_d, and if v is an element in T_R, then v_d >= r_d. Furthermore, in our implementation, r is the median of all the points (defined below) in T in dimension d. And finally, T_L and T_R are also kd-trees whose roots' splitting dimensions, if they exist, are (d + 1) mod k.

Because the size of the tree is static and known at construction, we can assure that it's balanced and very regularly shaped. We accomplish this by choosing a median node to be the root of each subtree. In this situation, we can use a linear structure like an array or a vector to store the points, rather than using dynamic memory to allocate nodes like we did with the QuadTree. There are a few different ways to implement a regularly shaped binary tree using an array. Our testing code for this mp requires that you implement it by storing the root of the subtree containing array indices {a, a+1, ... b-1, b} in cell floor((a+b)/2). This means, in particular, that the index of the root of the entire tree will be in cell floor((0 + (n-1))/2). Your recursive tree-building calls will refer to the cells on the left and to the cells on the right of this location.

The median node of n nodes is calculated as the cell floor((n-1)/2). 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 the Point class's operator<. Although this is arbitrary and doesn't affect the functionality of the KD-Tree, 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. 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 3-D tree will have levels split by dimension 0, 1, 2, 0, 1, 2, etc.

Because we don't want to modify the vector of Points passed in to the constructor, the actual work should be done on a vector of integers, which index into the Points vector. You will probably want to write a helper function which performs the median selection and partitioning on this integer vector.


template<int Dim>
KDTree<Dim>::KDTree(const vector< Point<Dim> > & newPoints)
{
// This is the structure of the function creating KD Tree
}


The following are relevant .h file function delcarations

template<int Dim>
class KDTree
{
private:
// Member variables
vector< Point<Dim> > points;
vector<int> point_index;
// You may add your own member variables here

// You may add your own helper functions here

public:

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

Point<Dim> findNearestNeighbor(const Point<Dim> & a) const;
};


//The following is stucture of our Point<Dim> where dim is 3
template<int Dim>
template <typename T>
Point<Dim>::Point(T x0, T x1, T x2)
: am_mine(false)
{
vals[0] = x0;
vals[1] = x1;
vals[2] = x2;
}

Explanation / Answer

https://wiki.engr.illinois.edu/display/cs225/MP+6.1

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.