کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
439565 | 690803 | 2011 | 16 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems](/preview/png/439565.png)
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 WW-decomposition, which is able to identify all well-constrained subsystems: it manages to decompose systems which were not decomposable by classic combinatorial methods.
► A powerful and easy to implement method to decompose constraint systems is presented.
► The decomposition algorithm is not sensitive to the connectivity of the constraint graph.
► A robust way to test rigidity and to identify maximal well-constrained systems is presented.
► All algorithms are incremental and can thus use idle time.
Journal: Computer-Aided Design - Volume 43, Issue 10, October 2011, Pages 1234–1249