Solving incidence and tangency constraints in 2D

Solving Incidence and Tangency Constraints in 2D N uria Mata Departament de Llenguatges i Sistemes Informatics Universitat Politecnica de Catalunya Av. Diagonal 647, 8 a , 08028 Barcelona e-mail: [email protected] c.es January 21, 1997 Abstract This pap er rep orts on solving geometric constraint satisfaction problems involving incidence and tangency constraints in 2D. A variational geometric constraint solver based on a constructive approach is used: the main goal is to keep the present set of rules as small as p ossible. Dening tangency conditions as distance and angle constraints allows solving xed radius congurations. Non-xed radius schemes are also characterized and a new set of constructive rules is prop osed. 1 1 Intro duction In Geometric Constraint Satisfaction Problems (GCSP), mo delling tasks are p erformed by giving dimensions and geometric esp ecications, or constraints , to rough sketches. Several approaches to the geometric constraint satisfaction have b een rep orted in the literature. Most constraint solvers translate constraint relations into a system of equations that are solved using iterative techniques, in numerical constraint solvers , or symb olic algebraic metho ds, in symbolic constraint solvers . Other approaches are based on constraint propagation on graphs representing systems of constraint equations. In constructive solvers , constraints are satised by placing subsets of wellconstrained geometric elements in a nite numb er of construction steps. They are based on the fact that most congurations in an engineering drawing are solvable using a rather small set of to ols like ruler, compass and protractor. Constructive solvers can b e based either on rewriting rules [2, 13] or on constraint graph analysis [1, 12, 10]. Our group has built a variational geometric constraint solver based on a constructive approach [7]. It computes a solution in two phases. First, using rewriting rules, the solver builds a sequence of construction steps without the need of arranging the set of constraints in a predened order. Then, the construction steps are carried out to generate an instance of the geometric ob ject for the current dimension values. Sketches are comp osed from geometric elements and constraints. At present, p oints and segments are the only geometric elements allowed in the solver. Constraints that can b e dened on these ob jects include distance b etween two p oints, p erp endicular distance b etween a p oint and a segment, and angle b etween two segments. The p ossible geometric elements that can b e dened using tangency constraints are circles, arcs and segments. This pap er describ es how to extend the present sets of geometries and constraints, by including arcs, circles, incidence and 2D tangency constraints, while keeping the set of rules as small as p ossible. In the next section, the constructive geometric constraint solver used in the present work is intro duced. In section 3, we will discuss ab out constraints involving arcs and circles. In section 4, incidence and tangency constraints in 2D will b e characterized: xed and variable radii congurations will b e intro duced and a new set of constructive rules will b e prop osed. Finally, in section 5, our conclusions will fo cus on the convenience of extending the present set of rules in the geometric constraint solver. 2 The Constructive Geometric Constraint Solver The geometric constraint solving system has two ma jor comp onents, the analyser and the constructor . The analyser deals with the problem of determining symb olically whether or not a geometric sketch is solvable. It is based on a constructive technique which exhibits prop erties of b oth rule and graph constructive approaches. The solver is fed with a top ologically correct sketch prop erly annotated with constraints. Then, if the set of constraints consistently denes the ob ject, the analyser generates a sequence of constructive steps that determine each geometric element such that the constraints are satised. The constructor resp onds to the problem of building an instance of the geometric ob ject. The instantiation is carried out by applying the sequence of construction steps generated by the analyser to the actual parameters values. Whenever no numerical incompatibilities arise in the computation, an instance of the geometric ob ject is generated. The solver considers only well-constrained, two-dimensional sketches. In the next sections, we discuss some issues concerning the data representation and the rules used. 2 2.1 Data representation in GCSP A GCSP can b e mo delled using a constraint graph to represent b oth, geometric comp onents and constraints dened on these elements. Each no de represents the degrees of freedom of the underlying geometry in the graph. Edges constraint the p ossible movements of these geometries: the more edges in a graph, the more likely to b e rigid. A constraint graph is a simple, undirected and nite graph consisting of no des representing geometries and pairwise edges corresp onding to the equations b etween each two constraint geometries [12]. In GCSP, the primary interest is not in graphs, but rather in their concrete realizations in some Euclidean space. The graph realization problem is that of computing the relative lo cations of a set of vertices placed in Euclidean space, relying only up on some set of inter-vertex constraints. By Laman's theorem [11], the relative p ositions of n given p oints are totally determined by 2 n ? 3 indep endent relations dened b etween them. In 2D Euclidean space, indep endent relations mean, using a graph approach, that a graph G with n geometric elements and 2 n ? 3 constraints is rigid if and only if no subgraph G 0 has more than 2 n 0 ? 3 edges, n 0  n . 2.2 Rules Rules are applied on subsets of p oints and constraints. These subsets are known as constraint sets , CX sets in short, and they are classied in CA, CD and CH sets. An angle constraint set, CA set, is a pair of oriented segments which are mutually constrained by an angle. A distance constraint set, CD set, is a set of p oints with mutually constrained distances. A CH set is a p oint and a segment constrained by a p erp endicular distance from the p oint to the segment. A sketch is solved when all the p oints b elong to the same CD set. Dep ending on the functionality of the rules, the following typ es are considered: creation rules, merging rules or construction rules.  Creation rules Creation rules generate elementary CD , CA and CH sets as an interpretation of the dimensioning scheme dened by the user.  Merging rules Merging rules allow to compute op erations b etween constrained sets.  Construction rules Mo dels are built incrementally using lo cally solvable geometric constructions. CD , CA and CH sets are combined into larger CD sets if they pairwise share a single geometric element. Merging CX sets require rigid b o dy motions. All these rules are explained with detail in [8]. 3 Constraints involving arcs and circles 2D tangency constraints are dened on arcs, circles and segments. Considering that arcs are partial visualizations of circles b etween the two arc endp oints, only the two following basic congurations need to b e dened:  2D tangency constraints b etween a segment and a circle  2D tangency constraints b etween two circles Besides tangency constraints, incidence on circles and constraints on the radius may also exist. GCSP are solved when all p oints are p ositioned in a CD set. By Laman's theorem, 2 n ? 3 well-distributed constraints are enough to determine the relative p osition of n 3 AB AB D d1 d2 d3 r r r r C E DE (b) constraint graph(a) sketck D d2 C B Ed3 d1 Q A r t, on t, on Figure 1: Solver representation of 2D tangency constraints in a xed radii conguration. given p oints. Using a kinematical analysis approach, the total numb er of allowed motions is the numb er of degrees of freedom, 2 n (in two-dimensional space, a p oint has 2 traslational degrees of freedom), minus the rigid b o dy motions (two traslational and one rotational rigid b o dy motion on the plane). When circles are included in the geometries set, a dimensionality problem arises. A p oint on a circle, ( x ? c x ) 2 + ( y ? c y ) 2 = r 2 , has 3 degrees of freedom: two degrees of freedom to p osition the center, C = ( c x ; c y ), and one more for the radius, r . Therefore, some care must b e taken when determining the numb er of constraints that consistently dene GCSP's when arcs and circles are involved. More general than Laman's theorem, although not sucient, is Gr ubler's condition [3]. The relative p osition of n given geometric elements in the two-dimensional Euclidean space is determined by P n i =1 d i ? 3 well-distributed constraints, d i the numb er of degrees of freedom of geometry i . 4 Characterization of incidence and tangency constraints in 2D In this section, incidence and tangency constraints will b e characterized in terms of constraint sets, CD CA and CH sets, considering b oth, xed radii (section 4.1) and variable radii congurations (section 4.2). 4.1 Fixed radii congurations In xed radii congurations, p oints on a circle are determined once the p osition of the center p oint is known. The two remaining traslational degrees of freedom of the circle need to b e constrained to consistently dene a sketch. With an appropiate representation and some prepro cessing, we may restrict ourselves to p oints and segments, with pairwise distance and angle constraints. The circle placement problem is reduced to p ositioning the center p oint. Constraints on circles, 4 C1 2 2 1 C r r (a) d ( C , C ) = r + r 1 2 1 2 C1C2 r1 r2 d ( C , C ) = r - r (b) 1 2 2 1 tt Figure 2: Solver representation of 2D tangency b etween to circles with known radius dimensions. incidence and tangency constraints, are transformed into an equivalent representation in which only distance constraints app ear. Let Q ( C ; r ) b e the circle centered in C and given radius r . Three new creation rules are dened: 1. point P on circle Q ( C ; r ) This constraint is translated into a distance constraint b etween the p oint P and the center C of circle Q ( C ; r ), d ( P ; C ) = r . As shown in gure 1, A and E are p oints on 1 the circle Q and, therefore, incidence is translated into the following distance constraints: d ( C ; A ) = r and d ( C ; B ) = r . 2. segment s tangent to circle Q ( C ; r ) A tangency constraint b etween a segment s and a circle Q is expressed by a p erp endicular distance constraint set b etween the center of the circle and the tangent segment. In the example shown in gure 1, Q is tangent 2 to segments AB and D E . Tangency constraints are translated into d ( C ; AB ) = r and d ( C ; D E ) = r . Since the distance from a p oint to a segment is the usual minimal distance, this constraint implicitly represent the usual information derived from tangency constraints b etween a segment and a circle: the radius and the segment are constrained by a right-angle through the tangency p oint. 3. circle Q 1 ( C 1 ; r 1 ) tangent to circle Q 2 ( C 2 ; r 2 ) A tangency constraint b etween two circles, Q 1 and Q 2 , is expressed by a distance constraint b etween the two center p oints, C 1 and C 2 , equal to j r 1  r 2 j . The two p ossible solutions are illustrated in gure 2. 4.2 Variable radii congurations Circles can also b e used even if values for the radii are not explicitly given. In this case, the solver not only has to determine the p osition of the center p oint, but also the value of the radius which satises the set of constraints on the circle. Circles with variable radius have three degrees of freedom. Therefore, at least three constraints on the circle need to b e dened in order to cancel the two traslational degrees of freedom and a radial allowed motion. Constraints on the circle may b e referred either to the center p oint or to the circumference (incidence or 2D tangency constraints). Dep ending on whether the center p oint 1 Incidence is represented by an on annotation in the sketch. 2 In the sketch, tangency constraints are denoted by t . 5 A C d1 d2 B 1 a on Figure 3: The radius of the circle is calculated as the distance b etween the center p oint, C , and p oint A on the circle. can or cannot b e p ositioned b efore the radius is determined, two diferent problems must b e considered. If the center p oint can b e p ositioned in a well-constrained subset of geometric elements, the additional constraint on the circle may allow to dimension the radius. Otherwise, the three constraints on the circle need to b e simultaneously considered. In section 4.2.1, the radius of the circle will b e determined once the center p oint p osition is known. In section 4.2.2, b oth the center and the radius will b e calculated from the set of constraints on the circle. Finally, in section 4.2.3, a new approach to solve variable radii congurations will b e presented. 4.2.1 Computing the radius of the circle once the center p oint p osition is known If the p osition of the center p oint can b e determined indep endently from the radius of the circle, the radius dimension can b e calculated using an incidence or a tangency constraint. This additional constraint on the circle will provide the value for the radius using one of the following rules: 1. point P on circle Q ( C ; r ) If a p oint P is on a circle Q , and P and C b elong to the same CD set, then the value for the radius r can b e calculated by r = d ( C ; P ) . In gure 3, p oints A , B and C are relatively p ositioned using two distance constraints ( d 1 and d 2 ) and one angle constraint ( a 1 ). The radius of the circle is determined by the distance b etween A and the center p oint, C , b oth b elonging to the same CD set. 2. segment s tangent to circle Q ( C ; r ) If a segment s and a circle Q ( C ; r ), s and C b elonging to the same CD set, are related by a tangency constraint, then the value for the radius can b e calculated as the p erp endicular distance b etween the segment and the centre of the circle: r = d ( C ; s ) In the example shown in gure 4, p oints A , B and C can b e relatively p ositioned in a CD set. Then, the radius can b e calculated as the distance b etween segment AB and the center p oint C . Once the radius is known, p oint D can b e p ositioned in the sketch using the two remaining constraints: p oint D on Q and segment B D tangent to circle Q . 6 A B C D Q d d 1 2 d3 tt, on Figure 4: In this sketch, the value for the radii is calculated using a tangency constraint. C1 2 2 C r C r C2 2 1 r = d (C , C ) - r 1 1 2 2 t t Figure 5: Computing the radius dimension r 1 from a tangency constraint b etween two circles. 3. circle Q 1 tangent to circle Q 2 Given two circles Q 1 ( C 1 ; r 1 ) and Q 2 ( C 2 ; r 2 ) such that their center p oints, C 1 and C 2 , b elong to the same CD set, they will b e well-constrained if and only if one of them has a radius dimension. If b oth circles have variable radii, the sketch is under-constrained. Considering r 1 to b e the unknown radius, it can b e calculated as follows: r 1 = j d ( C 1 ; C 2 )  r 2 j as illustrated in gure 5. In our current approach, these three rules cannot b e conceptually classied in any of the categories describ ed in section 2.2. Computations on the radii are carried out and the dimension values obtained are later used as explicit constraints. In variable radii congurations, the relations derived from incidence and tangency constraints are symb olic, therefore, the valuation of the radii has to b e p erformed b efore using creation rules to generate the elementary constraint sets involving the radius dimension. Since 7 computing the value for the radii do es not entail adding any geometric element to an existent CD set, this op eration cannot b e considered a construction rule, either. In fact, these three rules op erate on elements b elonging to the same CD set and not b etween constraint sets as it would b e p erformed by merging rules. At this stage, two dierent solutions have b een considered: creating a new typ e of rules or using a geometric constraint solver based on a hybrid approach. A new class of rules to deal with symb olic constraints -considering their functionality, we have named them propagation rules - can b e dened. Some tangency and incidence constraints intro duce symb olic dimensions that may b e determined by computing geometric relations from a partially completed construction. A solver based on a hybrid approach is a combination of several metho ds mentioned in section 1. A hybrid geometric constraint solver supp orting symb olic constraints is describ ed in [6]. This work rep orts on a technique to enhance constructive geometric constraint solvers with the capability of managing functional relationships b etween dimension variables. Essentially, it is a purely geometric constraint solver communicated bi-directionally with an equational solver. In the next section, congurations using circles with variable center and radii will b e analysed. Using the results obtained in sections 4.2.1 and 4.2.2, we will adopt the most suitable approach for variable radii congurations in section 4.2.3. 4.2.2 Computing the radius and the center p oint In the previous sections, constraints on circles were transformed into an equivalent representation in which only distance b etween two p oints and p erp endicular distance b etween a p oint and a segment app eared. In xed radii congurations and in variable radii circles with known center p osition, the p oints of the circle have up to two degrees of freedom. Therefore, solving constraints on circles -expressed in terms of p oints, segments and distance constraintscan b e done using the present set of rules dened on sets of p oints, distance, p erp endicular distance and angle constraints. In well-constrained sketches, when the radius dimension and the center p oint are unknown, all constraints on the circle must b e expressed as a function of the radii. Incidence and tangency constraints must b e translated into symb olic constraints using the relationships given in section 4.2.1:  point P on circle Q ( C ; r ) d ( C ; P ) = r  segment s tangent to circle Q ( C ; r ) d ( C ; s ) = r  circle Q 1 ( C 1 ; r 1 ) tangent to circle Q 2 ( C 2 ; r 2 ) d ( C 1 ; C 2 ) = j r 1  r 2 j A combination of these three basic constraints gives ten dierent ways of dening circles using incidence and tangency constraints. The resulting congurations are summarized in table 1 and a more detailed information is provided b elow, as well as examples on each conguration. 1. Circle dened by three incident p oints Set of constraints: p oint P 1 on circle Q ( C ; r ) ! d ( C ; P 1 ) = r p oint P 2 on circle Q ( C ; r ) ! d ( C ; P 2 ) = r p oint P 3 on circle Q ( C ; r ) ! d ( C ; P 3 ) = r 8 Table 1: Dierent ways to dene a circle using incidence and tangency constraints. Case points segments circles Conguration 1 P 1 ; P 2 ; P 3 P P P 1 2 3Q (C, r ) 2 P 1 ; P 2 s 1 P P 1 2 t 1 s Q (C, r ) 3 P 1 ; P 2 Q 1 P11 r C1 t P2Q (C, r ) Q (C ,r ) 1 1 1 4 P 1 s 1 ; s 2 t 1 ss2 t 1 PQ (C, r ) 5 P 1 s 1 Q 1 P11 r C1 t t s1 Q (C, r ) Q (C , r ) 1 1 1 6 P 1 Q 1 ; Q 2 1 r C1 t P1 t r2 Q (C, r ) Q (C ,r ) Q (C ,r ) 222 111 7 s 1 ; s 2 Q 1 1 r C1 s s2 1t t t Q (C ,r ) 11 Q (C, r ) 1 8 s 1 ; s 2 ; s 3 s2 t t t s1 s3 Q (C, r ) 9 s 1 Q 1 ; Q 2 1 r C1 t s1t t C2r2Q(C,r ) Q (C ,r ) Q (C ,r ) 2 2 1 1 1 2 10 Q 1 ; Q 2 ; Q 3 C C1C2 C3 rr r 12 3 t t t Q (C, r ) Q Q Q 2 3 1 9 C1 r1 P3a a 2 3 P2P1 P5 P4 d d 1 2 Q a1 1 r r PP P PP CC ss s s d d a a a r rr r 1 1 1 1 1 2 2 2 1 3 1 1 3 45 12 23 34 45 r + r1 C s23 34 s t t t Q (C, r ) Figure 12: Circle tangent to segment s 23 , segment s 34 and circle Q 1 . s P s 3 2 3 P12 Ps1d1 a1a2 P C r r r a a2 s s s 2 3 3 1 d1 P1P2 C tt tQ (C, r ) Figure 13: Circle tangent to three segments: s 1 , s 2 and s 3 . 16 P P PP1 2 3 4 d d 1 2 aa 1 rr 12 C C 1 2 P P P P s s 12 3 4 13 C1 a d d 1 2 3 r1 24 s s12 r1 Cr2 r2 C 34 r + r r r + r12 1 a a2 2 a3 2 34 s t t tQ (C, r ) Q Q1 2 Figure 14: Circle tangent to segment s 3 4 and tangent to circles Q 1 and Q 2 . The sketch shown in gure 14 is an example of how the value for the radius can b e calculated and the center p oint p ositioned, while satisfying the set of dimensional and 2D tangency constraints dened on circle Q . Once P 1 , P 2 , P 3 , P 4 , C 1 and C 2 have relatively b een placed, the construction that needs to b e solved is: a  C x + b  C y + c = r ( C 1 x ? C x ) 2 + ( C 1 y ? C y ) 2 = ( r  r 1 ) 2 ( C 2 x ? C x ) 2 + ( C 2 y ? C y ) 2 = ( r  r 2 ) 2 In this sketch, four p ossible solutions verify the whole set of constraints, but only one of them would capture the user intent. The problem to cho ose the desired solution among all p ossible constructions is a complex task in GCSP [5]. 10. Circle dened by three tangency constraints b etween circles Set of constraints: circle Q 1 ( C 1 ; r 1 ) tangent to circle Q ( C ; r ) ! d ( C ; C 1 ) = j r  r 1 j circle Q 2 ( C 2 ; r 2 ) tangent to circle Q ( C ; r ) ! d ( C ; C 2 ) = j r  r 2 j circle Q 3 ( C 3 ; r 3 ) tangent to circle Q ( C ; r ) ! d ( C ; C 3 ) = j r  r 3 j 17 d C d d r r C1 3 1 1 2 3 3 2 r 2 CC CC C 1 2 3 d dd 1 23 r - r r - r r - r 1 2 3 t t t Q (C, r ) Q2 Q3 Q1 Figure 15: Circle tangent to three circles: Q 1 , Q 2 and Q 3 . A circle tangent to three given circles is known as the Problem of Ap ollonius. In fact, this is the general problem which includes the 9 congurations describ ed ab ove. A p oint is a circle with null dimension radius. A segment is a circle with a value for the radius equal to innite. There are, in general, eight p ossible solutions dep ending on the relative p osition of C with resp ect to the already placed center p oints C 1 , C 2 and C 3 , [9]. These solutions are obtained from the following system of equations: ( C 1 x ? C x ) 2 + ( C 1 y ? C y ) 2 = ( r  r 1 ) 2 ( C 2 x ? C x ) 2 + ( C 2 y ? C y ) 2 = ( r  r 2 ) 2 ( C 3 x ? C x ) 2 + ( C 3 y ? C y ) 2 = ( r  r 3 ) 2 In gure 15, the three given circles are contained within the solution circle. In a rule-based approach, a sp ecic rule has to b e dened for each of the 10 basic congurations given ab ove. In section 4.2.1, using the information given by the p osition of the center p oint, three more rules needed to b e dened. As a whole, 13 propagation rules need to b e considered to solve any conguration involving arcs and circles with variable radii. On the other hand, any circle dened by three symb olic constraints can b e translated into a system of three quadratic equations, with the co ordinates of the center p oint and the value of the radius as the unknowns. The hybrid solver in [6], can switch to numeric metho ds to compute the p osition of the center p oint and the radius dimension. Then it switches back to the constructive metho d to solve the remaining constraints. 4.2.3 Solving variable radii congurations using propagation rules or a hybrid approach Adding propagation rules to the solver or using the geometric constraint solver based on a hybrid approach need to b e evaluated taking into account the following considerations:  the numb er of propagation rules that must b e dened  the scop e of the solver  the correctness of the analyzer using symb olic constraints 18 Thirteen propagation rules need to b e dened to solve any variable radii circle conguration. Since the solver already has 18 construction rules, that means to nearly double the numb er of rules in the geometric constraint solver. The hybrid solver describ ed in [6] considers 2D geometric constraint problems involving constraints with xed value as well as constraints with symb olic value. The technique used deals with two sets of data: the geometric constraint data, represented by a set of clusters, and the symb olic equation data, describ ed by a bigraph. The constructor builds an instance of the solution by executing a sequence of construction steps generated by the analyser. Since all values needed must b e available when a construction step is carried out, the analyser classies each symb olic constraint according to the way by which its value will b e computed. A symb olic constraint is computable when its value is to b e found by solving a subset of constraint equations. A symb olic constraint is propagatable when its value can b e derived from geometric elements already placed with resp ect to each other. When a constraint can b e b oth computable and propagatable, it is considered to b e propagatable by the analyser. The relations derived from incidence and 2D tangency constraints in variable radii circles b ecome propagatable or computable dep ending on whether the center p oint p osition is known or not. As it has b een intro duced in section 4.2.1, when the center p oint p osition is known, all geometric elements involved in the valuation of the radius b elong to the same CD set. In this conguration, the dimension of the radius is a propagatable constraint. Otherwise, the radius is a computable constraint b ecause its dimension has to b e valuated along with the co ordinates of the center p oint (see congurations dened in section 4.2.2). Propagation rules, of course, enlarge the scop e of the solver, but further extensions would require including even more rules. On the contrary, using a suitable translation of new geometries and constraints, these may b e included to the hybrid solver without much eort. Besides, the hybrid solver supp orts other kind of relations such as engineering constraints. The correctness of the analyser for the currently available set of rules has b een established in [7]. Adding propagation rules to the constructive solver would imply proving termination again. The correctness of the analyser in the hybrid solver has b een shown in [6]. All these considerations lead us to cho ose the geometric constraint solver based on a hybrid approach to solve variable radii congurations involving arcs or circles on the plane. 5 Conclusions This work has rep orted on the use of circles in geometric constraint satisfaction problems. Incidence and 2D tangency constraints on circles either with xed or variable radii have b een studied. Considering circles in 2D geometric constraint solving entails three new geometric constraints: p oint incident to a circle, straigth segment tangent to a circle, and tangency b etween two circles. We have shown that geometric ob jects including circles with xed radius can b e solved without extending the set of construction rules available in our rule-based solver. This has b een achieved by including three new creation rules which translate the new geometric constraints into the already existing p oint to p oint distance constraint and p oint to segment distance constraint. Some constraint driven variational CAD systems cannot solve mo dels where circles have variable radius. We have characterized variable radii congurations and two diferent approaches have b een presented: adding a new set of rules to the solver, propagations rules , or using a hybrid solver. The hybrid solver extends the capabilities of the constructive solver to constraints on variable radii circles without increasing the 19 present set of construction rules. The correctness of the analyser has b een established in previous works. Acknowledgements I wish to thank Prof. Rob ert Joan-Arinyo and Antoni Soto for their advice and fruitful collab oration on the development of this work. This research has b een supp orted by the Comision Interministerial de Ciencia y Tecnologa (CICYT), under the pro ject \Dise ~no mediante restricciones geometricas" (TIC95-0630-C05-04). References [1] W. Bouma, I. Fudos, C. Homann, J. Cai, and R. Paige. Geometric constraint solver. Computer Aided Design , 27(6):487{501, June 1995. [2] B.D. Br uderlin. Using geometric rewrite rules for solving geometric problems symb olically. In Theoretical Computer Science 116 , pages 291{303. Elsevier Science Publishers B.V., 1993. [3] E.A. Dijksman. Motion Geometry of Mechanisms . Cambridge University Press, 1976. [4] B. Hendrickson. Conditions for unique graph realizations. SIAM J.Comput. , 21(1):65{84, 1992. [5] C.H. Homann and R. Joan-Arinyo. Geometric Modeling for Product Realization , chapter Erep - An Editable, High-Level Representation for Geometric Design and Analysis. Elsevier Science Publishers B.V. (North-Holland), 1993. [6] C.M. Homann and R. Joan-Arinyo. Symb olic constraints in constructive geometric constraint solving. Journal of Symbolic Computation , 1997. To app ear. [7] R. Joan-Arinyo and A. Soto. A rule-constructive geometric constraint solver. Technical Rep ort LSI-95-25-R, Department LiSI, Universitat Politecnica de Catalunya, 1995. [8] R. Joan-Arinyo and A. Soto. A set of rules for a constructive geometric constraint solver. Technical Rep ort LSI-95-19-R, Department LiSI, Universitat Politecnica de Catalunya, 1995. [9] R. Ra jagopalan Kavasseri. Variable radius circle computations in geometric constraint solving. Master's thesis, Purdue University, August 1996. [10] G.A. Kramer. A geometric constraint engine. Articial Intel ligence , 58(1-3):327{ 360, 1992. [11] G. Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics , 4(4):331{340, Octob er 1970. [12] J.C. Owen. Algebraic solution for geometry from dimensional constraints. ACM , pages 397{407, 1991. [13] A. Verroust, F. Schonek, and D. Roller. Rule-oriented metho d for parameterized computer-aided design. Computer Aided Design , 24(10):531{540, Octob er 1992. 20