Geometric Constraint Solving Based on Connectivity of Graph

Abstract

We propose a geometric constraint solving method based on connectivity analysis in graph theory, which can be used to decompose a structurally well-constrained problem in 2D into some smaller ones if possible. We also show how to merge two rigid bodies if they share two or three geometric primitives in a bi-connected or tri-connected graph respectively.

Keywords:

• Geometric constraint solving
• parametric CAD
• k-connected graph
• separating k-tuple
• D-tree decomposition