# HampshireCS/CS112-Spring2012

Fetching latest commit…
Cannot retrieve the latest commit at this time.

# Homework 19

In this assignment, you will be fleshing out a Quadtree. Quadtrees are traditionally used in graphics programming to quickly eliminate large groups of points.

QuadTreeNode is already mostly a quadtree. However, in order to actually use it in a program, there should be easier ways to access the data inside the QuadTree. Specifically, we need a way to get a list of all the points in the quadtree and a way to get every rectangle (quadrents).

As you add the methods in this homework, run `test_quad.py` to run the normal battery of unit tests to see if it works. Once you are completely done, you can use `./rundemo` to run a graphical demo to see your quadtree in action.

`rundemo` is a python file so can just be opened in IDLE on Windows.

### Getting the Points (get_points)

Add a method `get_points` to QuadTreeNode. This method will fetch a list of every point stored in a QuadTreeNode and it's children. Since each

Requirements:

• if there are no points, return an empty list
• if there is only one point, return a list with only that point in it
• if there is more than one point, return a list with every point
• the order the points are output doesn't matter

Example:

```>>> qtree = QuadTreeNode(Rect(0, 0, 100, 100))
>>> # no points
>>> qtree.get_points()
[]
>>> # one point
>>> qtree.get_points()
[ (25,25) ]
>>> # many points
[ (25,25), (75, 75), (22, 22) ]```

Add a method `get_rects` which fetches every rectangle out of a QuadTree. This includes the root node and its children if it has any and so on. This should be a flat list of rectangles (not lists in lists).

Requirements:

• if there are zero/one points, return just the root rect
• if there is more than one point, return the root rect and all it's children
• if there is more than one level of nesting, return nested child.
• order of rects doesn't matter

HINT: You can use an optional `rects` parameter to keep track of all the rects as you add them. Since arrays are a reference, adding a rect to an array as you recurse is a good way to track all the values

Example:

```>>> qtree = QuadTreeNode(Rect(0, 0, 100, 100))
>>> # no points
>>> qtree.get_rects()
[<rect(0, 0, 100, 100)>]
>>> # one point
>>> qtree.get_rects()
[<rect(0, 0, 100, 100)>]
>>> # two points in different quadrents
>>> qtree.get_rects()
[<rect(0, 0, 100, 100)>, <rect(0, 0, 50, 50)>, <rect(50, 0, 50, 50)>, <rect(0, 50, 50, 50)>, <rect(50, 50, 50, 50)>]
>>> # two points in the same quadrent
>>> qtree.get_rects()
[<rect(0, 0, 100, 100)>, <rect(0, 0, 50, 50)>, <rect(0, 0, 25, 25)>, <rect(25, 0, 25, 25)>, <rect(0, 25, 25, 25)>, <rect(25, 25, 25, 25)>, <rect(25, 0, 25, 25)>, <rect(0, 25, 25, 25)>, <rect(25, 25, 25, 25)>]```

Add a method `collidepoint` which returns the smallest QuadTreeNode which collides with a given point.