Contents

• List of Figures
• Introduction
• Major Data Structures
• Theoretical Basis of the Algorithm
• Brief Algorithm
• Detailed, Efficient, Algorithm
  • General numerical speed
  • Using an expandable array to store the edges in each cell
  • Finding intersections
  • Locating the polygon containing each edge endpoint
  • Creating the one dimensional slab structure
  • Degenerate cases
• Error Control
• Design Tradeoffs and Choices Not Taken
  • Storing the vertices in a separate array and having the edges contain vertex numbers instead of vertex coordinates
  • Using integers instead of reals for coordinates
  • Splitting chains into separate edges
  • Storing the (cell, edge) information
• Implementation and Testing
• Possible Extensions
  • Producing the Overlay Polygons
  • The Cross-Area Problem
  • Overlaying multiple input maps simultaneously
  • Three Dimensional Overlaying
• Summary
• Acknowledgements
• References
• About this document ...