Computation of Minimal Isovist Sets.

Abstract

A minimal isovist set (MIS) of a simple polygonal region P is a smallest set of points in P whose union of isovists equals P (where the isovist of x is the set of all points visible from x). This thesis represents an algorithm to search for an MIS for an arbitrary P. An MIS is shown to be equivalent to a minimal covering of P with star-shaped polygons. A (non-complete) algorithm to find a minimal covering is proposed which uses the vertices of the kernels of the star-shaped polygons. The complexity of finding an MIS is reduced to a worst-case consideration of no more than n to the 4th power points in P. A comparison of the proposed algorithm with two previously published algorithms is made. Extension of this method to exterior views and interior holes is discussd, and areas for future research are mentioned. Keywords: Shape analysis; Isovist sets; Visibility; Star-shaped regions. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1984
Accession Number
ADA157624

Entities

People

  • M. F. Doherty

Organizations

  • University of Maryland

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Autonomous Navigation
  • Computational Complexity
  • Computations
  • Computer Graphics
  • Computer Programs
  • Computer Science
  • Computers
  • Coverings
  • Geometry
  • Image Processing
  • Information Processing
  • Mathematical Analysis
  • Operating Systems
  • Pattern Recognition
  • Two Dimensional

Readers

  • Graph Algorithms and Convex Optimization.
  • Logistics and Supply Chain Management.