
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 rulebased approaches which employ adhoc 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 twofold. 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].
Copyright © Analysis Situs 2020present  ^^^  contact us 