Partitioning Spatial Data

Partitioning Spatial Data
Software Design Considerations

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Qualitative Goals: A Reminder

Motivation

The Need for Partitioning:
- We need to display the map at an appropriate scale hence we can't display all of the streets
- We need to be able to find the street's near the current location
Some Important Observations:
- We don't need to add or remove features in real-time
- Since we are drawing a relatively small number of features, draw() will execute more quickly

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

Think About What draw() Needs:
- It certainly needs to be able to retrieve the appropriate partition
Think About When to Call startDisplay():
- The method that handles GPS points needs to determine if the point is in the partition that is being displayed
- If a new partition needs to be displayed you must call startDisplay()

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.)

The Point Class:
- 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?