Computation of Minimal Isovist Sets

摘要

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