| Many new geometric and topological representations of shapes are being developed. Work in this area is motivated because of the need to provide computational models as a basis for computer systems that can manipulate spatial information. Topological representations are particularly important because (i) they can be used with a variety of different geometric primitives, and (ii) they correspond to the more intuitive, higher-level properties of shapes.;This thesis concentrates on the topological properties of two- and three-dimensional subdivisions of space. Subdivisions are characterized as simplicial complexes that are combinatorial manifolds. Two important pieces of information are needed to represent these subdivisions: adjacency and relative ordering. A relational model for storing this information is presented which is useful for accessing the information stored in a topological database. The mathematical properties of manifolds are used to develop various properties of a well-formed subdivision. These include valency restrictions on the number of adjacent elements, and generalizations of Euler operators for constructing subdivisions. A 2-d data structure, the half-edge, and a new 3-d data structure, the face-edge are analyzed. These data structures have two important properties: they occupy minimal space and all elemental adjacencies can be determined in time proportional to the number of neighboring elements. Finally, two applications of these principles are discussed. First, converting a line-drawing to a solid model, and second, testing for topological equivalence. |
