This paper proposes two algorithms for solving geometric constraint systems. The first algorithm is for constrained systems without loops and has linear complexity. The second algorithm can solve constraint systems wi...This paper proposes two algorithms for solving geometric constraint systems. The first algorithm is for constrained systems without loops and has linear complexity. The second algorithm can solve constraint systems with loops. The latter algorithm is of quadratic complexity and is complete for constraint problems about simple polygons. The key to it is to combine the idea of graph based methods for geometric constraint solving and geometric transformations coming from rule-based methods.展开更多
基金973" Project ( No. G19980306) by the National Natural Science Foundation of China under an outstanding youth grant ( Grant No. 69725002) .
文摘This paper proposes two algorithms for solving geometric constraint systems. The first algorithm is for constrained systems without loops and has linear complexity. The second algorithm can solve constraint systems with loops. The latter algorithm is of quadratic complexity and is complete for constraint problems about simple polygons. The key to it is to combine the idea of graph based methods for geometric constraint solving and geometric transformations coming from rule-based methods.