Partitioning Spatial Data

Partitioning Spatial Data
Software Design Considerations

Computer Science Department

bernstdh@jmu.edu

Qualitative Goals: A Reminder

Motivation

The Need for Partitioning:
- We need to be able to find the street's near the current location
- We need to display the map at an appropriate scale hence we can't display all of the streets
An Important Observation:
- We don't need to add or remove features in real-time

High Level Design Issues

An Observation:
- Streets are piecewise linear curves, not points
Issues:
- It may not be possible to have one street per cell
- A piecewise linear curve can "intersect" the window even when none of the break points do

High Level Design Issues (cont.)

Cells in a Parition:
- How can/should they be represented?
The Partition:
- What data structures can/should be used for a grid?
- What data structures can/should be used for a quad tree?

Detailed Design Issues (cont.)

Think About When you Project, Scale and Translate:
- GPS points are in lon./lat. and will need to be converted
- Some things must change every time the map pans/scrolls
Think About What Partitions to Draw:
- The aspect ratio of the window need no match the aspect ratio of the partitions

Detailed Design Issues (cont.)

Points:
- Do we need to add methods to calculate the corners of partition cells?
- Do we need to add methods to determine if a point is in a cell?
The PiecewiseLinearCurve Class:
- How can we determine if a Point is in a cell?
- How can we determine if a PiecewiseLinearCurve is in a cell?

There's Always More to Learn