Shape grammars

There are various grammar formalisms for design, with different requirements for the representation, interpretation, and generation of entities. Most examples of shape grammars rely on labeled shapes, a combination of – often two-dimensional – line segments and labeled points (Stiny, Reference Stiny1980). Stiny (Reference Stiny1992) proposes numeric weights as attributes to denote line thicknesses or surface tones. Knight (Reference Knight1989, Reference Knight1993) considers a variety of qualitative aspects of design as shape attributes. Stiny (Reference Stiny1981) proposes to augment shape grammars with description functions in order to enable the construction of verbal descriptions of designs. Stouffs and Krishnamurti (Reference Stouffs, Krishnamurti and Gero2002) propose sortal grammars using a compositional approach to the representational structures underlying (augmented) shape grammars, allowing the definition and exploration of a variety of grammar formalisms.

Stouffs (Reference Stouffs2018) addresses the problem of implementing a shape grammar interpreter that supports varying shape grammar formalisms. He proposes an algebraic treatment that facilitates a modular approach based on a connection between algebraic abstraction and procedural abstraction (Frank, Reference Frank1999). However, he does not address parametric shape grammars and only touches upon transformations other than similarity. Nevertheless, his approach could include parametric shape grammars and shape grammars allowing for arbitrary transformations as well. In this paper, we address the algorithmic complexity of implementing such transformations.

Shape grammar implementations: the state of the art

Ideally, a shape grammar implementation should: (1) support visual computing, (2) allow emergence, (3) not rely on pre-defined parts, and (4) be parametric (Gips, Reference Gips1999).

Shapes have explicit definitions, but indefinitely many “touchable” parts, all of which can become a focus of design intent. These parts emerge under the part relation, regardless of whether they were originally envisioned as such. The concept of emergent shapes describes creative design activities, in the sense that looking at a design provides new insights that lead to a new interpretation of existing design elements. Continuity of visual computations requires an anticipation of the structures that are to be changed (Krishnamurti & Stouffs, Reference Krishnamurti and Stouffs1997), but creativity is devoid of anticipation and instead relies on a restructuring of information. The concept of emergent shapes thus is highly relevant for design search (Mitchell, Reference Mitchell, Gero and Maher1993; Stiny, Reference Stiny1994). Emergence is challenging to implement, however, which is why many implementations do not support it (Chau et al., Reference Chau, Chen, McKay and de Pennington2004).

A corollary to supporting emergence is that an implementation cannot rely on pre-defined geometrical parts since it is impossible to predict which parts of a shape a designer might choose to develop further. Employing pre-defined parts thus involves assumptions about what a designer might want to do. For example, the geometric primitives provided in CAD programs make certain shapes easier to draw and manipulate than others. Shape grammars eliminate hierarchies and overlaps between parts and allow arbitrary de- and recomposition (Stiny, Reference Stiny1994).

Parametric shape grammars allow more flexible rule applications compared with non-parametric ones. As discussed in the section “Sets of transformations”, the distinction between parametric and non-parametric grammars can be understood as a special case of the type of transformations under which a visual calculation accepts shapes as isomorphic.

Non-parametric shape grammar implementation is well researched, with a successful implementation presented by Tapia (Reference Tapia1999). Current research focuses on parametric shape grammar implementations based on graphs (Grasl & Economou, Reference Grasl and Economou2013; Wortmann, Reference Wortmann2013; Yue & Krishnamurti, Reference Yue and Krishnamurti2013; Strobbe et al., Reference Strobbe, Pauwels, Verstraeten, De Meyer and Van Campenhout2015), since graphs avoid pre-defined parts and provide the needed flexibility to support both emergence and parametric transformations.

The subshape detection problem

The central problem for shape grammar implementations that support emergence is the matching problem. This problem is termed subshape detection. A solution to this problem consists of finding a correspondence between the spatial elements in the left-hand side of a shape rule (the input shape) and a part of a given design (the target shape) and of determining the transformation (matrix) that represents this correspondence. If such a correspondence is found, the input shape and the target shape are isomorphic to each other.

The equivalent problems for set and graph grammars, termed subset and subgraph detection, consist of searching for either a single entity or a group of entities within a set or graph. This search is straightforward – it requires a one-to-one matching of entities that are identical under a certain transformation – but not always computationally efficient. The subgraph isomorphism problem, for example, is NP-complete (Garey & Johnson, Reference Garey and Johnson1979), which means that there is no known algorithm that can solve problems of this type efficiently, i.e., in polynomial time. But the ability to replace spatially any subshape of a shape is a prime requirement for visual calculations.

Algorithmic complexity

A fundamental issue for shape grammar implementations is algorithmic complexity, which is a measure of the number of steps required by an algorithm. Algorithmic complexity measures this number of steps not directly, but asymptotically, that is, it describes the type of growth of this number as the size of the input for the algorithm increases. [Algorithmic complexity is indicated in Big-O notation (Cormen et al., Reference Cormen, Leiserson, Rivest and Stein2009), with O(n^k) indicating an upper and Ω(n^j) a lower bound. In other words, for inputs of size n, the algorithm that takes at most n^k and at least n^j steps.]

A problem is tractable when an algorithm with polynomial complexity is available (i.e., the number of steps is bounded by some n^k, where n is the size of the input and k is a constant) and intractable when there is none. Intractable problems – which often also are NP-complete or NP-hard – can be very slow, or even impossible, to compute. In practice, such problems are solved by approximation algorithms, but such approximations might not be acceptable in terms of the envisioned use of shape grammar implementations. For example, a designer might want to see all ways to apply a rule, and not only some, or even require the full enumeration of a grammar. Tractability thus is a key consideration for interactive shape grammar implementations which aim to provide quick feedback to designers.

Even for tractable problems, it is important whether their algorithmic complexity is constant [O(1)], linear [O(n)], linearithmic [O(n log n)], or another polynomial such as [O(n^k)]. Note that polynomial algorithms can still be slow, especially for larger inputs n and values of k >2.

Algorithmic complexity of shape grammar implementations

Despite the great relevance of algorithmic complexity, the literature on shape grammar implementations discusses it only rarely. For subshape detection for non-parametric shape grammars, Krishnamurti (Reference Krishnamurti1981) provides a polynomial algorithm that tests matches between the target shape and the design in terms of comparing triplets of intersection points. For n maximal elements, this algorithm tests O(n ⁴) triplets (actually, combinations of two intersection points with the third point constructed from these two points) drawn from O(n ²) intersection points. Trescak et al. (Reference Trescak, Esteva and Rodriguez2012) propose an improved version of this algorithm that sorts the triplets in terms of their angles, which avoids more time-intensive tests but does not improve algorithmic complexity.

The parametric shape grammar implementation of Grasl and Economou (Reference Grasl and Economou2013) achieves subshape detection through non-planar subgraph matching, which is NP-complete. Yue and Krishnamurti (Reference Yue and Krishnamurti2013) argue that subshape detection for parametric shape grammars is NP-complete in general. Their proof rests on the claim that – by converting a graph into a shape – one could use a hypothetical, polynomial-time subshape detection algorithm for subgraph matching. But the existence of such an algorithm would contradict the fact that subgraph matching is NP-complete. However, subgraph matching is NP-complete only for non-planar graphs (Dorn, Reference Dorn2010). For planar graphs, it is linear in the size of the graph and exponential in the size of the subgraph, or 2^O(k)n. One could thus use the hypothetical, polynomial-time subshape detection algorithm for planar subgraph detection without contradiction. In other words, we hypothesize that there is no bijective mapping between graphs and shapes: for shapes, intersection points are an inevitable result of intersecting maximal elements, while for graphs, intersecting edges does not result in a new vertex (Wortmann, Reference Wortmann2013). This paper presents a subshape detection algorithm whose complexity is similar to the result for subgraph isomorphism by Dorn (Reference Dorn2010).

Beyond subshape detection, Yue and Krishnamurti (Reference Yue and Krishnamurti2013) identify three factors influencing the tractability – and thus algorithmic complexity – of shape grammar implementations: operations on shapes, the potential number of matching instances where a rule can be applied, and indeterminacy of rule application. Another factor for the algorithmic complexity of shape grammar implementations is the data structure used for representing shapes. In the analysis by Wortmann (Reference Wortmann2013) of different graph data structures used for shapes, the smallest representations are quadratic, or Θ(n ²). This paper discusses the algorithmic complexity of the number of matching instances in terms of different sets of (parametric and non-parametric) transformations.

Translated

In this category, the only allowed transformation is a translation. In other words, a shape can only be moved, but not rotated or mirrored. Consequently, there is only one way in which a rule that copies and moves a square diagonally can apply to the squares of the translated derivation in Figure 2, resulting in a purely diagonal arrangement. In practice, translation-only shape grammars are rare, most likely due to their limited formal possibilities.

Fig. 2. Derivations based on the same initial shape (a square) and the same shape rule applied under different transformations: translated, isometric, similar, and matrix (from left to right).

Isometric

The isometric, or Euclidean, transformations include translation, rotation, and reflection. As implied by the term “rigid”, these transformations preserve a shape's size, proportions, and angles, though not necessarily its orientation. The isometric derivation in Figure 2 applies the rule as the translated derivation, but in different orientations. However, the rule cannot apply to the smaller and larger squares that emerge from the overlap of the original ones, since isometry does not include scaling.

Although one can achieve the formal possibilities of an isometric shape grammar also within a translated one (by adding individual rules for symmetries and rotations), isometric shape grammars allow geometric precision with a more economical set of rules. This precision makes them especially applicable to traditional architectural designs methods that emphasize proportions and measurements. A classic example of an isometric grammar is the Palladian Grammar (Stiny & Mitchell, Reference Stiny and Mitchell1978b). [Note that the Palladian grammar, in principle, allows for (non-uniform) scaling, as the size of the grid cell may vary.]

Similar

Similarity transformations include uniform scaling in addition to the Euclidean transformations. Uniform scaling preserves a shape's proportions and angles, but not its size, as is visible in the similar derivation in Figure 2. In contrast to isometry, in this case, the same rule can apply to different-sized squares. Like fractal patterns, similarity-based shape grammars operate on different scales. Accordingly, they are suitable for abstract, scale-less pattern designs such as the Sierpinski gasket (Yue & Krishnamurti, Reference Yue and Krishnamurti2014).

Matrix

This category includes all transformations that can be expressed as a transformation matrix, such as affine and projective transformations (transformation matrices are convenient for computer implementation). Matrix transformations include translation, isometry, and similarity, as well as linear transformations. Linear transformations include both affine and projective transformations. Projective transformations, for example, perspective projections, do not preserve the angles and proportions of a shape, in contrast to more general characteristics, like maximal elements, intersections, and convexity. Affine transformations preserve parallel lines and ratios of distances as well. In the projective (matrix) derivation in Figure 2, starting with an initial shape including only horizontal and vertical lines, and applying a shape rule that adds only parallel lines, the derivation also includes only horizontal and vertical lines.

Matrix-based shape grammars are parametric in the sense that they guide rule-application not with numerical criteria such as lengths and angles, but with topological criteria such as the number of maximal elements, closure, convexity, etc. Stiny (Reference Stiny1980) refers to such grammars as having open terms. For example, Tapia (Reference Tapia1992) implements the ice ray grammar of Chinese lattice designs (Stiny, Reference Stiny1977) as a parametric grammar that allows triangles of any kind as inputs and preserves not the proportions, but only the number of sides of output shapes.

Arbitrary

This last category includes all transformations, including ones that transformation matrices cannot express. Stiny (Reference Stiny1990) discusses the application of visual rules in terms of arbitrary transformations t. For example, shape isomorphism can be defined topologically based on relations of connectivity between maximal elements. One can also preserve other characteristics such as the convexity or number of sides of a shape. Other possibilities include basing shape isomorphism on the area enclosed by a shape, or the fact that a shape is a polygon, etc. To analyze the algorithmic complexity of different sets of transformations, this paper examines only cases where the number of maximal elements is invariant.

With this flexibility of rule application, Stiny (Reference Stiny2011) intends to preserve a maximum of design freedom. Per this view, shape grammars are a special case of calculating with visual rules, in that they restrict visual calculations to a set of rules and transformations. As a general design method, visual calculating does not require such restrictions. However, the next section shows how the increasing computational complexity of the sets of transformations results in algorithmic restrictions in terms of generalized shape grammar implementations.

Limitations

The analysis has two limitations: (1) It assumes that, in the parametric case, all maximal elements intersect each other and (2) only considers closed quadrilaterals as target shapes. For the parametric case, the analysis generalizes to target shapes with arbitrary numbers of maximal elements. These limitations are justifiable in terms of proving lower bounds for algorithmic complexity because removing them would only increase this complexity and makes implementation more challenging. For example, graph-based shape grammar implementations often represent maximal line segments as portions of infinite lines. In this case, non-closed shapes become a special case of closed ones. In addition, note that the resulting bounds do not consider the complexity of representing shapes (Wortmann, Reference Wortmann2013) and the complexity of subshape detection. (In other words, we consider how many subshapes one would need to find, not how to find them.) Nevertheless, the resulting bounds provide guidance for the design of general shape grammar implementations.

Translated and isometric

Let n/2 parallel, equidistant, horizontal maximal elements intersect with n/2 parallel, equidistant, vertical maximal elements. Then the total number of maximal elements is n, and the largest number of identical squares under translation is (n/2 − 1)² or n ²/4 − n + 1. Consequently, the algorithmic complexity to find all target shapes for a rule having such a square as an input is Ω(n ²). For example, the 4 × 4 grid of eight lines in Figure 4a yields two (vertical and horizontal) sets of 8/2 − 1 = 3 columns, in Figure 4b. Squaring, that is, intersecting the two sets of three columns yields nine identical, translated squares. When isometry also is admissible, every square can be rotated four times and mirrored, which yields eight target shapes per square. However, this linear increase does not affect the quadratic bound already established for translation.

Fig. 4. Diagrams illustrating the derivation of the lower bounds. Panels (a) and (b) illustrate translation and isometry, (a)–(d) similarity, and (e) matrix and arbitrary.

Similar

Once one admits also similarity transformations, target shapes of different sizes become targets for rule application. That is, we should consider not only the (n/2 − 1)² squares in the original grid, but also squares resulting from grids with a smaller number of maximal elements, such as [(n − 2)/(2 − 1)]², [(n − 4)/(2 − 1)]², …, [4/(2 − 1)]². In other words, one can combine different sets of smaller squares into bigger squares. For example, the 4 × 4 grid of eight lines in Figure 4a yields two (vertical and horizontal) sets of (8 − 2)/2 − 1 = 2 overlapping columns, in Figure 4c. Squaring, that is, intersecting the two sets of two columns yields four identical, translated squares. Likewise, in Figure 4d, there are two sets of (8 − 4)/2 − 1 = 1 columns, which yield one square.

The resulting number of squares is a quadratic series. The sum of such a series (Sloane & Arndt, Reference Sloane and Arndt2010) – also known as the sum of square pyramidal numbers – can be expressed like this:

$$\eqalign{ 1^2 + 2^2 + 3^2 + \,\cdots\, + m^2 & = \mathop \sum \limits_1^m k^2 =\, \displaystyle{{m\lpar {m + 1} \rpar \lpar {2m + 1} \rpar } \over 6} \cr &= \displaystyle{{m^3} \over 3} \,+\, \displaystyle{{m^2} \over 2} \,+\, \displaystyle{m \over 6}.} $$

Considered in terms of the number of maximal elements n, m = n/2 − 1. Asymptotically, the potential number of target shapes under similarity transformations is cubic or Ω(n ³).

Matrix and arbitrary

In the parametric case, any combination of four maximal elements forms a quadrilateral (if all maximal lines intersect each other), and thus is a potential target for rule application. Figure 4e shows how three intersecting lines always form a triangle, and how the fourth line cuts this triangle into two smaller triangles and one quadrilateral. In the worst case for affine transformations, all quadrilaterals could also be isomorphic in terms of affinity. An algorithm for subshape detection in the affine case would thus have to test for every quadrilateral if there exists an affine transformation matrix that maps it onto an input shape.

Even under non-linear transformations, one might want to retain the distinction between convex and concave shapes. However, this distinction at best halves the number of potential target shapes, and thus has no impact on algorithmic complexity.

If one retains the number of maximal elements k as an invariant between input and target shapes, one can express the number of potential target shapes for input shapes with n-maximal elements as a combination, multiplied by eight to account for rotations and symmetry:

$$8\left( {\matrix{ n \cr k \cr}} \right) = \displaystyle{{8n!} \over {k!\lpar {n - k} \rpar !}}.$$

Asymptotically, for a quadrilateral input shape, the potential number of target shapes is Ω(n ⁴). In general, this expression is Ω(n^k). When k grows close to n/2, the expression becomes non-polynomial. However, even in the polynomial case, one can expect the performance of a parametric shape grammar implementation to deteriorate rapidly as input shapes become more complicated and the overall design grows larger. Note that this result is similar to the bound for planar subgraph isomorphism by Dorn (Reference Dorn2010).

Consequently, the most critical factor for the algorithmic complexity of parametric shape grammar implementations is the size of the input shapes. In the general case, parametric subshape recognition is non-polynomial, even with a hypothetical, linear time subshape detection algorithm. One can limit combinatorial explosion by introducing additional criteria for mapping shapes, such as convexity, proportions, closure, etc. Nevertheless, this result highlights an acute challenge.

Yue and Krishnamurti (Reference Yue and Krishnamurti2013) present a similar result in terms of the open terms of parametric shape grammars and argue that this number is “usually small enough for their time complexity to be relatively inexpensive”. Indeed, for individual grammars, it is often possible to design more efficient parametric implementations (Stouffs, Reference Stouffs2017). However, one cannot assume such efficiency for designers that use a parametric shape grammar implementation for design exploration. In this case, quite complex input shapes might arise easily.

Grasl and Economou (Reference Grasl and Economou2013) report benchmark results of their parametric shape grammar implementation, searching for parametric quadrilaterals in a grid similar to the ones presented in Figure 3. They employ the subgraph detection algorithm by Batz (Reference Batz2006), which – in a square grid consisting of 22 maximal elements – finds all 3.025 quadrilaterals in about 500 milliseconds. However, for targets shapes with more than four maximal elements, the number of targets would increase rapidly, which would arguably affect the subgraph detection algorithm's performance.

Strobbe et al. (Reference Strobbe, Pauwels, Verstraeten, De Meyer and Van Campenhout2015) employ a similar graph-matching algorithm for subshape detection. They report a running time that is exponential in terms of the size of the design but “reasonably low (<2 s)” for a floorplan with about 30 rooms. However, they also do not consider the size of the input shape, which again is only a quadrilateral.

One should also note that both benchmarks only use two-dimensional line segments. The impact of more complex geometries on the performance of parametric grammar implementations (Stouffs & Krishnamurti, Reference Stouffs and Krishnamurti2006) would probably be considerable and deserves further study.

Non-parametric (translated, isometric, and similar)

In two dimensions, only two distinct points are needed to determine any similarity transformation, except for a reflection about the axis connecting both points. For shapes made up only of k line segments, as considered here, three infinite lines, not all parallel, result in at least two intersection points, yielding two (or three) distinct points. Specifically, when no two lines are parallel, there are three distinct intersection points. Otherwise, a third distinct point can always be constructed at a perpendicular angle from the axis connecting both points and at a distance equal between the two existing points (Krishnamurti, Reference Krishnamurti1981). In both cases, non-parametric subshape detection requires the matching of three maximal lines with at least two intersections. Once a similarity transformation is found, one can verify the matching in O(k) steps. As such, the algorithm presented by Trescak et al. (Reference Trescak, Esteva and Rodriguez2012) considering triplets of intersection points, while ordering them by angle and ratio of lengths, is unnecessarily complex. Considering n maximal lines, the number of intersection points is O(n ²), and there are O(n ⁶) triplets to be considered. But the number of triplets of maximal elements is only O(n ³) and angles and ratios of lengths can still be used to quickly reduce potential matches. Note that this is also the potential number of target shapes under similarity transformations, providing a tight bound.

Parametric (matrix and arbitrary)

With Ω(n^k) as the lower bound for parametric target shapes established in the section “Matrix and arbitrary”, one can sketch a subshape detection algorithm and analyze its complexity: Given an input shape s with k maximal elements, one can compare it with a potential target shape t by a pairwise comparison of the elements and their labels. Such labels can denote invariants such as intersections with other elements, convexity, line segments, etc. (Wortmann, Reference Wortmann2013). First, we compute the O(k ²) intersections for s and t. For every element of t, we then perform a pairwise comparison with the elements of s. This comparison verifies the connection between elements and matches between labels. Using tree search to traverse t, each comparison would take O(k ²). These tree searches are easy to parallelize. Note that, in this case, we do not search for emergent subshapes, but check only whether two shapes are isomorphic, which is an easier problem. To perform comparisons for all elements then takes O(k ³). We must perform this test for all candidate target shapes, which yields a tight bound of O(n^k). Note that, depending on the size of k, this bound is exponential in the worst case, although one can use labels to limit the combinatorial explosion. Note that the above, non-parametric subshape detection algorithm is a special case of the parametric one since both rest on the general principle of comparing combinations of maximal elements for isomorphism.

A graph-based variant of this algorithm would convert s and t into planar graphs. In this case, a planar graph representation is possible, because the representation does not need to account for emergent subshapes (Wortmann, Reference Wortmann2013). Isomorphism for planar, connected, undirected, and unlabeled graphs is possible in O(k ³) as well (Kukluk et al., Reference Kukluk, Holder and Cook2004), resulting in the same overall complexity (since labels would decrease, rather than increase, the complexity of the comparison).