Find isomorphous faces

Searching for subgraph isomorphisms has been considered as a general way of a feature matching over the past decades. Although this method is known to possess high complexity, it has remarkable advantages over the rule-based approaches which employ ad-hoc shape interrogation procedures. The primary benefit of the subgraph isomorphism method is its ability to handle custom feature definitions (i.e., the user's features). It is a single common algorithm that operates with whatever feature descriptors represented with their AAG subgraphs. In practice, the availability of isomorphism searching algorithms allows users of a geometric modeling system to specify their features using a formal graph language or simply by interactive picking of feature faces.

The computational complexity of subgraph isomorphism is O(N^K), where N is the number of faces in the problem graph, and K is the number of feature faces to match. While such a complexity implies a computationally exhaustive implementation, the overall approach remains practical. An appropriate set of topological and geometric heuristics should be employed to reduce computation time. The purpose of heuristics is two-fold. First, by preliminary elimination of some nodes from the CAD model's AAG, one reduces the dimension of a problem, i.e., the employed adjacency matrix. Second, eliminating impossible bijections from the candidate isomorphism matrix reduces the number of checks, making the overall computation less intensive than in a general case.

You can find more information on this approach in our paper [Slyadnev et al, 2020].