面向欠约束几何系统的一种同伦求解方法

Solving Under-constrained Geometric System by Homotopy Method

针对几何约束系统的数值求解过程中 ,经常发生的数值不稳定性问题 ,构造了一种面向欠约束系统的同伦方法 ,并将其与现有的求解与分解方法有机地结合起来 ,提出了一种牛顿 -同伦混合方法 ,在牛顿迭代失败的位置自动调用欠约束同伦法 ,既提高了几何约束求解器的效率 ,同时又保证了求解的效率 .

When a geometric constraint system can not be fully decomposed, numerical solving methods are used, in which Newton-Raphson iteration method is the most popular. However, Newton-Raphson iteration method is not stable. To improve the stability of numerical geometric constraint solving, an homotopy method, named under constrained homotopy, is advanced in the paper especially for under-constrained geometric system. It can be combined with the decomposition of geometric constraint system and can be used together with other solving methods easily, and thus helps to the solving ability of geometric constraint solver. Some key problems of under constrained homotopy, such as construction of the homotopy function, homotopy path tracing and singularity analysis of homotopy path, are discussed in the paper. A pure homotopy method for under-constrained geometric systems is not very effective. To solve this problem, a hybrid Newton-Homotopy method is proposed. It makes use of both the fastness of Newton-Raphson iteration method and the stability of homotopy method and thus improves both the ability and the efficiency of the geometric constraint solver.