Geometric Constraint Solver Based On D-tree Decomposition Analysis

Geometric constraint solving is the core of computer-aided design technology. The graph theory based solving method is one of the most important methods of geometric constraint solving. The advantage of the method is that it has a faster solving speed and a lower time complexity, so that it is widely used. As the primary method of the graph theory based solving method, decomposition analysis is widely used at the same time there are two issues have been a focus of research:the high time complexity of the separation pair searching algorithm and the decomposition analysis algorithm could not give a guide to the follow algorithm. For these two issues, this thesis proposes a geometric solver based on D-tree decomposition analysis.For the first issue, this thesis propose a D-tree separation pair searching algorithm and a D-tree visual edge adding algorithm in order to reduce the time complexity. We introduce the degree of node to the geometric solving. Based on the study of the nature of decomposition analysis algorithms and reduction analysis algorithm, we propose and prove a series of new nature, then we propose a D-tree separate pair searching algorithm and a D-tree virtual edge adding algorithm. Based on the proposed algorithms, we propose a D-tree decomposition analysis algorithm. The new proposed algorithm reduce the time complexity of decomposition analysis from O(E+V) to O(V) in each iteration.For the second issue, According to the regularity result of the proposed algorithm, we propose D-tree decomposition result present and the sequence of solving exporting algorithm. The algorithm can give a sequence of solving, so that the followed algorithm can solve the geometric triangles in the order of the sequence of solving without judging, which avoid unnecessary loss of resources.Finally, we present D-tree geometric constraint solver which takes the D-tree decomposition analysis algorithm and the sequence of solving exporting algorithm as the major parts. The solver can decompose a geometric constraint graph, then give sequence of solving. Through the solving of two geometric constraint problems, it indicates that D-tree geometric constraint solver conceptually easier to understand and have a better solution efficiency which also can avoid the loss of unnecessary resources.