Asg 5: Qt kd-tree


To provide an interactive Qt front end for the kd-tree


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


  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: 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., If you don't have a three-button mouse, an alternate mapping may use "modifier" keyboard keys, e.g., 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;
    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

Turn in all of your code, in one tar.gz archive of your asg##/ directory, including:
  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

See handin notes