用DM-分解求解几何约束问题

Geometric constraint solving with DM-decomposition of bigraph

提出了几何约束求解的新方法:偶图DM-分解法.这种方法首先将一个几何约束系统分解成一些具有偏序关系的几何约束子系统,然后按偏序关系给出一个构造序列,从而降低了求解的难度.这种方法还可以判断是否存在过约束和欠约束的部分,并指出其存在的位置.同时,在改变几何约束问题的参数时,相应的几何图形不必完全重新构造,只需构造其中的一部分,这大大加快了构造的速度.最后举例说明这种方法的可行性和有效性.

A new nlethod （DM-decomposition of bigraph）, for geometric： constraint solving is proposed. Firstly, the method can split a geometric constraint solving system into some smaller geometric constraint solving systems with some partial order. Secondly, a sequence is constructed according to the partial order, which reduces the difficulty of geometric constraint solving. Furthermore, the method can report the existence and location of over-constrainted or under-constrainted parts. Due to the partial order, it is not necessary to reconstruct the configuration corresponding to the problem of geometric constraint solving while the parameters are changed. We only need reconstruct a part of the configuration with lower partial order, thus increasing the speed of constructing. In order to show the feasibility and validity of the proposed method, some examples are studied.