论文部分内容阅读
本文提出了一个几何约束求解的新算法：偶图DM-分解法。这种方法首先将一个几何约束系统分解成一些具有某种偏序的较小的几何约束系统，然后按偏序关系给出一个构造序列，从而降低了求解的难度。这种方法还可判断过约束和欠约束的部分是否存在，并指出其存在的位置。当改变几何约束问题的参数时，利用偏序关系，相应的几何图形不必完全重新构造，我们只需构造其中的一部分，这大大加快了构造的速度。该算法的复杂度为O(｜V+｜+｜V-｜)3，其中｜V+｜和｜V-｜分别代表偶图中顶点和边的个数。