Asg 5: Qt kd-tree

Objectives

Description

1. Use Qt to implement a graphical user interface (GUI) for testing the kd-tree's insert() and nn(), knn(), and range() (query) functions.

   

Suggestions

1. Make heavy use of Qt's (4.2) online reference documentation.
2. You have the following graphical user interface (GUI) actions expected from the user:
   • point insertion
   • nearest-neighbor query
   • k-nearest-neighbor query
   • range query
   Mapping user actions to GUI event is a classic Human-Computer Interaction (HCI) problem, one that is best approached via thoughtful design. Generally, one strives to match natural and intuitive actions to GUI events, e.g.,
   • point insertion would be fairly natural by pressing the left mouse button;
   • the nearest-neighbor query via a middle mouse button press;
   • the k-nearest neighbor via a CTRL-middle mouse button press; and
   • the range query via a rectangular box selection made by clicking and dragging while pressing the right mouse button.
   If you don't have a three-button mouse, an alternate mapping may use "modifier" keyboard keys, e.g.,
   • point insertion: left mouse button;
   • the nearest-neighbor query: ALT-left mouse button;
   • the k-nearest neighbor: ALT-SHIFT left mouse button;
   • the range query: SHIFT left mouse button.
   Your GLTexobj object, subclassed (derived) from Qt's QGLWidget readily provides these mouse event handlers (that you have to override). Your derived GLTexobj class just needs to provide the following "event handles":

   void GLTexobj::mousePressEvent(QMouseEvent* e)
   void GLTexobj::mouseReleaseEvent(QMouseEvent* e)
   	

   When the mouse is pressed, you check to see which button triggered the event by testing against a pre-defined enumerated type, e.g., if the left mouse button was pressed,

     if(e->button() == Qt::LeftButton) {
       // left mouse button pressed
     }
   	

   you should add a new point_t(x,y) to the list of points "owned" by the GLTexobj. If the right mouse button was pressed,

     if(e->button() ==Qt::RightButton) {
       // right mouse button pressed
     }
   	

   you should turn on a box drawing flag (a simple boolean) and set the starting box coordinates to the mouse coordinates:

       // starting to draw the range query bounding box
       drawingBox = true;
       x1 = x; y1 = y;
       x2 = x; y2 = y;
   	

   When the mouse button is released, and it's the right button that was released, set the final coordinates of the range box, "sort" both sets of coordinates into their minimum and maximum:

       x2 = x; y2 = y;
       point_t min,max;
       min[0] = x1 < x2 ? x1 : x2;  max[0] = x1 > x2 ? x1 : x2;
       min[1] = y1 < y2 ? y1 : y2;  max[1] = y1 > y2 ? y1 : y2;
   	

   stop drawing the range box and call the kd-tree range query:

       drawingBox = false;
       kdtree.range(min,max,range);
   	

   Modifier keyboard keys can be checked by similarly testing the event modifiers() against pre-defined enumerated types, e.g.,

     if(e->modifiers() == Qt::ShiftModifier) {
       // SHIFT key pressed when button pressed
     }
   	

   or if there are two that you want to be pressed simultanesouly,

     if(e->modifiers() == (Qt::ShiftModifier & Qt::AltModifier)) {
       // ALT SHIFT key pressed when button pressed
     }
   	

   or maybe you don't want any modifiers pressed at all:

     if(e->modifiers() == Qt::NoModifier) {
       // no modifier key pressed when button pressed
     }
   	

3. Note that the Qt GLTexobj window's mouse coordinates are usually measured within the window dimensions: [0,width()],[0,height()] with (0,0) at upper-left. To map these coordinates so that (0,0) is at the window center, use this handy conversion (with QMouseEvent* e):

     // handle Qt to OpenGL y-coordinate flip
     x = e->x();
     y = height() - e->y();
   
     // normalize coordinates (puts them in range [0,1])
     double dx = (double)x/width();
     double dy = (double)y/height();
   
     // scale coorindates by 2 then shift to the right by 1, scale again by w,h
     dx = width()*(2.0*dx - 1.0);
     dy = height()*(2.0*dy - 1.0);
   
     // set integer coordinates
     x = (int)dx;
     y = (int)dy;
   	

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