Geometric Search and Replace in Solid Model Editing
Chandrajit Bajaj, Kōkichi Sugihara · Purdue e-Pubs (Purdue University System) · 1992
AbstractWe present an efficient solution to a three dimensional geometric search and replace operationin the editing ofsolid models in both boundary representation or feature based solid modelingsystems. This combined operation, similar to the one dimensional string search and replace inword processors, proves very useful for detecting and modifying solid model descriptions withrepetitive features. Our geometric search and replace operation is £ased on the solution of thefollowing problem - Given ~ labeled embedded graph G = (V, E, C\') and a labeled patternp = (C, 'P), find all edges in E ofG that are consistent with (C, 'P). This problem is related tothe subgraph isomorphism problem, but is much easier because of the given embeddings of thegraph and the pattern. We present an efficient algorithm for this problem in which the totalnumber of label comparisons required for any 71 vertex embedded graph G is no more than 471,independent of the size of the pattern.