CPSC 212-002 Computer Science IV
(Data Structures and Algorithms)

Fall 2009
15:30-16:45TTH Daniel 415
Assignment 6

Objectives:
To build a kd-tree

Due date:
11/12/09

What to hand in:
A tar.gz archive of your asg6/ directory, including:
  1. A README file containing
    1. Course id--section no
    2. Name
    3. Assignment 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:
See handin notes

Description:
  1. Implement a kd-tree complete with insert() and nn(), knn(), and range() (query) functions
  2. Provide the following private member functions:
    
            kdNode*         insert(kdNode* &,std::vector<P>&,const T&,const T&,int);
            void            nn(kdNode* &,T&,P&,double&);
            void            knn(kdNode* &,T&,std::vector<P>&,double&,int);
            void            range(kdNode* &,const T&,const T&,std::vector<P>&);
    
            void            clear(kdNode* &);
            kdNode*         clone(kdNode* ) 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                                   *ptp = NULL;
            std::vector<Point*>                     pts;
            std::vector<Point*>::iterator           pit;
            kdTree<Point,Point*,PointAxisCompare>   kdtree;
    
            Point                                   query(276,335);
            Point                                   *nearest;
            double                                  radius(0.0);
    
            int                                     k=3;
            std::vector<Point*>                     knearest;
    
            double                                  x1=100, y1=-100;
            double                                  x2=400, y2=150;
            Point                                   min,max;
            std::vector<Point*>                     range;
    
      // read points in from file
      while(std::cin >> (ptp = new Point(0.0,0.0))) pts.push_back(ptp);
    
      // build kd-tree
      kdtree.insert(pts,Point(-640,-480),Point(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