Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems |
| |
Authors: | Simon EB Thierry Pascal Schreck Dominique Michelucci Christoph Fünfzig Jean-David Génevaux |
| |
Affiliation: | aLSIIT, UMR CNRS 7005, Université de Strasbourg, France;bLE21, UMR CNRS 5158, Université de Bourgogne, France |
| |
Abstract: | This paper describes new ways to tackle several important problems encountered in geometric constraint solving, in the context of CAD, and which are linked to the handling of under- and over-constrained systems. It presents a powerful decomposition algorithm of such systems.Our methods are based on the witness principle whose theoretical background is recalled in a first step. A method to generate a witness is then explained. We show that having a witness can be used to incrementally detect over-constrainedness and thus to compute a well-constrained boundary system. An algorithm is introduced to check if anchoring a given subset of the coordinates brings the number of solutions to a finite number.An algorithm to efficiently identify all maximal well-constrained parts of a geometric constraint system is described. This allows us to design a powerful algorithm of decomposition, called W-decomposition, which is able to identify all well-constrained subsystems: it manages to decompose systems which were not decomposable by classic combinatorial methods. |
| |
Keywords: | Geometric constraint solving Witness configuration Jacobian matrix _method=retrieve& _eid=1-s2 0-S0010448511001606& _mathId=si173 gif& _pii=S0010448511001606& _issn=00104485& _acct=C000054348& _version=1& _userid=3837164& md5=69c8c939383a3f43796ecf5275ecd89f')" style="cursor:pointer W-decomposition" target="_blank">">W-decomposition Under-constrainedness Over-constrainedness Well-constrainedness Transformation groups |
本文献已被 ScienceDirect 等数据库收录! |