Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-02T23:18:46.321Z Has data issue: false hasContentIssue false
  • English
  • Français

Modelling spatial reasoning systems with shape algebras and formal logic

Published online by Cambridge University Press:  27 February 2009

Scott C. Chase
Scott C. Chase
Affiliation:
National Institute of Standards and Technology, Manufacturing Systems Integration Division, Gaithersburg, MD 20899–0001, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

The combination of the paradigms of shape algebras and predicate logic representations, used in a new method for describing designs, is presented. First-order predicate logic provides a natural, intuitive way of representing shapes and spatial relations in the development of complete computer systems for reasoning about designs. Shape algebraic formalisms have advantages over more traditional representations of geometric objects. Here we illustrate the definition of a large set of high-level design relations from a small set of simple structures and spatial relations, with examples from the domains of geographic information systems and architecture.

Keywords

Shape AlgebrasShape GrammarsFeature EmergenceFeature RecognitionFormal Logic
Type
Articles
Information
AI EDAM , Volume 11 , Issue 4 , September 1997 , pp. 273 - 285
Copyright
Copyright © Cambridge University Press 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Akiner, V.T. (1986). Topology-1: A knowledge-based system for reasoning about objects and space. Design Studies 7(2), 94–105.CrossRefGoogle Scholar
Arbab, F., & Wing, J.M. (1987). Geometric reasoning: A new paradigm for processing geometric information. In Design Theory for CAD, (Yoshikawa, H., Warman, E.A., Eds.), pp. 145–159. North-Holland, Amsterdam.Google Scholar
Brown, K.N., McMahon, C.A., & Sims Williams, J.H. (1995). Features, aka the semantics of a formal language of manufacturing. Res. Eng. Design 7(3), 151–172.CrossRefGoogle Scholar
Carlson, C. (1994). A tutorial introduction to grammatical programming. In Formal Design Methods for CAD, (Gero, J.S., Tyugu, E., Eds.), pp. 73–84. North-Holland, Amsterdam.Google Scholar
Chase, S.C. (1989). Shapes and shape grammars: From mathematical model to computer implementation. Environ. Plann. B: Plann. Design 16(2), 215–242.CrossRefGoogle Scholar
Chase, S.C. (1993). The use of multiple representations to facilitate design interpretation. Proc. ARECDAO '93, 205–217.Google Scholar
Chase, S.C. (1996). Modeling designs with shape algebras and formal logic. PhD dissertation, University of California, Los Angeles.CrossRefGoogle Scholar
Cherneff, J. (1990). Knowledge based interpretation of architectural drawings. Report R90–13 (IESL 90–05). MIT, Cambridge, MA.Google Scholar
Coyne, R.D., Rosenman, M.A., Radford, A.D., Balachandran, M., & Gero, J.S. (1990). Knowledge-based design systems. Addison-Wesley, Reading, MA.Google Scholar
Eastman, C.M. (1978). The representation of design problems and maintenance of their structure. In Artificial Intelligence and Pattern Recognition in Computer Aided Design, (Latombe, J.C., Ed.), pp. 335–357. North-Holland, New York.Google Scholar
Eastman, C.M., Bond, A.H., & Chase, S.C. (1991). A formal approach for product model information. Res. Eng. Design 2, 65–80.CrossRefGoogle Scholar
Fu, Z., & de Pennington, A. (1994). Geometric reasoning based on graph grammar parsing. J. Mechanical Design 116(3), 763–769.CrossRefGoogle Scholar
Heisserman, J. (1994). Generative geometric design. IEEE Comput. Graphics Applications 14(2), 37–45.CrossRefGoogle Scholar
Henderson, M.R. (1984). Extraction of feature information from three dimensional CAD data. PhD dissertation, Purdue University.Google Scholar
Hofstadter, D.R. (1979). Gödel, Escher, Bach: An eternal golden braid. Basic Books, New York.Google Scholar
Hoskins, E.M. (1973). Computer aids in system building. In Computer-Aided Design, (Vlietstra, J. & Wielinga, R.F., Eds.), pp. 127–140. North-Holland, Amsterdam.Google Scholar
Jaffar, J., Michaylov, S., Stuckey, P.J., & Yan, R.H.C. (1992). The CLP(ℛ) language and system. ACM Transactions Programming Languages Syst. 14(3), 339–395.CrossRefGoogle Scholar
Knight, T.W. (1980). The generation of Hepplewhite-style chair-back designs. Environ. Plann. B 7, 227–238.CrossRefGoogle Scholar
Koning, H., & Eizenberg, J. (1981). The language of the prairie: Frank Lloyd Wright's prairie houses. Environ. Plann. B 8, 295–323.CrossRefGoogle Scholar
Koutamanis, A. (1990). Development of a computerized handbook of architectural plans. PhD dissertation, Delft University of Technology.Google Scholar
Kowalski, R.A. (1979). Logic for problem solving. North-Holland, New York.Google Scholar
Krishnamurti, R. (1980). The arithmetic of shapes. Environ. Plann. B 7, 463–484.CrossRefGoogle Scholar
Krishnamurti, R. (1981). The construction of shapes. Environ. Plann. B 8, 5–40.CrossRefGoogle Scholar
Krishnamurti, R. (1992 a). The arithmetic of maximal planes. Environ. Plann. B: Plann. Design 19, 431–464.CrossRefGoogle Scholar
Krishnamurti, R. (1992 b). The maximal representation of a shape. Environ. Plann. B: Plann. Design 19, 267–288.CrossRefGoogle Scholar
Krishnamurti, R., & Giraud, C. (1986). Towards a shape editor: The implementation of a shape generation system. Environ. Plann. B: Plann. Design 13, 391–404.CrossRefGoogle Scholar
Krishnamurti, R., & Stouffs, R. (1997). Spatial change: Continuity, reversibility and emergent shapes. Environ. Plann. B: Plann. Design 24, 359–384.CrossRefGoogle Scholar
Mitchell, W.J. (1990). The logic of architecture. MIT Press, Cambridge, MA.Google Scholar
Preparata, F.P., & Shamos, M.I. (1985). Computational geometry: An introduction. Springer-Verlag, New York.CrossRefGoogle Scholar
Robinove, C.J. (1986). Principles of logic and the use of digital geographic information systems. Circular 977, Dept. of the Interior, U.S. Geological Survey.CrossRefGoogle Scholar
Rosen, D.W., Dixon, J.R., & Finger, S. (1994). Conversions of feature-based design representations using graph grammar parsing. J. Mechanical Design 116(3), 785–792.CrossRefGoogle Scholar
Stiny, G. (1977). Ice-ray: A note on the generation of Chinese lattice designs. Environ. Plann. B 4, 89–98.CrossRefGoogle Scholar
Stiny, G. (1981). A note on the description of designs. Environ. Plann. B 8, 257–267.CrossRefGoogle Scholar
Stiny, G. (1989). Formal devices for design. In Design Theory '88, (New-some, S.L., Spillers, W., & Finger, S., Eds.), pp. 173–188. Springer-Verlag, New York.Google Scholar
Stiny, G. (1991). The algebras of design. Res. Eng. Design 2, 171–181.CrossRefGoogle Scholar
Stiny, G. (1992). Weights. Environ. Plann. B: Plann. Design 19, 413–430.CrossRefGoogle Scholar
Stiny, G., & Gips, J. (1972). Shape grammars and the generative specification of painting and sculpture. In Information Processing 71, (Freiman, C.V., Ed.), pp. 1460–1465. North-Holland, Amsterdam.Google Scholar
Stiny, G., & Mitchell, W.J. (1978). The Palladian grammar. Environ. Plann. B 5, 5–18.CrossRefGoogle Scholar
Stouffs, R., & Krishnamurti, R. (1993). The complexity of the maximal representation of shapes. Proc. 1F1P TC5/WC5.2 Workshop on Formal Methods for Computer-Aided Design, 53–66.Google Scholar
Tapia, M. (1992). Chinese lattice designs and parametric shape grammars. The Visual Comput. 9, 47–56.CrossRefGoogle Scholar
Tapia, M.A. (1996). From shape to style, shape grammars: Issues in representation and computation, presentation and selection. PhD dissertation, University of Toronto.Google Scholar