The spatial synthesis problem addressed in this paper is the configuration of rectangles in 2D space, where the sides of the rectangles are parallel to an orthogonal coordinate system. Variables are the locations of the edges of the rectangles and their orientations. Algebraic constraints on these variables define a layout and constitute a constraint satisfaction problem. We give a new O(n2) algorithm for incremental path-consistency, which is applied after adding each algebraic constraint. Problem requirements are formulated as spatial relations between the rectangles, for example, adjacency, minimum distance, and nonoverlap. Spatial relations are expressed by Boolean combinations of the algebraic constraints; called disjunctive constraints. Solutions are generated by backtracking search, which selects a disjunctive constraint and instantiates its disjuncts. The selected disjuncts describe an equivalence class of configurations that is a significantly different solution. This method generates the set of significantly different solutions that satisfy all the requirements. The order of instantiating disjunctive constraints is critical for search efficiency. It is determined dynamically at each search state, using functions of heuristic measures called textures. Textures implement fail-first and prune-early strategies. Extensions to the model, that is, 3D configurations, configurations of nonrectangular shapes, constraint relaxation, optimization, and adding new rectangles during search are discussed.

Because mechanical operations are performed only up to a certain precision, the geometry of parts involved in real-life products is never known precisely. But if tolerance models for specifying acceptable variations have received a substantial attention, operations on toleranced objects have not been studied extensively. That is the reason why we address in this paper the computation of the union and the intersection of toleranced simple polygons, under a simple and already known tolerance model. First, we provide a practical and efficient algorithm that stores in an implicit data structure the information necessary to answer a request for specific values of the tolerances without performing a computation from scratch. If the polygons are of sizes m and n, and s is the number of intersections between edges occurring for all the combinations of tolerance values, the preprocessed data structure takes O(s) space and the algorithm that computes a union/intersection from it takes O((n + m)log s + k' + k log k) time, where k is the number of vertices of the union/intersection and k ≤ k' ≤ s. Although the algorithm is not output sensitive, we show that the expectations of k and k' remain within a constant factor τ, a function of the input geometry. Second, we define and study the stability of union or intersection features. Third, we list interesting applications of the algorithms related to feasibility of assembly and assembly sequencing of real assemblies.

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.

Few existing Computer Aided Design (CAD) systems provide assistance to designers in developing geometric concepts at the early design stages. Instead they require a high level of precision and detail suited to detail design. To support the early geometric design, a CAD system should provide utilities for the rapid capture and iterative development of vague geometric models. This paper presents a pilot system that is being developed based on such a vision. The system has adopted minimum commitment modelling and incremental refinement as the guiding principles. The representation of geometric configuration is based on a parametric and constraint-based geometric design model, and provides a uniform representation of the approximate and precise size and location parameters. A constraint-based mechanism has been developed for processing geometric information. The use of the system in assisting the development of a geometric configuration is also demonstrated. Finally, features and limitations of the system as well as relations to relevant works are discussed, and based on this a number of key research directions are established.

The “sketch” drawn by a human designer represents a shape class of wider variability than can be captured by traditional CAD models; these typically work with parametrizations based on a nearly finished shape. Traditional Qualitative Reasoning is also unable to model this degree of ambiguity in shape. Cognitively, shapes are often represented in terms of an axial model. In defining 2D contours, such an axial representation is called the Medial Axis Transform or MAT. By perturbing the parameters of the MAT—length, link angle, and the node radius—one can define a shape class. Unlike the contour-to-MAT transform, which is well-known to be unstable, the MAT-to-contour process is an integrative process and is very stable. The variation in these parameters can be controlled by defining a suitable discretization over the parameter space. This leads to a broad class of similar shapes from which an optimized shape can be obtained for a given set of criteria. The optimizing criteria may involve the boundary description for each shape; the axial model is only used for generating the shape class. This Qualitative MAT model has been tested in several design optimization contexts, using Genetic Algorithms, and we show results for Automobile contours, IC engine parts, building profiles, etc.

The geometric dimensioning and tolerancing (GD&T) specifications of a design are directly associated with its performance and functional requirements. They also govern the manufacturing and quality control processes needed to achieve those requirements. This paper reviews recent work in geometric tolerance representation and reasoning and presents a generic and uniform graph-based representation scheme, called the Tolerance Network, to represent GD&T specifications across a part or assembly. The network can accommodate GD&T specifications related to the function, behavior, manufacturing, and inspection requirements embedded in design specifications and supports the use of different types of tolerances. The network also accommodates common design practices such as the specification of overconstrained features and parts. The necessary properties of such a network are discussed that allow under- and overconstrained design specifications to be detected and analyzed.

This paper proposes a new method for dealing with geometrical layout constraints. Geometrical layout constraints are classified into three classes of dimensional, regional, and interference constraints. Dimensional constraints are handled by using an existing methodology. A method is proposed to translate the other two classes of constraints into dimensional constraints. Thus, it is possible to uniformly deal with all of those geometrical layout constraints. The method is twofold. First, it converts regional, interference constraints into a set of simple inequalities. Then each inequality is solved by a geometric gadget, which is a structured set of dimensional constraints. A prototype system is developed and applied to some layout design examples.