Lab 11: kd-tree

Objectives

Assignment

1. Implement a kd-tree complete with insert() and nn(), knn(), and range() (query) functions
2. Provide the following private member functions:

   node_t*         insert(node_t* &,std::vector<P>&,const T&,const T&,int);
   void            nn(node_t* &,T&,P&,double&);
   void            knn(node_t* &,T&,std::vector<P>&,double&,int);
   void            range(node_t* &,const T&,const T&,std::vector<P>&);
   
   void            clear(node_t* &);
   node_t*         clone(node_t* ) const;
   	

3. The insert() routine prints out tree information as it is built (debugging info)
4. The operator<< output function prints the tree contents via inorder traversal
5. Your code should be such that the following main() routine works unaltered:

   #include       <iostream>
   #include       <iomanip>
   #include       <vector>
   
   using namespace std;
   
   #include        "point.h"
   #include        "tree.h"
           
   // prototypes
   int     main(int argc, char **argv);
                   
   int main(int argc, char **argv)
   {       
           point_t                                   *ptp = NULL;
           std::vector<point_t*>                     pts;
           std::vector<point_t*>::iterator           pit;
           kdTree<point_t,point_t*,PointAxisCompare> kdtree;
   
           point_t                                   query(276,335);
           point_t                                   *nearest;
           double                                    radius(0.0);
   
           int                                       k=3;
           std::vector<point_t*>                     knearest;
   
           double                                    x1=100, y1=-100;
           double                                    x2=400, y2=150;
           point_t                                   min,max;
           std::vector<point_t*>                     range;
   
     // read points in from file
     while(std::cin >> (ptp = new point_t(0.0,0.0))) pts.push_back(ptp);
   
     // build kd-tree
     kdtree.insert(pts,point_t(-640,-480),point_t(640,480));
   
     // print kd-tree (in-order traversal)
     std::cout << "kd-tree (in-order): " << std::endl << kdtree;
   
     // nearest-neighbor
     kdtree.nn(query,nearest,radius);
     std::cout << "Point nearest to " << query << " is " << nearest << std::endl;
   
     // k nearest-neighbors
     kdtree.knn(query,knearest,radius,k);
     std::cout << k << " points nearest to " << query << " are " << std::endl;
     for(pit=knearest.begin(); pit!=knearest.end(); pit++)
       std::cout << *pit << std::endl;
   
     // range query points may be disorganized, i.e., user may have started out
     // at bottom-right, top-right, whatever; sort out into minx, maxx, miny, maxy
     // bounding box s.t. top-left is (minx,miny)
     min[0] = x1 < x2 ? x1 : x2;  max[0] = x1 > x2 ? x1 : x2;
     min[1] = y1 < y2 ? y1 : y2;  max[1] = y1 > y2 ? y1 : y2;
     kdtree.range(min,max,range);
     std::cout << " points in range " << min << "," << max << " are " << std::endl;
     for(pit=range.begin(); pit!=range.end(); pit++)
       std::cout << *pit << std::endl;
   
     // clean up (proper deletion)
     kdtree.clear();
     for(pit=pts.begin(); pit!=pts.end(); pit=pts.erase(pit))
       if(*pit) delete *pit;
   }
   	

6. Input file:
   

   -478.00000000 171.00000000 
   -258.00000000 37.00000000 
   14.00000000 105.00000000 
   -320.00000000 -147.00000000 
   304.00000000 149.00000000 
   140.00000000 -31.00000000 
   	

7. Sample output:
   

   depth: 0
   size: 6
   -478.00, 171.00
   -320.00, -147.00
   -258.00, 37.00
   14.00, 105.00
   140.00, -31.00
   304.00, 149.00
   depth: 1
   size: 3
   -320.00, -147.00
   -258.00, 37.00
   -478.00, 171.00
   depth: 2
   size: 1
   -320.00, -147.00
   depth: 2
   size: 1
   -478.00, 171.00
   depth: 1
   size: 2
   140.00, -31.00
   304.00, 149.00
   depth: 2
   size: 1
   140.00, -31.00
   kd-tree (in-order): 
   -320.00, -147.00
   -258.00, 37.00
   -478.00, 171.00
   14.00, 105.00
   140.00, -31.00
   304.00, 149.00
   Point nearest to 276.00, 335.00 is 304.00, 149.00
   3 points nearest to 276.00, 335.00 are 
   304.00, 149.00
   14.00, 105.00
   140.00, -31.00
    points in range 100.00, -100.00,400.00, 150.00 are 
   304.00, 149.00
   140.00, -31.00
   	

Suggestions

1. For the knn query, be sure to store nodes in the resultant vector in order sorted on distance to the query point; you will likely need to use the STL vector's

   	
   insert(iterator position, size_type n, const T& x);
   	

   function to do this

Turn in

1. A README file containing
   1. Course id--section no
   2. Name
   3. Lab description
   4. Brief solution description (e.g., program design, description of algorithm, etc., however appropriate).
   5. Lessons learned, identified interesting features of your program
   6. Any special usage instructions
2. Makefile
3. source code (.h headers and .cpp source)
4. object code (do a make clean before tar)

How to hand in