6533b854fe1ef96bd12af4c2
RESEARCH PRODUCT
Using the witness method to detect rigid subsystems of geometric constraints in CAD
Simon E. B. ThierryPascal SchreckChristoph FünfzigJean-david GénevauxDominique Micheluccisubject
Mathematical optimization[ INFO.INFO-MO ] Computer Science [cs]/Modeling and Simulationrigidity theorygeometric constraints solvingComputation020207 software engineeringCADJacobian matrix02 engineering and technologyW-decompositionwitness configuration16. Peace & justiceWitness[INFO.INFO-MO]Computer Science [cs]/Modeling and Simulationsymbols.namesakeJacobian matrix and determinant0202 electrical engineering electronic engineering information engineeringsymbols020201 artificial intelligence & image processingRigidity theoryAlgorithmAlgorithmsMathematicsdescription
International audience; This paper deals with the resolution of geometric constraint systems encountered in CAD-CAM. The main results are that the witness method can be used to detect that a constraint system is over-constrained and that the computation of the maximal rigid subsystems of a system leads to a powerful decomposition method. In a first step, we recall the theoretical framework of the witness method in geometric constraint solving and extend this method to generate a witness. We show then that it can be used to incrementally detect over-constrainedness. We give an algorithm to efficiently identify all maximal rigid parts of a geometric constraint system. We introduce the algorithm of W-decomposition to identify all rigid subsystems: it manages to decompose systems which were not decomposable by classical combinatorial methods.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2010-09-01 |