Revisiting variable radius circles in constructive geometric constraint solving

Revisiting Variable Radius Circles in Constructive Geometric Constraint Solving Ching-Shoei Chiang Department of Computer and Information Science Soochow University Taiwan, R.O.C. Robert Joan-Arinyo Departament de Llenguatges i Sistemes Inform`atics Universitat Polit`ecnica de Catalunya Barcelona, Catalonia, Spain [email protected], [email protected] March 13, 2002 Abstract Variable-radius circles are common constructs in planar constraint solving and are usually not handled fully by algebraic constraint solvers. We give a complete treatment of variable-radius circles when such a circle must be determined simultaneously with placing two groups of geometric entities. The problem arises for instance in solvers using triangle decomposition to reduce the complexity of the constraint problem. This work offers a set of basic constructive methods that permits to determine variable radius circles simultaneously with placing two rigid geometric objects when geometric constraints are defined on both the circumference and center point of the constraint circle. The problem has been classified by the geometric entities in two groups, one is fixed and the other has translational and rotational movement, so that the variable radius circles satisfy the constraints on the geometric entities in these two groups. The number of solutions for each problem is also given. Keywords: Geometric constraint solving, variable radius circles, constructive solvers, algebraic solvers, cyclographic maps. 1 1 Introduction In constraint-based geometric design, the designer creates a rough sketch of an object made out of simple geometric elements. Then the intended exact shape is specified by annotating the sketch with constraints. A geometric constraint solver then checks whether the set of geometric constraints coherently defines the object and, if so, determines the position of the geometric elements. Many techniques have been reported in the literature that provide powerful and efficient methods for solving systems of geometric constraints. For example, see [2] and references therein for an extensive analysis of work on constraint solving. Among them, our interest focuses on constructive techniques, Constructive solvers have two major components: the analyzer and the constructor. The analyzer symbolically determines whether a geometric problem defined by constraints is solvable. If the problem is solvable, the output of the analyzer is a sequence of construction steps, known as the construction plan, that places each geometric element in such a way that constraints are satisfied. After assigning specific values to the parameters, the constructor interprets the construction plan and builds an object instance, provided that no numerical incompatibilities arise. The complexity of geometric constraint solving is doubly exponential, a fcat that derives from the ability to express polynomial algebraic equations by geometric constraint configurations. As a result, it is accepted that practical solvers are not complete, that is, they solve a subclass of geometric problems. A practical useful class of problems are twodimensional constraint problems where the geometric elements are points, straight lines, and circles with fixed radii, and in which the constraints are like distance between two points, distance from a point to a line, angle between two lines, line-circle tangency and so on. Various extensions to the geometric repertoire that constructive solvers can handle in two dimensions can be considered. Exemples are circles with variable radius, conics and B´ezier curves. Of them, variable radius circles are common constructs in two dimensional constraint solving and are usually not handled fully by constructive solvers. Probably they are the most useful extension as they permit auxiliary construction in addition, as explained 2 by Hoffmann and Vermeer, [9], Hoffmann and Joan-Arinyo, [8], and JoanArinyo and Soto, [10]. When the underlying solver is numerical and good initial guesses are available for the geometric elements, variable radius circles pose no particular problem. But the numerical approach to solving constraints has many drawbacks, including reliance on good starting values and the inability to explore solution variants, [2]. What is needed is a constructive solution, preferable one in which there is no need to solve high-degree polynomials. Recently, Hoffmann and Chiang, [6, 7], reported on an extension of the basic constructs to deal with variable radius circles in constructive solvers. Here, the constraints on the variable radius circle are placed only on the circumference. In this work we further extend the basic constructions to consider constraint problems in which variable radius circles occur with constraints defined on their center points. The rest of the paper is organized as follows. In Section 2 we give a short overview on related work. Next in Section 3 we define a minimal set of tools a user interface should provide to define variable radius circles. Section 4 recalls the fundamental concepts of the cyclographic model geometry we will make use of. General algorithms for the constructions which solve the problem considered here are given in Section 5. In Section 6 we present solving estrategies to keep to a minimum the complexity of the algorithms implementation. Finally we offer some conclusions in Section 7. 2 Prior Work There is a paucity of published works reporting on variable radius circles in constructive geometric constraint solving. Ramanathan, [14], studied the Apollonious problem which consists in constructing a circle tangent to three given circles. The work addressed two problems: Devising a coordinate-independent enumeration method of the eight possible solutions and performing the computations efficiently. The technique was applied to constraint-based, variable radius fitting of fillets to two lines. Joan-Arinyo and Soto described in [10] a hybrid technique that allows to solve constraint problems involving geometric elements with more than two degrees of freedom. In particular it is shown how the method solves variable 3 r Co e1 e2 e3 C(Co, r)Rigid cluster Figure 1: Variable radius circle C(C0,r) attached to one cluster. radius circles attached to one geometric object which is determined up to position and orientation, from now on referred to as a cluster [3], through three constraints. See Figure 1. Hoffmann and Chiang recently, [6, 7], reported on a more general approach to constructively solving constraint problems involving variable radius circles. The approach uses cyclographic maps, a special case of Laguerre geometry, [5], and handles the situation where the variable radius circle, C(C0,r), (see Figure 2) is attached to two clusters, S1and S2,whichshare a common geometric element, E. The total number of degrees of freedom that need to be canceled for S1,S2and the variable radius circle to define a cluster is four: three for the circle itself plus one due to the possible relative motion between S1and S2along E. These constraints are canceled by attaching the variable radius circle to each cluster through two constraints. Note that, otherwise the problem could be reduced to the previous case. A limitation of the method is that it only considers constraints placed on the circumference of the variable radius circle. The DCM is a commercial solver, [1], which permits sequential constructions of variable radius circles when they are attached to one given cluster through three constraints. As far as we know, [11, 12], no details have been disclosed about how the variable radius circles are handled. 3 Definition of Variable Radius Circles To define geometric problems involving circles with variable radius, the user interface should provide an appropiate set of tools. A minimal set of tools 4 r Co e e11 e12 e1m e21 e22 S1 C(Co, r) S2 e2n Figure 2: Variable radius circle C(C0,r) attached to two clusters. would include an explicit command to trigger the variable radius circle definition along with operations to place geometric constraints on its circumference and on its center. We assume that the geometric elements from which constraint problems are built are points, straight lines and circles. A sufficient set of constraints to define variable radius circles includes tangencies and distances. 3.1 Constraints Placed on the Circumference We define the tangency constraints placed on the circumference as follows. See Figure 3. The circumference of the variable radius circle can be tangent to P Qo r C Co d d dt ton LQ Figure 3: Constraints placed on the circumference of a variable radius circle. 5 •The circumference of a fixed radius circle. •A straight line. •A point. This is the usual on constraint. Distance constraints placed on the circumference of the variable radius circle, see Figure 3, are defined as follows •Distance to a fixed radius circle Q: The minimum distance between the two circles measured along the straight line defined by their center points. •Distance to a straight line L: The minimum distance between the circle and the line measured along the perpendicular to the given line through the circle center point. •Distance to a point P: Distance between the circle and the point measured along the straight line defined by the point and the center of the circle. 3.2 Constraints Placed on the Center Point Center points of variable radius circles have no privileges over other points. Therefore the set of constraints that apply to generic points apply also to center points of circles with variable radius. We assume that the constraints available at the user interface are, see Figure 4, •The center point can be at a given distance from another geometric element. •The center point can be on (tangent to) another geometric element. To facilitate the user interaction, other constraints could be added to the repertoire so far presented. 4 The Cyclographic Model Several geometric design problems can be solved in a surprisingly simple way if one uses Laguerre geometry. A specific case of this geometry, known 6 P Qo r C Co don on LQ on dd Figure 4: Constraints placed on the center of a variable radius circle. as the cyclographic model, results particularly useful to solve the problem we have at hand, [14]. For the sake of completness, we recall the fundamental concepts of the cyclographic model for the embedding of space R2in R3we will make use of. For a general and more in depth discusion on the cyclographic model and its applications to computer aided geometric design see Hoffmnann [5], and Pottmann and Peternell [13]. The fundamental elements in R2we consider are rays and cycles.Aray is an oriented straight line. A cycle is an oriented circle or a point (cycle with radius 0). The orientation is fixed by a unit normal vector field in the case of rays and by a signed radius in the case of the cycle. The basic relation is that of oriented contact between cycles and rays. Refer to Figure 5. An oriented cycle and a ray are in oriented contact, if they are tangent and the unit normals coincide at the point of contact. For a point and a ray, oriented contact equals incidence. L C ab L C Figure 5: Contact ray-cycle. a) Oriented. b) No oriented. 7 γ C a r r π/4 C (a, b) b π/4 π/4 P γ P Figure 6: Cyclographic maps. a) Cycle. b) Point. Let C(a, b, r) denote a cycle with center point (a, b) and signed radius r. We assume that when r>0, the cycle is oriented counterclockwise; if r<0, the cycle is oriented clockwise. When r= 0, the cycle represents a point and is considered to have both orientations simultaneously. With each cycle C(a, b, r) there is an associated cyclographic map,denoted by γC, defined as the cone whose apex is the point (a, b, r)inR3, whose axis is parallel to the Zaxis and whose angle is equal to π/4. Figure 6 illustrates this concept. Consider the line in R2whose equation is ax +by +c=0. Notethat, depending on the orientation, a straight line can support two different rays. The orientation of a ray, given by its direction vector, is defined as the vector [b, −a]; that is, the result of rotating clockwise by 90◦the vector [a, b], which is normal to the line. We shall denote a ray by L(a, b, c)orjustL. With each ray L(a, b, c) there is an associated cyclographic map, denoted by γL, defined as the plane in R3which intersects the XY plane at Land at an angle with [b, −a]equaltoπ/4. See Figure 7. n LL π/4 γ L Figure 7: Cyclographic map of a ray. 8 The distance of a point to a ray is measured as a positive quantity if the point is to the left of the ray as seen in the ray’s orientation. The angle between a pair of rays, ∠(Li,L j) is measured from the direction of Li clockwise to the direction of Lj. 5 Solving Variable Radius Circles The set of constraints given in Section 3 refer to the tools available at the user interface to provide a friendly interaction. To facilitate the solving proces, we first show how to transform the problem defined at the user interface into an equivalent problem, where distance constraints on the variable radius circle are expressed as tangencies. Next, to handle the constraints defined on the center point of variable radius circles in a uniform and consistent way, we extend the cyclographic model with two new auxiliary maps. Then we give general algorithms that compute variable radius circles that are attached to two rigid clusters through constraints placed on both, the circumference and the center point of the circle. Following [6, 7], we consider two different scenarios: 1) The geometric element Eshared by clusters S1 and S2, see Figure 2, is a straight line and relative motion is translational, and 2) Eis a circle or point and the relative motion of clusters is a rotation. 5.1 Problem Transformation First we consider the distance constraints placed on the circumference of the variable radius circle to be determined, C(C0,r). The circle-line distance constraint, dis(C, L)=d, see Figure 8, is equivalent to a tangency constraint between the circle Cand a line Lwhich has been translated a distance d along its normal. Let Q(Q0,r) be a circle with center Q0andfixedradius r. the distance constraint dis(C, Q(Q0,r)) = dis transformed into the tangency constraint t(C, Q(Q0,r+d)). Finally, the distance constraint between Cand point P,dis(C, P)=d, is transformed into the equivalent tangency constraint t(C, Q(P,d)). Distance constraints placed on the center point C0of C(C0,r)aretransformed into tangency (on) constraints as follows. The center point-point distance, dis(C0,P)=dis transformed into t(C0,Q(P,d)). The center point-line constraint dis(C0,L)=dis transformed into t(C0,L ), where L 9 Problem 2constraints 1constraint E1: E(LL,LL)(1,4) E11: E(LL,L’L’)(1,2) E13: E(LL,LL’)(1,2) E12: E(LL’,LL’)(1,2) E2: E(CL,LL)(2,8) E21: E(CL,L’L’)(2,4) E25: E(CL,LL’)(2,4) E22: E(CL’,LL’)(2,4) E26: E(CL’,LL)(2,4) E23: E(C’L,LL’)(2,4) E27: E(C’L,LL)(2,4) E24: E(C’L’,LL)(2,4) E3: E(CL,CL)(4,16) E31: E(CL,C’L’)(4,8) E35: E(CL,CL’)(4,4) E32: E(CL’,CL’)(4,4) E36: E(CL,C’L)(4,16) E33: E(C’L,CL’)(4,16) E34: E(C’L,C’L)(4,4) E4: E(CC,LL)(4,16) E41: E(CC,L’L’)(2,4) E44: E(CC,LL’)(2,4) E42: E(CC’,LL’)(4,16) E45: E(CC’,LL)(4,16) E43: E(C’C’,LL)(2,4) E5: E(CC,CL)(8,32) E51: E(CC,C’L’)(4,8) E55: E(CC,CL’)(4,4) E52: E(CC’,CL’)(8,16) E56: E(CC,C’L)(4,16) E53: E(CC’,C’L)(8,16) E57: E(CC’,CL)(8,16) E54: E(C’C’,CL)(4,8) E6: E(CC,CC)(16,64) E61: E(CC,C’C’)(4,8) E63: E(CC,CC’)(8,16) E62: E(CC’,CC’)(16,64) Table 1: General merge problem classification. we will denote by Land Cthe geometric elements in a merge problem on which center constraints have been defined. For example C(LL,CL) will denote that one line in the fixed cluster and the circle in the moving cluster support center constraints with respect to the variable radius circle. A general classification for the translational and rotational merge problem is shown in Table 1. The first column indicates the problems with circumference constraints only, the second and third columns show the different problems with two and one center constraints respectively. The pair (m, n) after each problem indicates the maximum number of solutions, m for translational and nfor rotational problems. We will explain later on how these figures have been derived. 16 6.2 Degree of the Equations To simplify the problem, we assume that in the translational case the straight line shared by the clusters is coincident with the X-axis and that in the rotational problem the cycle shared by the clusters is centered at the origin. Using the notation alreay introduce in Section 5 and with simple geometry, we have the following theorem Theorem 6.1 The equations for γL,τL,γL(d), and τL(d) are degree one. The equations for γC,τC,γC(d), τC(d), γL(θ), and τL(θ) are degree two. And, the equations for γC(θ)andτC(θ) are degree 4 equations. Notice that the equations for γL,τL,γC and τC have 3 variables x, y, z, and the equations for γL(d), τL(d), γC(d), τC(d), γL(θ), τL(θ), γC(θ)and τC(θ) add one more variable, d. As mentioned in Section 5, the variable radius circle can be found by intersecting four surfaces, each surface being a γ-map or a τ-map, depending on whether the constraint on the variable radius cycle is a circumference constraint or a center constraint. The system of equations can be easily generated by generating the equations of the maps associated to each geometric element involved. For example, the solution to the problem L(CL,CL)can be figured out by finding the intersection γC1∩τL 2∩τC 3(d)∩γL4(d) Since equations τL 2,andγL4(d) are degree one and γC1and τC 3(d)are degree two equations, from Bezout’s theorem, [4], we know there are 4 solutions for this system. By using Bezout’s theorem, every subproblem Eij of problem Ei, see Table 1, has the same number of solutions. For example, every subproblem of L1, including L11,L12 and L13, has only one solution, and every subproblem of C1, including C11,C12 and C13, has four solutions. The number of solutions for each problem is summarized in Table 1. In the following section, we will derive strategies for each merge problem subclass to reduce these numbers to compute a variable radius circle. Notice that the number of solutions given is based on our approach by using the γcyclographic maps and τmaps. If we do not use these maps, the number of solutions must be multiplied by 8, the number of essentially distinct orientations of lines and cycles. For example, the number of solutions to the problems L(LL, LL)andC(LL, LL) would be 8 and 32, respectively. 17 6.3 Algorithms for the Translational Merge Problem The subproblems given in Table 1 are individualized as translational merge problems by replacing Eij with Tij. To derive strategies to reduce the degree of the equations to be solved, we group the translational merge problems intol three different classes as follows: 1. Problems with two center constraints defined in the same cluster. This includes T11, T21, T24, T31, T41, T43, T51, T54 and T61. 2. Problems that can be transformed into the intersection of three planes and one surface. This includes T12, T13, T22, T23, T25, T26, T27, T32, T34, T35, T44, T55, and part of the problems in the previous class. 3. Problems that can be transformed into the intersection of one γC,one τC, and two planes. This includes T33, T36, T42, T45, T52, T53, T56, T57, T62 and T63. In the following three subsections we present, from easy to hard, the solution of the problems listed above. 6.3.1 Two center constraints in the same cluster This problem can be solved by forcing the cluster with two center constraints to be the moving cluster, so the problem becomes L(E1E2,E 3E 4). Notice that if the moving cluster has two center constraints the cluster fixed has no center constraints. From the fact that the cone-cone intersection can be transformed into cone-plane intersection, [6, 7], the intersection of the geometric elements in the first cluster can always be represented by the intersection of the map of the first element E1with a fixed plane. The algorithm to solve the problem is: Algorithm L(E1E2,E 3E 4) 1. Find the point (x, y)=τE 3∩τE 4. 2. Substitute the point (x+d, y) into the equation of the plane generated in the first cluster and find z(d)whichisadegree one equation of variable d. 3. Substitute the point (x+d, y, z(d)) into the equation of E1 to yield one equation in d. 18 4. Solve the equation to find the value of d. 5. The variable radius circle seeked has (x+d, y) as center point and z(d)asradius. The following three theorems give the tools needed to figure out the intersection of τE 3and τE 4. The first theorem is trivial and applies when both E 3and E 4are straight lines. Theorem 6.2 Two different straight lines Li=[ai,b i,e i]andL2=[aj,b j,e j] which are not parallel, intersect at point (−eibj+ejbi,−aiej+ajei,a ibj−ajbi) The second theorem reduces the line-circle intersection to two line-line intersections. Theorem 6.3 Let L=[a, b, e] be a straight line and C=(x, y, r)acircle. Intersecting Land Cis equivalent to intersecting Land L=[a,b ,e ]where a=a(2t)+b(1 −t2) b=−a(1 −t2)+b(2t) e=−M(1 −t2)−N(2t) and t=±−(ax +by +e−r)/(ax +by +e+r) M=bx −ay N=ax +by Furthermore, the intersection points are (Ax+Cxt, Ay+Cyt, 1) where Ax=bM −ae, Cx=br2−(N+e)2 Ay=−aM −be, Cy=−ar2−(N+e)2 Notice that tis real if and only if −r≤ax +by +d≤rand that each different value for trepresents a different line. Notice further that when intersecting a circle Cwith a line L(d)= [a, b, e−ad], the above theorem applies just replacing eby e−ad or replacing 19 xby x−d. In this case, the relation between tand dbecomes ad(1 −t2)= (e−r)(1 −t2)+N(1 + t2). The third theorem transforms the intersection of two circles into a linecircle intersection. Theorem 6.4 Let Ci=(xi,y i,r i)andCj=(xj,y j,r j)betwocircles. Intersecting Ciand Cjis equivalent to intersect either circle Cior Cjwith the line L=[a, b, e]where a=xj−xi b=yj−yi e=1 2(x2 i+y2 i−r2 i−x2 j−y2 j+r2 j) The number of solutions in each case can be easily calculated. Two lines intersect at most in one point and a line and a circle or two circles intersect at most in two points. If the cluster fixed has two cycles, we can transform the intersection of their cyclographic maps into the intersection of one cone with a plane, which has two equations of degree one. This increases the number of solutions by a factor of 2. Therefore, there is one solution for T11, two solutions for T21, T24, T41, T43, and four solutions for T31, T51, T54 and T61. 6.3.2 Intersection of three planes and one surface In [6, 7], cone-cone intersections are transformed into cone-plane intersections. Let Π(C1,C i) denote the plane that contains the intersection curves of the cones γC1and γCior τC1and τCi. an consider, for example, the subproblem E(CC,CC). First three planes, namely Π(C1,C 2), Π(C1,C 3) and Π(C1,C 4) are intersected. Then this intersection is substituted in the map γC1. We apply this approach here to find the intersection of four cones, with the degree of freedom that the third and fourth cones move along the X-axis or rotate about the origin. We use the similar approach to solve the problem in this criterion. Notice that the intersection of τC1and τC2can be convert into the intersection of τC1with a plane τL. Table 2 summarizes the problems we consider here. The third, fourth and fifth columns give the planes, generated as γand τmaps, whose common point defines the distance dthat the moving cluster must be translated along the X-axis. This common point is then substituted in the equation given in 20 Problem Equation Π1Π2Π3Degree T12: L(LL’,LL’) γL1τL 2γL3(d)τL4(d) 1 T13: L(LL,LL’) γL1γL2γL3(d)τL4(d) 1 T22: L(CL’,LL’) γC1τL2γL3(d)τL4(d) 2 T23: L(C’L,LL’) γC 1γL2γL3(d)τL4(d) 2 T25: L(CL,LL’) γC1γL2γL3(d)τL4(d) 2 T26: L(CL’,LL) γC1τL2γL3(d)γL4(d) 2 T27: L(C’L,LL) τC 1γL2γL3(d)γL4(d) 2 T32: L(CL’,CL’) γC1τL2P(C1,C 3(d)) τL4(d) 4 T34: L(C’L,C’L) τC 1γL2P(C 1,C 3(d)) γL4(d) 4 T35: L(CL,CL’) γC1γL2P(C1,C 3(d)) τL4(d) 4 T44: L(CC,LL’) γC1P(C1,C 2)γL3(d)τL4(d) 2 T55: L(CC,CL’) γC1P(C1,C 2)P(C1,C 3(d)) τL4(d) 4 Table 2: Classification of the three planes and one surface intersection problem. the second column, yielding an equation on the variable dwhose degree is shown in the last column. The specific algorithm to solve the problem can be written as follows. Algorithm L(E1E2,E 3E4) 1. Find the point (x(d),y(d),z(d),w(d)) = Π1∩Π2∩Π3. 2. If circum(E1,C)then M:= γE1 else if center(E1,C)then M:= τE 1 endif 3. Generate one equation with one variable dby replacing (x(d),y(d),z(d),w(d)) in the equation of M. 4. Solve the system of equations to find variable d. 5. The variable radius circle seeked has (x(d)/w(d),y(d)/w(d)) as center point and z(d)/w(d)asradius. 6.3.3 Intersection of one γ-cylinder one τ-cylinder and two planes The Table 3 summarizes the problems we consider in this section. These problems are transformed into the intersection of two planes with a cone, 21 Problem γC τCΠ1Π2Deg 1 Deg 2 Degree T33: L(CL,CL)γC1τC 3(d)τL2γL4(d)(1,1,0) (0,0,0) 4 T36: L(CL,CL)γC1τC 3(d)γL2γL4(d)(1,1,0) (0,0,0) 4 T42: L(CC,LL )γC1τC 2γL3(d)τL4(d)(1,0,0) (0,0,0) 4 T45: L(CC,LL)γC1τC 2γL3(d)γl4(d)(1,0,0) (0,0,0) 4 T52: L(CC,CL )γC1τC 2dP(C1,C 3(d)) τ(L4(d)) (2,2,0) (0,0,1) 8 T53: L(CC,CL)γC1τC 2P(C 2,C 3(d)) γL4(d)(2,2,0) (0,1,1) 8 T56: L(CC,CL)γC1τC 3(d)P(C1,C 2)γL4(d)(1,1,0) (0,0,0) 4 T57: L(CC,CL)γC1τC 2P(C1,C 3(d)) τL4(d)(2,2,0) (0,1,1) 8 T62: L(CC,CC)γC1τC 2P(C1,C 3(d)) P(C 2,C 4(d)) (2,3,0) (0,1,1) 18(16) T63: L(CC,CC)γC1τC 2P(C1,C 3(d)) P(C3,C 4)(d)(2,2,0) (0,1,1) 8 Table 3: Classification of the γC,τCand two planes intersection problem. γC, and a cylinder, τC. The planes Π1and Π2, are given in the fourth and fifth columns, the second column lists the γmap and the third column the τmap. Note that when the moving cluster is translated along the X-axis, the line common to planes Π1and Π2defines the distance d. Assume that Π1=(a1(d),b 1(d),c 1(d),w 1(d)) and Π2=(a2(d),b 2(d),c 2(d),w 2(d)) are two planes in Table 3, the parametric form of the line where Π1and Π2 intersect is L=(a1(d),b 1(d),c 1(d),w 1(d)) + s(a2(d),b 2(d),c 2(d),w 2(d)) The degrees on the variable dof each component in (a1(d),b 1(d),c 1(d)) and (a2(d),b 2(d),c 2(d)) are shown in the sixth and seventh column in Table 3. The algorithm for finding the solution to this class of problems is the following Algorithm L(CE2,E 3E4) 1. According to the subproblem at hand and following Table 3, generate γC,τC,Π 1and Π2) 2. Find the parametric form of the line L=Π 1∩Π2. 3. Generate two equations in dand sby substituting the explicit form of L into the implicit forms of γC and τC. 22 4. Figure out dby solving the system of two equations derived in step 3. 5. Point (a1(d),b1(d)) + s(a2(d),b2(d)) is the center of the variable radius circle and c1(d)+s∗c2(d) is the radius. Applying Bezout’s theorem to the equations derived in step 3 in the Algorithm L(CE2,E 3E4), we find the maximun number of solutions to the problem, which is given in the eight column of Table 3. Notice that compared to the system of equations generated in Section 6.2, this approach yields 2 more solutions for the problem L(CC,CC). 6.4 Algorithms for the Rotational Merge Problem The classification for rotational clusters is the same as in the translational case. All what is needed is to replace Eij with Rij in Table 1 to indicate that the problem has the same constraint pattern but the moving cluster is now rotated. We also separate these problems into three different classes. They are: 1. Problems with two center constraints defined in the same cluster. This includes R11, R21, R24, R31, R41, R43, R51, R54 and R61. 2. Problems which can be transformed into the intersection of three planes and one surface. This includes R12, R13, R22, R23, R25, R26, R27, R32, R34, R35, R44, R55, and part of the problems in the previous class. 3. The remainder of the problems, including R33, R36, R42, R45, R52, R53, R56, R57, R62, R63. 6.4.1 Two center constraints in the same cluster If the cluster with two center constraints is the one that will be rotated, the problems in this class are formally solved in the same way as L(E1E2,E 3E 4). The intersection of the geometric elements in the cluster fixed can always be represented by the intersection of the map of the first element E1with afixedplane. Ifθis the rotation angle and t=tan(θ/2) the algorithm to solve the problem is 23 Algorithm C(E1E2,E 3E 4) 1. Find the point (x, y)=τE 3∩τE 4. 2. Rotate the point (x, y)byanangleθyielding (x(t),y(t)). 3. Replace (x(t),y(t)) into the equation of the plane generated in the first cluster and find z(t) which is a degree one equation in t. 4. Substitute (x(t),y(t),z(t)) into the equation of E1to yield one equation in t. 5. Solve the equation to find the value of t. 6. The seeked circle is centerd on (x(t),y(t)) and z(t) is the radius. 6.4.2 Intersection of three planes and one surface Problems in this class, C(E1E2,E 3E4), are solved as problems in the corresponding translational class L(E1E2,E 3E4) replacing the translation with the rotation αIf t=tan(θ/2), the algorithm is Algorithm C(E1E2,E 3E4) 1. Find the point (x(t),y(t),z(t),w(t)) = Π1∩Π2∩Π3. 2. If circum(E1,C)then M:= γE1 else if center(E1,C)then M:= τE 1 endif 3. Generate one equation with one variable tby replacing (x(t),y(t),z(t),w(t)) in the equation of M. 4. Solve the system of equations to find variable t. 5. The variable radius circle seeked has (x(t)/w(t),y(t)/w(t)) as center point and z(t)/w(t)asradius. To justify the degree reduction, we need the following result. Theorem 6.5 Consider three planes with constant coefficients except for t: Π1=[a2,b 2,c 2,−d2] Π2=[a3(1 −t2)−b3(2t)+e3(1 + t2),a 3(2t)+b3(1 −t2)+f3(1 + t2), c3(1 + t2),−d3(1 + t2)] Π3=[a4(1 −t2)−b4(2t)+e4(1 + t2),a 4(2t)+b4(1 −t2)+f4(1 + t2), c4(1 + t2),−d4(1 + t2)] 24 Then Π1,Π2and Π3intersect in a point (x(t),y(t),z(t),w(t)) whose components are expressions of degree 2 in t. Now it is easy to show that problems in this class have two solutions when the first component E1is a ray, such as in problems C12 and C13. Otherwise, they have 4 soultions, such as in problems C22, C23, C25, C26, C27, C32, C34, C35, C44 and C55. The number of solutions is given in the Table 1. 6.4.3 Remainder Problems The remainder subproblems of rotational merge problems are C33, C36, C42, C45, C52, C53, C56, C57,C62 and C63. Unfortunately, the strategy presented in Section 6.3 does not work here because the degree of the parametric line generated at an intermediate step does not allow to reduce the final degree of γC and τC. We need to derive some results before presenting our algorithm. Let C be a cycle centered at (x1,y 1)with(signed)radiusz1and let Land Lbe rays with equations a2x+b2y+d2=0,anda2 2+b2 2= 1 respectively. Let δ=(a2,b 2,d 2)·(x1,y 1,1) = (a2x1+b2y1+d2). Theorem 6.6 The intersection points for γC and γL are given by ⎧ ⎪ ⎨ ⎪ ⎩ x(u)=x1+z11−u2 1+u2−δ w(u)(1 −u2) y(u)=y1+z12u 1+u2−δ w(u)(2u) z(u)=2z1−δ w(u)(1 + u2) Notice that when z1= 0, the locus of the intersection points in the above theorem can be written in homogeneous form as: ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ x(u)=x1w(u)−δ(1 −u2) y(u)=y1w(u)−δ(2u) z(u)=δ(1 + u2) w(u)=(a2,b 2,−1) ·(1 −u2,2u, 1+u2) Theorem 6.7 The intersection points for γC and τLare ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ x(u)=x1w(u)−δ(1 −u2) y(u)=y1w(u)−δ(2u) z(u)=z1w(u)−δ(1 + u2) w(u)=(a2,b 2,0) ·(1 −u2,2u, 1+u2) 25 where Π = [x1−x0,y 1−y0,z 0−z1,(x2 0+y2 0−z2 0−x2 1−y2 1+z2 1)/2]. Theorem 8.12 The cyclographic map for the ray [a, b, d] rotated about the origin by θhas the form [a(1 −t2)−b(2t),a(2t)+b(1 −t2),c(1 + t2),d(1 + t2)] where t=tan(θ/2), −π<θ<π,andc=−√a2+b2.Whenθ=π,the cyclographic map becomes [−a, −b, c, d]. Theorem 8.13 Let L=[a, b, d]bearay.ThemapsγL(θ)andτL(θ)have the form [a(1 −t2)−b(2t)+e(1 + t2),a(2t)+b(1 −t2)+f(1 + t2),c(1 + t2),d(1 + t2)] where t=tan(θ/2), −π<θ<π,e=f=0,andc=−√a2+b2,c=0 for the γL(θ)andτL(θ) respectively. When θ=π,theγL(θ)andτL(θ) becomes [−a, −b, c, d]. Theorem 8.14 Let C 1=(x1,y 1,z 1)andC 3=(x3,y 3,z 3). The intersection plane of τC 1and τC 3(θ) has the form [a(1 −t2)−b(2t)+e(1 + t2),a(2t)+b(1 −t2)+f(1 + t2),c(1 + t2),d(1 + t2)] where t=tan(θ/2), −π<θ<π,a=x3,b =y3,e =−x1,f =−y1,c =0, and d=(x2 1+y2 1−z2 1−x2 3−y2 3+z2 3)/2. When θ=π, the cyclographic map becomes [−a+e, −b+f,0,d]. 32