Computer Science 225
Advanced Programming
Spring 2020, Siena College
Lecture 12: Spatial Data Structures
Date: Monday, February 17, 2020
Agenda
- Announcements
- Lab 3: More Java Swing due as usual in labs this week
- Problem Set 3 continues
- BestOfTestsS20 test cases from lab are merged in
- Exam 1 information
- Wednesday, February 26, 7-9 PM (or so)
- please contact me (email me right now) if you have a conflict
- in trade for your attendance at the evening exam, there will
be no lab meetings next week, though the first hour of each
(10:30-11:30 Tues, 1-2 Tues, 10:30-11:30 Wed) will be open review
times
- topics covered are lecture topics up to this week's discussion of spatial data structures, all three problem sets, Labs 0-4
- exam will include written (closed notes) and practical portions (open notes and Java API but not the entire Internet)
- examples of specifics you should know/be able to do
- all terminology: give a definition, identify an example
- write methods on a generic list or using the return values of an iterator
- draw a memory diagram including stack, heap, and static data
- write Iterator/generator classes
- write and use Comparable classes and Comparators
- write Java applications that use Java Swing components and event handlers
- use interfaces, abstract classes, and inheritance to design and implement a program
- Spatial data structures
- an interface to define required operations
- a simple implementation based on ArrayLists
- an implementation based on an adaptive quadtree
- In-class exercise (2 points): draw the quadtree that results
from the addition of the 10 points in the SmallTest program in
today's example
Terminology
- spatial data structure
- quadtree
- quadrant
- terminal quadrant
- adaptive
Examples