CS 2420: Introduction to Computer Science II: Homework 10

CS 2420:
Introduction to Computer Science II
Homework 10

Assigned: Monday, Nov 17, 2014
Due: Wednesday, Nov 26, 2014, at 3pm.

Homework 10

Part I: Implement a KD Tree

Implement a balanced kd-tree. You may assume that the set of points to be stored is passed to the constructor. You will also need a method that finds all the points within a specified radius of a query point. To get full credit building the KD-tree should take O(n log n). An O(n (log n)^2) will lose 10 pts (20%).

Part II: Incorporate your KD Tree into the Boid Simulator

Use the KD tree to lookup nearby boids in the boid simulator. This should lead to a significant performance increase.

Part III: Modify the Boid simulator

Modify the boids simulator to include new behavior and/or some user interaction. See Steering Behaviors For Autonomous Characters for ideas. Another idea would be to draw boids that have some shape and orient the "head" in the velocity direction (as below).

What to hand in

Create a web page for the assignment. Include screen shots of your applet. Or better yet add the applet to your webpage! Use the CADE online handin system to handin your source code. Please zip and handin your entire project directory (including an info.txt file). If you work in a team only one of you need to submit the source code.

Grading

Each homework assignment will receive a grade out of 100 points. This week, the available points will be broken down like so:

50 points: KD Tree
20 points: Creative modifications
10 points: Comments describing the class, each method as well as the interesting pieces of the code itself
10 points: Elegance of programming
10 points: Web page