Monotone Polygon Intersection: Geometry, Computer Applications, and Computer Graphics

Abstract

Spatial queries are a fundamental class of queries on geographic data that consist primarily of points, lines, and polygons. Enhancing response time of spatial queries requires a spatial index. The chaintree is a dynamic spatial index structure being developed at RAND, based on a regular planar straight line graph. The chaintree organizes polygons to efficiently answer spatial queries. An operation basic to most chaintree procedures is polygon intersection. This Note presents a new algorithm for finding the intersection of two uniformly monotone polygons in linear time and space without preprocessing.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1991
Accession Number
ADA252538

Entities

People

  • Darrell H. Shane

Organizations

  • RAND Corporation

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Computer Graphics
  • Computer Science
  • Computers
  • Database Management Systems
  • Geometry
  • Graphics
  • Image Processing
  • Information Processing
  • Information Systems
  • Intervals
  • Monotone Functions
  • National Security
  • Numbers
  • Real Numbers

Fields of Study

  • Mathematics

Readers

  • Calculus or Mathematical Analysis
  • Computer Science.
  • Computer Vision.

Technology Areas

  • Space