4. Project 4

4.1. Project 4: Air Traffic Control

• Similar to Project 2

• You will implement a simplified Air Traffic Control System

  • Store a bunch of objects in 3D

  • Objects are primarily represented by bounding boxes.

  • Two indices: A SkipList (replaces the BST) and a 3d BinTree (replaces the kd tree).

4.2. Design Issues

• You will be storing a collection of objects that extend a base class.

  • Objects all have a name field (the key for the SkipList) and a 3D bounding box (used by the Bintree).

• The SkipList is a straightforward implementation (see code in OpenDSA).

  • This should be a generalized container class

• The Bintree is a full binary tree

  • Implement separate internal and leaf node classes that use an interface.

  • Implement empty nodes as a flyweight design pattern.

  • Implement the tree using the Composite design pattern.

4.3. Bintree 1

4.4. Bintree 2

4.5. Bintree 3

• You will be storing boxes, not points.

• Spatial data structures have a Decomposition Rule.

  • Our rule is that a node can store a list of up to three boxes, or as many boxes as required if they all share a common intersection.

  • If the boxes in the node violate this rule, then split it (during insertion).

  • If an internal node has two leaf children that, together, pass the rule, then merge them (on deletion).

• Since a box can appear in multiple nodes, collisions and intersections are only reported as associated with the origin point of the intersection box.