A formal, hierarchical model of shape, spatial relations and non-spatial properties is presented, constructed from first principles of geometry, topology and logic. The combination of the two major paradigms used here, shape algebras and logic, is one which has been largely unexplored. The underlying interest is the development of generalized design modeling systems in which the components may be used for a variety of synthesis and recognition problems.
The algebras of shape described by Stiny have been shown to be useful in the generation and analysis of designs. The generality of their representations, their non-reliance upon predetermined structure, and their use in combination provide a richness of expression lacking in more traditional representations.
The use of formal logic as a specification tool for modeling spatial relations is investigated here. Logic has proven itself useful as a programming and specification tool, providing advantages over traditional procedural programming methods. Among those is the ability to specify the knowledge to be encapsulated in a model without the need to specify data manipulation procedures. It is argued that specification in logic provides a natural method of development.
The model is developed by extending the formalisms of shape algebras with the use of logic to make more precise, generalized, parametric definitions of shape and spatial relations than has been previously possible. The value of such a model is demonstrated by the use of these generalized spatial relations for solving typical problems in the fields of geographic information systems and architecture. The advantages of the representations used over more traditional "kit-of-parts" models is also illustrated.
Shape grammars have been shown to be a sophisticated and useful method of generating designs. They are a big step away from intuitive methods of design toward structured methods, but using them in a "manual" mode (non-computerized) still involves a great deal of intuition. As a well-structured method, they would seem to lend themselves well to computer implementations. Determining how one can effectively utilize these grammars in a computerized environment is important. A computer can find solutions that may not be obvious to the designer.
A formal representation of shapes as individuals is developed; some binary operations and relations are then defined upon shapes. The formal mechanisms of shape grammars are presented, with some of the computational problems illustrated. Algorithms to solve some of these problems are given.
The computer language Prolog is introduced and the differences between declarative and procedural programming are discussed. A Prolog implementation of a generic shape grammar system is demonstrated, as are its limitations.
Finally, alternative representations of shapes and shape grammars are mentioned.