Well-constrained Completion and Decomposition for Under-constrained Geometric Constraint Pr.pdf

MM Research Preprints, 65–81 KLMM, AMSS, Academia Sinica Vol. 24, December 2005 Well-constrained Completion and Decomposition for Under-constrained Geometric Constraint Problems Xiao-Shan Gao KLMM, Institute of Systems Science, AMSS, Academia Sinica Gui-Fang Zhang School of Sciences, Beijing Forestry University, Beijing 100083, China Abstract. In this paper, we consider the optimal well-constrained completion problem, that is, for an under-constrained geometric constraint problem, add automatically new constraints in such a way that the new geometric constraint problem G is well-constrained and the set of equations need to be solved simultaneously in order to solve G has the smallest size. We propose a polynomial time algorithm which gives a partial solution to the above problem. Keywords. Geometric constraint solving, under-constrained 1. Introduction Geometric constraint solving (abbr. GCS) is one of the key techniques in intelligent and parametric CAD, which allows the user to make modifications to existing designs by changing parametric values. GCS methods may also be used in other fields like computer vision, molecular modelling, robotics, and feature-based design. There are four major approaches to GCS: the numerical approach, the symbolic approach, the rule-based approach, and the graph-based approach. Most existing GCS methods assumed that the problems are well-constrained. This paper will focus on using graph-based algorithms to solve under-constrained problems. The reason behind this research is that a natural way to draw a design figure is to do it incrementally, that is, to add geometric primitives and geometric constraints one by one. After a new primitive or a new constraint is added, it would be better for the constraint solving system to generate the design diagrams. But, before all the necessary constraints are added, the constraint problem is under-constrained. Joan-Arinyo et al proposed that the main problem about under-constrained problems are we