10.19.1.1. Spatial Data Structures¶

Fundamental idea: Need to treat X and Y dimensions as co-equal.

This requires different thinking from 1-dimensional key structures like BST or Hash Table

Support spatial queries: Records within radius of search point

10.19.1.2. Bintree (1)¶

Many variants and similar spatial data structures

PR quadtrees, k-d trees, and bintrees are common for storing point data

Decomposition rule: The rule that decides when to split the tree

Our rule: Only one point in a leaf

BUT: Splitting is useless if the points are the same!

So we don’t split when they are the same.

Keep on a list

10.19.1.3. Bintree (2)¶

10.19.1.4. Bintree Visualization¶

10.19.1.5. Ineractive Bintree¶

10.19.1.6. Implementation¶

Example: The world is 1024 units on each side (0..1023)

I define the origin as the upper left corner of the world square

The initial world is an empty box (1024 x 1024)

Different types of nodes:

Internal has 2 children (no data value)

Leaf with Seminar list (no children)

Leaf that is empty

10.19.1.7. Tree/Node Implementation (1)¶

Class hierarchy

Base node type: An interface

Internal nodes have 2 child pointers (no data)

Leaf nodes have no child pointers, store Seminars (unless empty)

How to implement empty nodes? There are a lot of them.

Definitely NOT as a null pointer!!

Avoid space concerns by implementing a Flyweight design pattern

Leaf can be a separate class, or not

Either way, it is a Singleton design pattern.

10.19.1.8. Tree/Node Implementation (2)¶

Tree initializes as an empty leaf node.

NO node stores its world box coordinates (pass them in)

All major tree methods (insert, remove, search, intersections) are implemented recursively.

NO use of parent pointers!

Composite design is natural here

10.19.1.9. Design Patterns (1)¶

• Design patterns capture reusable pieces of design wisdom.

• Goals:

  • Quickly communicate design wisdom to new designers

  • Give a shared vocabulary to designers

10.19.1.10. Design Patterns (2)¶

Three design patterns for Project 2:

Composite (will talk about in next section)

Flyweight

Everytime you need to point to an empty leaf, point to the same empty leaf.

By not using a null pointer, you can call operations on the object.

But you don’t pay any space for it!!

Of course, this means that it cannot have state

But your empty leaf node should not need state!

No storing the position/size. No storing parent pointers!

10.19.1.11. Design Patterns (3)¶

Singleton

There can be only one Flyweight object.

So need a way to control this – create it when you need it, but never again.

There are a few standard ways to do this. You can google for information.

The simplest approach is to:

Turn off the constructor (make it private)

Make clients go through getInstance() instead

Keep a static member which is the copy of the flyweight that you create only one time.