用连杆机构几何约束求解_英文_

用连杆机构几何约束求解_英文_ () u rna l o f So f tw a re ? ? ? ?2000, 11 9: 1151~ 1158JoISSN 100029825 ?? Geom e tr ic Con stra in t So lv in g w ith L in kage s 22GAO X iao shan ZHU Changca i ( )100080In st itu te o f Sy stem s Sc ience T h e C h ine se A cadem y o f Sc ience s B e ijing 2: , @. . . E m a ilxgao czh umm rcissaccn A bstrac tT h is p ap e r in t ro duce s link age s a s new d raw ing too l and show s th a t th is too l is com p le te, i. e. , a ll diag ram s th a t can be de sc r ibed co n st ruc t ive ly can be d raw n w ith link age s. T h is c la ss inc lude s th e co n st ra in t . , . , .p ro b lem s w ith d istance co n st ra in t s o n lyA s an app lica t io nth e au tho r s show th a t th e sim p le st co n st ra ined g rap h w h ich is beyo nd th e scop e o f Ow en and H o ffm ann' s pop u la r t r iang le decom po sit io n m e tho d s can be t ran sfo rm ed to p u re ly geom e t r ic co n st ruc t ive fo rmT o so lve th e equa t io n s de r ived f rom link age co n st ruc t io n sa geom e t r ic m e tho d w h ich is ba sed o n dynam ic lo cu s gene ra t io n is p ropo sed Key words Geom e t r ic co n st ra in t so lv ing, CA D , link age, co n st ra ined g rap h , geom e t r ic m e tho d. 1In troduc t ion 1 () . , , , . GCA u tom a ted geom e t ry d iag ram co n st ruc t io n o r geom e t r ic co n st ra in t so lv ing Sis th e cen t ra l top ic in m uch o f th e cu r ren t w o rk o f deve lop ing p a ram e t r ic CA D sy stem sIt a lso h a s app lica t io n s in m ech an ica l eng inee r ingch em ica l m o lecu la r m o de linglink age de sign com p u te r v isio n and com p u te r a ided in st ruc t io n T h e re a re fo u r !? 2 5 !? 6 8 ,m a in app ro ach e s to GC S:th e grap h ana ly sis app ro ach th e ru le2ba sed app ro ach , th e num e r ica l9, 10!? 11 13 com p u ta t io n app ro ach ,. , thand e sym bo lic com p u ta t io n app ro ach In p rac t icem o st p eop le u se a com b ina t io n o f th e se app ro ach e s to ge t th e be st re su lt. 22. , . T h e g rap h ana ly sis and th e ru leba sed app ro ach e s a re a lso ca lled th e geom e t r ic app ro achIn th is app ro ach a p ret rea tm en t is ca r r ied o u t to t ran sfo rm th e co n st ra in t p ro b lem in to a co n st ruc t ive fo rm th a t is ea sy to d rawIn , . . , . , . . 14 , , , . , , . . , . . , m o st ca se sth is is equ iva len t to co n st ruc t th e d iag ram sequen t ia lly w ith ru le r and com p a ssT h is can a lso be unde r stoo d a s d raw ing th e d iag ram w ith geom e t r ic too lsB u t w ith ru le r and com p a ssw e can o n ly d raw a sm a ll po r t io n o f th e d iag ram sIt is w e ll k now n th a t u sing ru le r and com p a ss a lo new e can de sc r ibe d iag ram s w ho se equa t io n sy stem s a re a sequence o f t r iangu la r ized equa t io n s o f deg ree le ss th an o r equa l to tw oIn R efa new too lco n ic sis added to en la rge th e so lv ing scop e to d iag ram s th a t can be de sc r ibed by a sequence o f t r iangu la r ized equa t io n s o f deg ree le ss th an o r equa l to fo u rIn th is p ap e rw e w ill in t ro duce link age s a s new too ls and show th a t th is too l is com p le te in ce r ta in sen seieany gene ra l co n st ruc t ive d iag ram can be d raw n w ith link age s sequen t ia llyW e a lso g ive an a lgo r ithm to f ind link age s in a co n st ra ined d iag ramA s an app lica t io nw e p ro ved 2 2 22th a t a ll w e llo r unde rco n st ra ined p ro b lem s co n ta in ing po in tto po in t d istance co n st ra in t s o n ly can be so lved w ith .link age s co n st ruc t ive ly ??T h is re sea rch is suppo r ted in p a r t b y th e N a t io n a l K ey B a sic R e sea rch P ro jec t o f C h in a( ) ???????????!????????, . 1998030600N oJ an d b y th e N a t io n a l N a tu ra l Sc ien ce Fo u n da t io n o f ( )????*???????????!?????????????, . 69725002.N oC h in a u n de r an O u t stan d in g Yo u th G ran t - - 1963. , . , , . 1974. . . , . .GAO X iaoshan w a s bo rn in H e is a p ro fe sso r in th e In st itu te o f Sy stem s Sc ienceT h e C h ine se A cadem y o f Sc ience sH is re sea rch in te re st s inc lude au tom a ted rea so n ingsym bo lic com p u ta t io ncom p u te r g rap h ic s and in te lligen t CA D and com p u te r a ided in st ruc t io nZHU Chan gca i w a s bo rn in H e is a P hDcand ida te in th e In st itu te o f Sy stem s Sc ienceT h e C h ine se A cadem y o f Sc ience sH is re sea rch a rea s a re in te lligen t CA D and com p u te r a ided in st ruc t io n222220000316, 20000418.M anu sc r ip t rece ived accep ted T o so lve th e equa t io n s de r ived f rom link age co n st ruc t io n s, be side s th e o f ten u sed num e r ica l and sym bo lic !? 15 17 ., . com p u ta t io n m e tho d sw e in t ro duce a geom e t r ic m e tho d w h ich u se s th e link age s to gene ra te lo c i and th en f ind s th e in te r sec t io n o f th e se lo c i by sea rch ing th e po in t s o n th e lo c iT h is geom e t r ic m e tho d is ba sed o n dynam ic gene ra t io n o f geom e t r ic lo cu s w h ich is w ide ly u sed in dynam ic geom e t r ic so f tw a re 3.M o st o f th e re su lt s p re sen ted in th is p ap e r can be ex tended to D ca se , . A s an app lica t io n o f th e m e tho d in t ro duced in th is p ap e rw e show th a t th e sim p le st co n st ra ined g rap h w h ich is beyo nd th e scop e o f Ow en and H o ffm ann' s t r iang le decom po sit io n m e tho d s can be t ran sfo rm ed to p u re ly geom e t r ic co n st ruc t ive fo rm if link age s a re a llow ed a s co n st ruc t io n too lsT h e link age s u sed in th e co n st ruc t io n a re 2. ree thk ind s o f fo u rba r link age s . 2 . 3 . 4, .T h e re st o f th is p ap e r is o rgan ized a s fo llow sSec t io n w ill show th e d raw ing scop e o f u sing link age s a s co n st ruc t io n too lsSec t io n w ill p re sen t th e geom e t r ic m e tho d fo r so lv ing equa t io n sIn Sec t io n w e w ill show how to so lve th e sim p le st co n st ra ined g rap h 2 Con struc t ion w ith L in ka ge s M o st o f th e geom e t r ic app ro ach e s to GC S is to t ran sfo rm a co n st ra ined p ro b lem in to co n st ruc t ive fo rm w ith . . ru le r and com p a ssW e gene ra lize th is co ncep t a s fo llow sA geom e t r ic d iag ram can be d raw n co n st ruc t ive ly o r in co n st ruc t ive fo rm if th e geom e t r ic o b jec t s in it can be listed in an o rde r () , , . . . , O 1 O 2 O m , () thsuchS a t each O can be de te rm ined by O , . . . , O w ith a se t o f geom e t r ic co n st ra in t ince s.a ll geom e t r ici 1 i- 1 o b jec t s can be t rea ted a s func t io n s o f po in t s, w e m ay a ssum e w itho u t lo ss o f gene ra lity th a t th e geom e t r ic o b jec t s . . 2, .a re po in t sT h e a lgeb ra ic equa t io n s fo r a d iag ram in co n st ruc t ive fo rm is na tu ra lly d iv ided in to b lo ck sIn D ca seth e a lgeb ra ic equa t io n s a re a s fo llow s () = f u , . . . , u, x , x 01, 1 1 m 1 2 () f u , . . . , u, x , x = 01, 2 2 m 1 2 () , . . . , , , , = 0f u ux x x 2, 1 1 m 1 3 4 ()2. 1.() f u , . . . , u, x , x , x = 02, 2 2 m 2 3 4 fi () f , . . . , u, x , . . . , x l, 2 1 m 1 p u = 0 ( ) 2. 1, . , , . S ince th e va r iab le s a re in t ro duced o ne by o ne o r tw o by tw o w e m ay t r iangu la r ize E qea silysayu sing re su ltan t com p u ta t io nL e t th e t r iangu la r ized equa t io n s be () 1 1 m 1 = tu , . . . , u, x 0 () = tu , . . . , u, x , x 02 2 m 1 2 ()2. 2.fi () = tu , . . . , u, x , . . . , x 0p 1 m 1 p , It is w e ll k now n th a t u sing ru le r and com p a ss a lo new e can de sc r ibe d iag ram s w ho se equa t io n sy stem s a re o f ( ) ( ) 14 ,2. 2. !?2. .i thand e fo rm E qdeg ree tIn R efa new too l, co n ic s, is added to en la rge th e scop e to so lve () ( ) : 2. 2!?4.i A na tu ra l que st io n iscan w e add m o re too ls such th a t th eand equa t io n sy stem s o f fo rm E q.deg ree t d iag ram s can be d raw n w ith th e se too ls co ve r ing a ll d iag ram s in co n st ruc t ive fo rm. T h e an sw e r is po sit ive. ()222. 1. , . : , , .B y a link agew e m ean a m ech an ism w ith o ne deg ree o f f reedom and co n sist ing o f link s w ith f ixed leng th s and ro ta t io n jo in sO ne exam p le is th e fo llow ing fo u rba r link age A B CD P F igT h e lo cu s o f th e fo u rba r link age in th e f igu re is gene ra ted a s fo llow sw ith po in t s A B f ixed and C ro ta t ing o n a c irc lepo in t P w ill gene ra te th e lo cu s ???!?? ??: ??????????????????????!? 1153 !? A d iag ram can be d raw n w ith link age s co n st ruc t ive ly if th e po in t s in th e d iag ram can be listed in an o rde r (), , . . . , P P m 12P , . . . , .such th a t each po in t P i is in t ro duced by th ree ba sic co n st ruc t io n s u sing th e po in t s a lready d raw n P 1 P i- 1 () () 1PO IN T P : tak ing a f ree po in t P in th e p lane. () () 22, : .ON tak ing a sem P L if ree po in t P o n th e lo cu s L o f a link age () ) (3, , : .IN tak ing T ER P L 1 L 2 th e in te r sec t io n P o f L 1 and L 2 w h ich a re th e lo c i o f tw o link age s 2. 1. .Theorem A d iag ram is in co n st ruc t ive fo rm iff it can be d raw n w ith link age s .P roof It is read ily seen th a t th e lo cu s o f a link age is an a lgeb ra ic2. 1 F igT h e fo u rba r link age andcu rve. T h e refo re, w e need o n ly to show th a t any d iag ram in co n st ruc t iveit s lo cu s. fo rm can be co n st ruc ted w ith link age sT h is is va lid becau se o f a fam o u s18 () = 0. , re su lt o f Kem p e w h ich sta te s th a t w e m ay de sign a link age to d raw any g iven a lgeb ra ic cu rve f x y In R ef. 18 , w e im p ro ved and im p lem en ted Kem p e' s re su lt and show ed th a t th e com p lex ity o f th e Kem p e link age is4 () !?.w O nh e re n is th e deg ree o f f , 2S ince link age s co u ld be ve ry com p lica tedit seem s th a t ru leba sed app ro ach e s a re m o re app rop r ia te to . 2, t ran sfo rm a co n st ra in t sy stem in to co n st ruc t ive fo rmFo r a ru leba sed sy stem lik e th e g lo ba l p rop aga t io n m e tho d . 6 , .de sc r ibed in R efw e m ay add th e fo llow ing a lgo r ithm to f ind a link age 2. 2. . . .A lgor ithm Suppo se th a t w e need to co n st ruc t po in t P 0W e w ill f ind a link age co n ta in ing P 0A po in t is sa id to be k now n if it h a s a lready been co n st ruc ted | | 1 , . .SIf th e re is a k now n po in t Q such th a t P 0Q is k now n th en P 0 is o n a c irc leT h e a lgo r ithm te rm ina te s = , 2.and go to O th e rw isele t S 0 P 0 S 2 ? !?, ? !?, . . | | . , SL e t S 1 be th e se t o f po in t s such th a t P S 1 Q S 0 stPQ is k now nIf S 1 is an em p ty se tth e a lgo r ithm te rm ina te s w itho u t f ind ing a link age. S3 L e t d be th e num be r o f d istance co n st ra in t s be tw een p a ir s o f po in t s in S !?S bu t no t inc lud ing p a ir s o f tw o1 0 , !?.1 0k now n po in t sn be th e num be r o f unk now n po in t s in S S 4 = 2- 1, !?. .SIf d n th en th e po in t s in S 1 S 0 co n sist o f a link ageT h e a lgo r ithm te rm ina te s > 2- 1, 22< 2- 1,5 . . , . . , SIf d n th en th e re is an o ve rco n st ra ined sub d iag ramT h e a lgo r ithm te rm ina te s w itho u t f ind ing a link ageO th e rw iseied n = !?2.0 1 0 le t S S S and go to S 2. 3.E x am p le In F ig. 2, th e leng th s o f th e n ine segm en t s a re k now n. T ry to d raw th e d iag ram. . , .W e m ay f ir st d raw t r iang le A B CN ex tw e w ill de te rm ine po in t P || , . 22. 22.S ince C P is k now nP is o n a c irc leU sing th e abo ve a lgo r ithm w e can f ind th a t po in t P is o n a fo u rba r link age A B U V PT h en P is th e in te r sec t io n o f a c irc le and th e lo cu s o f th e fo u rba r link age A B U V P F ig. 2 Po in t P is th e in te r sec t io no f tw o lo c i 3Eva lua t ion of Con struc t ion Sequen ce s of L in ka ge s () , , . . . , , , G iven a co n st ruc t io n sequence C 1 C 2 C n by in t ro duc ing coo rd ina te s p rop e r lyw e m ay o b ta in an ()2. 1.N ow w e w ill show how to so lve th is equa t io n sy stem. B a sica lly, w e need to so lve tw oequa t io n sy stem E q. .a lgeb ra ic equa t io n s () m 1f , . . . , u, x , y = 0u()3. 1.() = g u , . . . , u, x , y 0 m 1 P lea se no t ice th a t in ce r ta in ca se s, th e equa t io n s f and g a re th e equa t io n s o f th e lo c i fo r som e link age s, w h ich a re .no t exp lic it ly g iven ( )3. 1. . , . , . .If th e link age is com p lexth en it is d iff icu lt to f ind th e equa t io n o f it s lo cu sIn th is ca sew e m ay u se th e lo cu s in te r sec t io n m e tho d to f ind th e so lu t io n s o f E qSuppo se th a t w e need to f ind th e in te r sec t io n o f tw o lo c i L 1 and L 2T h e lo cu s in te r sec t io n m e tho d h a s tw o m a in step s 16 . . .Gen era te L ocusL o cu s gene ra t io n is a ba sic func t io n o f dynam ic geom e t ryIt w o rk s a s fo llow s () 1.. . 1, F ind a d r iv ing po in t w h ich w ill m o ve f ree ly o n a c irc leIn F iga d r iv ing po in t co u ld be C ()2S ta r t ing f rom th is d r iv ing po in t, f ind a sequence o f co n st ruc t io n s w ith line and c irc le to co n st ruc t th e w ho le link age. ( ) 3, . , .Fo r each po sit io n o f th e d r iv ing po in tw e m ay com p u te th e coo rd ina te s o f th e po in t s in th e link ageIn p a r t icu la rth e coo rd ina te s o f th e lo cu s po in t ( ) 4, . R ep ea t ing th e p reced ing step w e h ave a se t o f coo rd ina te s o f th e lo cu s po in tW e m ay u se line s o r B ezie r .cu rve s to co nnec t tw o ne igh bo r ing po in t s to fo rm a co n t inuo u s lo cu s !?. , 1 2 1 1 L L P L F in d In ter sec t ionA f te r th e tw o lo c i and a re gene ra tedw e sea rch th em to f ind tw o po in t s and !?| | .2 2 12 P L such th a t P P h a s m in im a l va N o luet ice th a t th e re m igh t be m o re th an o ne so lu t io n. In p rac t ice, th is m e tho d is qu ite eff ic ien t, becau se to gene ra te th e lo cu s w e need o n ly to so lve linea r and 17 .quad ra t ic equa t io n s w h ich h ave c lo sed fo rm so lu t io n s .W e f ir st u se an exam p le to illu st ra te th e m e tho d p re sen ted in th e p reced ing sec t io n 3. 1. . 3, . .E x am p le A s show n in F igth e leng th s o f th e n ine segm en t s a re k now nT ry to d raw th e d iag ram , . . . :W e m ay f ir st d raw po in t s E B N ow po in t D is th e in te r sec t io n o f a c irc le and th e lo cu s o f a link age EB F CA L e t F be th e d r iv ing po in tT h e co n st ruc t io n sequence fo r th e link age is a s fo llow s () )(, , | | C IR ON F E E F ) () ) ) () ) ) () )((((((, , , , , || , | | , , | | , || , , || , | | C IR C IR C IR IN T ER C C IR B B C F F C IN T ER A C IR E EA C CA IN T ER D C IR A A D F FD ) (|| ||, . , rep w h e re C IR B B C re sen t s th e c irc le w ith cen te r B and rad iu s B C W ith th e abo ve co n st ruc t io n sequencew e m ay F ig. 3 A co n st ra ined p ro b lem w ith six po in t s(,gene ra te th e lo cu s fo r po in t D w h en po in t F m o ve s o n C IR E 17 ). . 3 | | .F igis E F ac tua lly gene ra ted in th is w ay by a so f tw a re nam ed Geom e t ry E xp e r t 2. 3 3. 1 22. . .Bo th E xam p le s and co n ta in po in tto po in t d istance o n lyIt is no t d iff icu lt to ch eck th a t th ey a re th e tw o sm a lle st po ssib le co n st ra in t p ro b lem s o f th is k ind th a t can no t be so lved by ru le r and com p a ss co n st ruc t io nW e w ill show th a t a ll co n st ra in t p ro b lem s o f th is k ind can be so lved by link age s co n st ruc t ive ly 2 2 223. 2. Theorem A ll w e llo r unde rco n st ra ined p ro b lem s co n ta in ing po in tto po in t d istance co n st ra in t s o n ly can .be so lved w ith link age s co n st ruc t ive ly 22.P roof W e need o n ly co n side r w e llco n st ra ined p ro b lem s since unde rco n st ra ined p ro b lem s m ay becom e 222. w e llco n st ra ined p ro b lem s by add ing app rop r ia te num be r o f po in tto po in t d istance co n st ra in t sW e a ssum e th a t || 2- 3 , . . . . . . , . , . thL e p ro b lem co n ta in s n po in t sT h en it m u st h ave n co n st ra in t sL e t u s a ssum e th a t A B is k now nW e f ir st d raw A B e t C be a po in t such th a t A C is k now nW e w ill co n st ruc t po in t CS ince A C is k now nit is a lready o n a c irc leIf B C is a lso k now nw e m ay co n st ruc t C a s th e in te r sec t io n o f tw o c irc le sR ep ea t th e abo ve p ro ce ss ???!?? ??: ??????????????????????!? 1155 !? un t il w e canno t go fu r th e r. L e t S be th e se t o f po in t s co n st ruc ted in th is w ay, T be th e se t o f th e rem a in ing po in t s, = || , = | |. + = .and t T h en tkSTkn ()!?!? - . || . || . 2 || , T h e re m u st be po in t s P T and Q S such th a t PQ is k now nW e w ill co n st ruc t P w h ich is a lready o n a c irc le since PQ is k now nT h e num be r o f co n st ra in t s no t u sed in S is n k S ince PQ is a lso u sedw e h ave () () 2 - - 1 2 - 1= 2 - - 1 . , . 2. 2, , . co n st ra in t s lef tFo r th e po in t se t T to fo rm a link agew e need t co n st ra in t sT h en by A lgo r ithm T fo rm s a link ageand P is th e in te r sec t io n o f a c irc le and th e lo cu s o f th is link ageT h enknk !?rem a in ing po in t s can be t rea ted sim ila r ly. 4 A Sm a lle st Tr iconn ec ted Con stra in ed Gra ph H o ffm ann and Ow en' s t r iang le decom po sit io n m e tho d is o ne o f th e m o st pop u la r m e tho d s o f GC S. Co n st ra ined 3, 4 2. ,. 2 g rap h s th a t can be so lved by th e se m e tho d s a re no n t r ico nnnec ted g rap h sA s it is po in ted o u t in R efth e sim p le st co n st ra ined g rap h th a t canno t be so lved w ith th e se m e tho d s is th e fo llow ing g rap h. T h e ve r t ice s o f th e . :g rap h co u ld be a po in t o r a lineT h e edge s rep re sen t geom e t r ic co n st ra in t s Geom e t r ic co n st ra in t rep re sen ted by th e edge P a ir o f ve r t ice sD istance be tw een tw o po in t s A ng le fo rm ed by th e tw o line s???Po in tPo in t L ineL ine Po in tL ine Co inc idence o r d istance f rom po in t to line S ince each ve r tex o f th e co n st ra ined g rap h in F ig. 4 co u ld be a po in t o r a line, ) (: , . = , 2. 4 . = , 2. 4 . , . 4 13 .w w e m ay in t ro duce a no ta t io n to rep re sen t th e g rap hV 1V 2V 3 V 4V 5V 6 h e re V i co u ld be P o r L If V i P th en th e ith po sit io n in F igis a po in tIf V i L th en th e ith po sit io n in F igis a lineW ith th is no ta t io nF igrep re sen t s typ e s o f co n st ra ined g rap h s 4. 1. 13 .Theorem A ll th e p ro b lem s can be so lved w ith link age s co n st ruc t ive ly1 13 .T ab le g ive s th e info rm a t io n o n how to so lve th e p ro b lem s4F ig.Sm a lle st t r ico nnec ted g rap h?222 1, ; , In T ab le P L m ean s th e typ e o f po in tline co n st ra in tT yp e m ean s w h e th e r th e p ro b lem is w e llo ve ro r )( 2?; ; unde rco n st ra inedR C m ean s w h e th e r th e p ro b lem can be d raw n w ith ru le r and com p a ssL o cu s o ne tw o .m ean s th e m o st com p lica ted lo c i o r link age s needed in th e co n st ruc t io n ?. , 8 8. 3 . .Som e o f th e ca se s h ave been co n side redFo r in stanceca se s and ' a re so lved in R efw ith Gobne r ba sis m e tho dW e w ill show th a t a ll o f th e th ir teen ca se s can be so lved co n st ruc t ive ly if link age s a re a llow ed a s d raw ing too ls , . 1 2. 3. 2 1. 3, 6O f th e th ir teen ca se sf ive u se link age sC a se is E xam p le C a se is sim ila r to ca se C a se s '' and 8.' need tw o new typ e s o f link age s 22, !?A n l lfo u rba r link age co n sist s o f tw o f ixed line s u v and a t r iang le PA B w ith f ixed sh ap e such th a t A u and (() )()!?. . 5 . , .B vT h e lo cu s is gene ra ted by po in t P F igaT h is link age is deno ted by u vA B P 22, a A n lcfo u rba r link age co n sist s o f a f ixed line lf ixed c irc le c and a t r iang le PA B w ith f ixed sh ap e such th a t ((()) )!?!?. . 5 , F igb.A l and B cT h e lo cu s is gene ra ted by po in t P . T h is link age is deno ted by u cA B P , . B y th e def in it io n o f link age sa po in t canno t m o ve o n a lineT h is p ro b lem can be so lved w ith th e fam o u s )(() .. 5 P eauce lie r link age w h ich m ay gene ra te a st ra igh t line F igc () () () ()() ()2| | 22. .6 3. . , , , , , , F igu re ais th e geom e t r ic d iag ram fo r ca se 'W e m ay f ir st d raw u v PS ince d istance B u and d istance C v a re k now n B and C m o ve o n tw o line s and w e h ave an lllink age u vB C A N ow A is th e in te r sec t io n o f c irc le C IR P PA and th e lo cu s o f th e llfo u rba r link age u vB C A Table 1 T h ir teen t r ico nnec ted co n st ra in t g rap h s P ro b lem P ?L T yp e R ?C L o cu s o ne L o cu s tw o 1A ny u r2ba rfo irc le linec2A ny o N o Ye sNc irc le2fo u rba r c irc leN o3Co inc idencelinell2fo u r2ba r3D istance' 4W e ll W e ll W e ll W e ll O ve r W e ll5()A ny, P P P P P P U nde r W e ll W e ll6Co inc idence irc le c irc lec() () () () () () () () () () (, , , , , ), , , , , P P P P PL P P P PL L P P P PL L P P P L L L P PL P PL P PL L P P P PL L P P P PL PL L P PL L L P P PL L L P P PL , L L L U nde r22lcfo u rba r(), 6PL L PL L 'D istance s Ye s N irc o Ye le line line line line s Ye sYecW e ll O ve r O ve rN oline7A nyc irc le c irc leW e ll228llfo u rba rCo inc idence 8'D istance 9 10 11(), A nyYe slinec irc lePL L L L P ()12, O ve rPL L L L L () 13 , L L L L L L O ve r ()()()acb 2. 5 F igTw o new fo u rba r link age s ()()()acb 2. 6 F igT h ree co n sta in t p ro b lem s w h ich need fo u rba r link age s () 68. 6 8. C a se s ' and ' need sp ec ia l exp lana t io nF igu re cis th e geom e t ry d iag ram fo r ca se 'W e f ir st d rawth e ( ) . . , , , . P u vllP l dN is iag ram ex tw e w ill d raw line S ince d istance k now nis tangen t to a c irc leT h en w e m ay . 22, . . . 6.geneN o te and to ra te th e lo cu s o f lth a t A B l is a r ig id bo dy and po in t s A and B m o ve o n tw o line sT h en w e m ay u se an llfo u rba r link age to sim u la te th e m o vem en t o f th e r ig id bo dy A B lgene ra te th e lo cu s o f lT h e po sit io n o f l can be de te rm ined a s th e in te r sec t io n o f th e tw o lo c i o f line sC a se ' can be t rea ted sim ila r ly 24, 9, 10, 12, 13 , . ,C a se s a re o ve rco n st ra inedbecau se th e re a re co nf lic t ing co n st ra in t sH ow eveif thr e se ???!?? ??: ??????????????????????!? 1157 !? 2, co n st ra in t s in th em a re com p a t ib lea ll o f th e co n st ra ined sy stem s a re unde rco n st ra ined sy stem and can be d raw n .w ith ru le r and com p a ss ea sily .5, 7 11 . . 6 C a se s and can be d raw n w ith ru le r and com p a ssT h ey can be so lved w ith th e G lo ba l P rop aga t io n m e tho d in R ef (() ) !?T o so lve ca se 5 F ig. 7 a , w e f ir st d raw PQ u. S ince A B v and PQ u a re r ig id bo d ie s, w e k now th e ang le . !??!, : .N ow w fo rm ed by line s A B and PQth e p ro b lem is t ran sfo rm ed in to th e fo llow ing o ned raw a quad r ila te ra l if w e k now th e leng th s o f it s fo u r side s and th e ang le fo rm ed by a p a ir o f oppo site side sh ich h a s been so lved in R ef 6 . () () ) (!?. . . . , 6 . 7 , , || , 5, , bN is T o so lve ca se F ig w e f ir st d raw u v Pex tw e w ill d raw po in t A S ince PA is k now n A is o n a c irc le cS im ila r to ca se w e k now th e ang le be tw een line s A B and uS ince d istance B v k now nB is o n !?, .,S ince B and th e d irec t io n o f line A B A |A| BAa line l1a re k now n and B m o ve s o n line l1by t ran sfo rm a t io n m u st m o ve o n ano th e r line l2. A is th e in te r sec t io n o f c and l2. Fo r de ta ils abo u t th is k ind o f t ran sfo rm a t io n, see .. 6 R ef () () (() ) !?. . | | !? , !? , . 11 . 7 , , , . , , .N and N ow T o so lve ca se F igcw e f ir st d raw u v Pex tw e w ill d raw line nS ince d istancenP is k now nn is tangen t to a c irc leS ince n m m u a re k now nw e k now th e d irec t io n o f nn is a line w ith k now n d irec t io n and tangen t to a k now n c irc leand th u s can be de te rm ined ()()()cab F ig. 7 T h ree p ro b lem s w h ich can be so lved w ith ru le r and com p a ss Ref eren ce s 1 !? . . : , , 1999. 226252Gao X SA u tom a ted Geom e t ry D iag ram Co n st ruc t io n and E ng inee r ing Geom e t ryInA u tom a ted D educ t io n in Geom e t rySp r inge r22 3!? . . : , . . , 1995. 266298H o ffm ann CGeom e t r ic Co n st ra in t So lv ing in R and R InD u D ZH uang F ed sCom p u t ing in E uc lidean Geom e t ryW o r ld Sc ien t if ic ( ) H o ffm ann C M , L om o no so v A , S ith a ram M . F ind ing so lvab le sub se t s o f co n st ra in t g rap h s. L N C S, 1997, 1330: 163!? 1973. . : , . : , 1991. 397!? 407Ow en JA lgeb ra ic So lu t io n fo r Geom e t ry f rom D im en sio na l Co n st ra in t sInA CM Sym po sium Fo und o f So lid M o de lingA u st in T XA CM P re ss4, . . : 6 Yuan B Sun J GA g rap h ba sed app ro ach to de sign decom po sit io nInP ro ceed ing s o f th e th In te rna t io na l Co nfe rence o n . , , 1999. 984!? 988CA D &C GSh angh a iC h ina521998,, . , . , Gao X SC ho u S CSo lv ing geom e t r ic co n st ra in t sy stem s Ia g lo ba l p rop aga t io n app ro achCom p u te rA ided D e sign ( ): 30 147!? 546. : . , 1992K ram e r G ASo lv ing Geom e t r ic Co n st ra in t s Sy stem sA C a se S tudy in K inem a t ic sM IT P re ss 222,, , . . V e r ro u st A Scho nek F Ro lle r DR u leo r ien ted m e tho d fo r p a ram e te r ized com p u te ra ided de signCom p u te rA ided D e sign 7( ): 1992, 24 10531!? 5408 9Ge J X , P en Q X , D o ng J X et l. N ew a lgo r ithm s fo r au tom a t ic sh ap e so lv ing ba sed o n co n st ra in t s. C h ine se Jo u rna l o fa ( )Com p u te r s, 1995, 18 2: 114!? 12610( )23: 171!?, , . . , 1981, 15 L in V C Go ssa rd D C L igh t R AV a r ia t io na l geom e t ry in com p u te ra ided de signCom p u te r G rap h ic s 17711( )2222: 115!? 122, . , . , 1998, 30 Gao X iao sh anC ho u S CSo lv ing geom e t r ic co n st ra in t sy stem s IIa sym bo lic app ro ach and dec isio n o f R cco n st ruc t ib ilityCom p u te rA ided D e sign 2,. . Ko ndo KA lgeb ra ic m e tho d fo r m an ip u la t io n o f d im en sio na l re la t io n sh ip s in geom e t r ic m o de lsCom p u te rA ided D e sign 12( )1992, 24 3: 141!? 147 2000. . , W u W TM a th em a t ic s M ech an iza t io nSc ience P re ss13( )228: 30!? 47, . . , 1999, Gao X iao sh anJ iang KGeom e t r ic co n st ra in t so lv ing w ith co n ic sM M P rep r in t s141994. . , , GA BR I Geom e t ry IIT exa s In st rum en t sD a lla sT exa s151994. . . , J ak iw NGeom e te r' s Sk e tchp adU se r Gu ide and R efe rence M anua lKey C u r r icu lum P re ss162, , . . , , 1998Gao X iao sh anZh ang J ZC ho u S CGeom e t ry E xp e r tN ine C h ap te r P ub T a iw an1722, . . Gao X iao sh anZh u C h angca iA u tom a ted gene ra t io n o f Kem p e link age and it s com p lex ityJo u rna l o f Com p u te r Sc ience and18T ech no lo gy, 1999, 14: 460!? 467 ??????????? ???!?? ?????? ()???????????????????????? ???? 100080 ??????????????*/??????????, ?????/??????????, ????????, ??????????????????????????????????*/??,??????????????????????????????????????. */??????????, ???/???????? ??????E???E?E?????Ow en H o ffm ann ??*?????????????????*???????????????????. ????????????????????????E???, ?????????????????????????? ??????E?E?. , , , , .??? ?????????????????????????????????????????????? ??????T P 391