CS2230 Computer Science II: Data Structures Homework 6 Geographical queries with quad trees
Goals for this assignment
• Implement a Map using a search tree
• Write reusable code using generic types, abstract classes, and helper methods
• Get more practice writing JUnit tests
Purpose
screen shot of https://www.openstreetmap.org
Consider map web applications like OpenStreetMaps, Bing Maps, and Google Maps. They support a
feature to search for places of interest within the current viewing area. In this assignment you’ll
implement these kinds of searches using efficient data structures and algorithms.
Binary search trees can be used to build Maps (and Sets) that perform lookups and inserts in 𝑂(h) time,
which is efficient, particularly if the tree is balanced. Binary search trees are useful for data that are
ordered in 1 dimension, such as words in a dictionary. What about scenarios where there is ordering in 2
dimensions? Geography provides many examples of 2-dimensional data: coordinates on a map (in the
geographical sense of the word) are ordered North/South (latitude) and East/West (longitude).
In this project, you’ll build a data structure that efficiently supports point queries on 2D data. You’ve
already seen point queries on 1-dimensional data. Specifically, TreeMap has the get method that returns
the entry for a key. The geographical equivalent is like asking if there is an interesting landmark at a GPS
coordinate.
Copyright 2019, Brandon Myers
Submission Checklist
Wherever you see a in this document that means to write some Java code. Make sure files you create go within the appropriate package: net.datastructures or apps.
You are working optionally in a pair. If so, you will submit files to one of your two gitlab repositories at https://research-git.uiowa.edu/cs2230-fa19/hw6-hawkid
Before you are done submitting, you must check the following.
✓ Do the tests pass?
✓ Did I write the required tests?
✓ Does my github.uiowa.edu repository reflect the code I intend to turn in? (You must view this in
your web browser, not in IntelliJ or GitHub Desktop. If still in doubt, you can also clone your completed code into a second IntelliJ project and check it by running all the tests). It is your responsibility to have the right code by the due date.
Getting the code
Source repository
https://research-git.uiowa.edu/cs2230-assignments/spatial-tree-map-fa19.git
How to collaborate (skip if working alone)
If you are working together with a partner, you may want a way to share your code on gitlab together. Since you cannot change the membership of your hw6-hawkid repository, you’ll temporarily work in a single repo that one of you creates and shares with the other partner. Then at the end you can submit to one of your official hw6-hawkid repos.
1. Create a new project in gitlab with the name our-hw6. In Project URL you’ll see your own hawkid (not bdmyers). And in Visibility Level, choose Private. Then click Create Project.
Copyright 2019, Brandon Myers
2. In GitHub Desktop, set your remote repository to the HTTPS address of your new repo. You can find that by clicking the clone button in gitlab.
If you followed the naming convention in the previous steps, this address will be https://research- git.uiowa.edu/hawkid/our-hw6
3. In Github Desktop, do a push and then double check that the code is now in https://research- git.uiowa.edu/hawkid/our-hw6.
4. Now share the repo with your team member. To do this, make sure you are at https://research- git.uiowa.edu/hawkid/our-hw6. Then go to Settings > Members.
In that menu, you can type your partner’s hawkid into Gitlab member or Emal Address. For Choose a role permission pick Maintainer. Finally click Add to project.
Copyright 2019, Brandon Myers
5. Your partner should make sure that they can clone https://research-git.uiowa.edu/hawkid/our-hw6 (where the hawkid is of course the hawkid of the person who created the repo).
IMPORTANT: we cannot see your personal repo! Remember to submit your final code by pushing to the https://research-git.uiowa.edu/cs2230-fa19/hw6-hawkid we created for you! We will not accept exceptions at the end of the semester.
IMPORTANT: we cannot see your personal repo! Remember to submit your final code by pushing to the https://research-git.uiowa.edu/cs2230-fa19/hw6-hawkid we created for you! We will not accept exceptions at the end of the semester.
IMPORTANT: we cannot see your personal repo! Remember to submit your final code by pushing to the https://research-git.uiowa.edu/cs2230-fa19/hw6-hawkid we created for you! We will not accept exceptions at the end of the semester.
Setting up your project
Follow the usual steps for setting up the IntelliJ project from existing sources. Then do these additional steps…
1. Make sure to add Junit 4
2. This project requires the commons-csv-1.5.jar for reading the CSV file, as in previous application activities. Download it from the Homework 6 ICON assignment.
a. Unzip commons-csv-1.5-bin.zip
b. In IntelliJ, make sure you are looking at your project. Choose File | Project Structure …
c. In the Project Structure window, choose Libraries. Then press ‘+’. Choose Java.
d. Navigate to where you downloaded commons-csv-1.5.jar, then click open.
Quad Trees
• •
In a binary search tree, data has a total ordering in 1 dimension. Every node p has 0-2 children and the
property that
p’s left subtree has only data less than p’s data
p’s right subtree has only data greater than p’s data
This concept can be extended to 2 dimensions! In a quadtree, keys are 2-dimension (x and y). Every
node p has 0-4 children the property that
subtree of p
x in the subtree
y in the subtree
northwest (NW)
less
greater
northeast (NE)
greater
greater
southwest (SW)
less
less
southeast
greater
less
Copyright 2019, Brandon Myers
Example 1
Here is an illustration of the quad tree that we get by inserting the following coordinates in this order. We show the final points at all steps, just so you can see where they will go.
(0, 0)
As the first node, this becomes the root of the quadtree. It bisects the space into quadrants NW, NE, SW, SE.
3
This coordinate becomes the NW child of (0,0). It bisects (0,0)’s NW quadrant into 4 sub-quadrants.
,4
0, 0
,2
7, 7
-3
-5
, -6
6, -5
(-3, 4)
10, 12
(3, 2)
-5
, -6
0, 0
,2
7, 7
10, 12
6, -5
-3, 4
3
This coordinate becomes the NE child of (0,0). It bisects (0,0)’s NE quadrant into 4 sub-quadrants.
-5
, -6
0, 0
,2
7, 7
10, 12
6, -5
(10, 12)
-3, 4
3
We search to (0,0)’s NE and get to (3,2). We find that (10,12) needs to go in (3,2)’s NE.
-3
,4
0, 0
3
,2
7, 7
10, 12
-5
, -6
6, -5
Copyright 2019, Brandon Myers
(7, 7)
We search to (0,0)’s NE and get to (3,2). We search to (3,2)’s NE and get to (10,12). We find that (7,7) needs to go in (10,12)’s SW.
-3
,4
3
0, 0
,2
-5
, -6
6, -5
(-5, -6) (6, -5)
7, 7
10, 12
Finally, these coordinates bisect the SW and SE quadrants of (0,0), respectively.
-3, 4
Here is what the tree would look like in our tree notation, where we use little boxes to indicate the external nodes (i.e., leaves), which serve as sentinel nodes as in the LinkedBinaryTree. The order of the children from left to right goes (NW, NE, SW, SE).
0,0
7,7
Example 2
10, 12
7, 7
0, 0
3, 2
-5, -6
6, -5
-3,4 3,2
10,12
-5,-6 6,-5
As with binary search trees, inserting the elements in a different order produces a different tree. Copyright 2019, Brandon Myers
(7, 7) (10, 12) (6, -5) (-5, -6) (3, 2) (-3, 4) (0, 0)
Try drawing the quadtree for this order of coordinates, then check yourself at Answer key – example 2
Overview
The goal of the project is to have a Map data structure that supports 2D point queries (“what is at coordinate x, y?”). To do so, you will implement a variant of Map called SpatialTreeMap (similar to TreeMap). To build that data structure, you will first build a generic quad tree (similar to LinkedBinaryTree). As with previous projects, there will be some test cases for each part, as well as queries to try once enough is completed.
Part 1: LinkedQuadTree
First, you need to implement the underlying data structure of SpatialTreeMap. Much like LinkedBinaryTree is merely a binary tree that knows nothing about sorted-ness of elements so will LinkedQuadTree know nothing about sorted-ness. Recall that it is the TreeMap that uses the LinkedBinaryTree as a binary search tree.
You’ll find an Interface called QuadTree, which is inspired by the BinaryTree interface. Instead of declaring methods to access left/right children; it declares methods to access nw/ne/sw/se children.
Write an abstract class AbstractQuadTree. Requirements
• has this class signature
• overrides these methods o numChildren
o children
TIPS: We recommend you get inspiration for these two methods from AbstractBinaryTree.
public abstract class AbstractQuadTree
Copyright 2019, Brandon Myers
You will write a class LinkedQuadTree. Your inspiration should be the LinkedBinaryTree.
Node class
The elements of the LinkedQuadTree tree will be stored in Nodes, each of which keeps references to its parent, element, and children. Finish the Node class inside of LinkedQuadTree.java.
Implement the methods declared in the QuadTree interface.
We’ve provided the method comments inside of LinkedQuadTree.
• nw • ne • sw • se
You should copy the method signatures from QuadTree.java into your LinkedQuadTree class then implement them. You should use the left and right methods of LinkedBinaryTree for inspiration.
Implement the LinkedQuadTree’s add* methods.
These are
• addNW • addNE • addSW • addSE
The signatures are already provided in the LinkedQuadTree class. You should use the addLeft/addRight methods of LinkedBinaryTree for inspiration.
DO NOT implement the remove method of LinkedQuadTree. We have provided a default implementation that simply throws an UnsupportedOperationException. Implementing remove for a quad tree is beyond the scope of the project, and you won’t need it for the geography applications.
Write tests for LinkedQuadTree
In the test/ folder, you’ll find LinkedQuadTreeTest.java. It contains 1 sample test and stubs for additional tests you must write. The everythingTest should combine calls to all the add* methods to make a more interesting tree.
TIP: For the everythingTest, consider using the add* methods to build one of the Example quad trees.
STOP: Make sure you’ve made at least 1 commit with the title Part 1 in it.
Copyright 2019, Brandon Myers
Part 2: Point queries with SpatialTreeMap
This part builds up to the quadtree-based Map data structure. It is roughly equivalent to the TreeMap, except it implements the Sorted2DMap interface rather than the SortedMap interface.
Start by inspecting Sorted2DMap, Coord, as well as the starter code for the SpatialTreeMap code. Can you explain the meaning of the class signatures, including the types? If not, ask someone!
public class SpatialTreeMap
Implement size, expandExternal
To get acquainted with the SpatialTreeMap code, implement the size and expandExternal methods. You should get direct inspiration from TreeMap.
Implement treeSearch
Now for the interesting part! Implement the treeSearch method. You should get direct inspiration from the treeSearch method in TreeMap. Use the examples in the Quad Trees section of this document to study how search should work. At each step of the search, you should explore nw, ne, sw, or se rather than left or right. The search is over when either a) you encounter an external node (not found) or b) you encounter the exact Coord you are looking for.
TIP: Notice that SpatialTreeMap has two private instance variables compX and compY. These are the comparators for the X and Y types.
IMPORTANT CONSIDERATION: In the binary search tree in TreeMap, we deal with duplicate keys by simply not inserting a key if it is already in the tree. That allowed us to use < and > and = as separate cases; we didn’t need ≤ 𝑜𝑟 ≥.However, in a quadtree, we could have the situation where one dimension stays the same and the other changes. For example, inserting these into an empty SpatialTreeMap
(0,0)
(0,1)
results in the root is (0,0). But where do we put (0,1)? It could belong to NW or NE of (0,0). To resolve the ambiguity, you should give preference to the positive directions: North and East. In other words…
• put elements that lie on the line between NW and NE into NE.
• put elements that lie on the line between NE and SE into NE.
• put elements that lie on the line between NW and SW into NW.
• put elements that lie on the line between SW and SE into SE.
Copyright 2019, Brandon Myers
These cases will be covered properly if you use ≤ 𝑜𝑟 ≥ in the appropriate places.
Below is an illustration of this idea. It shows which parts of each axis belong to which quadrant.
Implement put
Implement the put method of SpatialTreeMap. Thanks to the wonderful abstractions of Positions and treeSearch, it should be almost identical to TreeMap’s put, except for some types.
Implement get
Implement the get method of SpatialTreeMap. Thanks to the magic of Positions and treeSearch, it should be almost identical to TreeMap’s get, except for some types.
Try SpatialTreeMapTest
You are now prepared to run the tests in SpatialTreeMapTest.java. You should debug your code until you pass…
• testSmallPut
• testMediumPut • testSmallGet
• testMediumGet
Together, these provide some coverage. However, they are not comprehensive tests, so we recommend
that you i) add more assertion statements to the existing tests and ii) add more test cases to provide yourself evidence that get and put work properly.
Run RandomDataPointQueries
A point query asks for a single datum from a Map. The RandomDataPointQueries program contains code to put random integer coordinates into a SpatialTreeMap strings and then get some of them. See if the code gets correct output.
You can change the random seed (see comments in code) to try it with other data.
Copyright 2019, Brandon Myers
Run EarthquakePointQueries
The file earthquakes.csv contains 1000’s of recorded earthquakes from ancient times to present day. Most of the records include the coordinates (latitude and longitude) of the earthquake. The EarthquakePointQueries program builds a Map of longitude/latitude -> CSVRecord. This allows us to look up earthquakes by coordinate.
STOP: Make sure you’ve made at least 1 commit with the title Part 2 in it.
Answer key – example 2
3, 2
Other resources
•
-3
,4
10, 12
7, 7
0, 0
-5, -6
6, -5
The quadtree in the following website (and most others) is not quite the same as the CS2230
quad tree. The following website distinguishes between rectangles and points, keeping
rectangles on the internal nodes and points on the external, while ours keeps data on every
node. Also, their bisection is based on the fixed coordinate space, while our bisection is based
on the data themselves. Yet, you might still find it generally helpful for understanding the
correspondence between the coordinate and tree views http://jimkang.com/quadtreevis/
Copyright 2019, Brandon Myers