- Forward


Partitioning Spatial Data
Software Design Considerations


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Qualitative Goals: A Reminder
Back SMYC Forward
  • Adequate - Meets all of the requirements and satisfies all of the constraints
  • Reliable - Low probability of failure under normal operating conditions
  • Robust - Able to operate under a wide variety of condtions
  • Safe - Able to minmize the damage resulting from failure
  • Easy to Repair and Enhance
  • Easy to Understand/Document and Use
  • Easy to Re-use
Motivation
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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
Back -