Constraint-Based Search and Replace gives users of graphical editors the ability to search for and modify complex spatial relationships within their documents. By doing so, It extends the power of graphical search and replace. These spatial relationships are expressed via constraints. For example, people can search for arbitrary angles, slopes, line lengths, distances between two lines, etc..., and then change these (or other) properties.

This technique allows people to define more complex replacement patterns - for example, to make all lines that are nearly tangent to a circle to be precisely tangent. It can also be used to define illustration beautification rules.

Constraint-based search and replace is incorporated into the MatchTool 2 utility for the Chimera graphical editor. The first panel on the left shows MatchTool 2 with a constraint-based search and replace pattern. These are magnified in the two panels below it. This is a pattern to search for all nearly 90 degree angles and make them exactly 90 degrees. The search pattern (blue panel) contains two constraints: that the two segments be connected (0.0" separation), and that the angle between them be 90 degrees. Note that the angle drawn is not truly 90 degrees. The tolerance is given by example. All connected line segments that are at least as close to 90 degrees as these two will match the search. The replace pattern (orange panel) shows the constraints that will be applied to all matches. The fourth (pink) panel shows the result of applying this constraint-based search and replace pattern to a scene. All the angles that are nearly 90 degrees become precisely 90 degrees. These constraints can be applied temporarily or applied to the objects for future editing, at the user's discretion.

The fifth (yellow) panel show two other transformations that we made with different constraint-based search and replace patterns. In the first, we round all right angles in a polygon, by splicing in an arc such that the arcs are tangent to both segments. In the second, we place a rounded rectangle around a text string with a given margin. Both of these transformations would have been impossible with regular graphical search and replace because we need to search and replace on relationships rather than individual graphical properties.

The final (blue-green) panel shows how constraint-based search and replace can be used for illustration beautification. Here the user has defined a set of constraint-based search and replace rules - all to be applied to the scene. This is done through a utility, called the RuleTool, which allows sets of search and replace patterns to be defined and to be applied together in sequence (or even as the illustration is drawn). We have defined and activated rules to connect nearly connected segments, make nearly 90 degree angles truly 90 degrees, make nearly horizontal segments horizontal, etc... When we apply these rules to the house labeled 'before' in the last panel to the left, it creates the neatened house labeled 'after'.

Although not shown here, constraint-based search can also be used as an iteration mechanism for graphical macros by example. As mentioned above, constraint-based search and replace can be used as a mechanism for adding constraints to a scene "by-example". Another technique that we developed for adding constraints "by-example" is called constraints from multiple snapshots.

After implementing graphical search and replace twice, first at Xerox PARC and then again at Columbia University, DJ Kurlander became aware of the need to write substitution rules for graphical relationships, not just graphical properties. He developed constraint-based search and replace as his solution to this problem . Constraint-based search and replace was first implemented in 1991 as part of the Matchtool 2 search and replace utility of DJ's Chimera graphical editor, and the work was initially published as a CHI '92 paper. Constraint-based search and replace also became the third chapter in DJ's doctoral dissertation, Graphical Editing by Example.

David Kurlander and Steven Feiner. Interactive Constraint-Based Search and Replace.  CHI ’92 Proceedings. pp. 609-618. May 1992. Monterey, CA.

David Kurlander. Graphical Editing by Example. Doctoral Dissertation, Computer Science Department, Columbia University. July 1993.

David Kurlander. Graphical Editing by Example: A Demonstration. SIGGRAPH Video Review, issue 89. 1993. Extended abstract in INTERCHI ‘93 Proceedings, p. 529. Click here for the video, or here for the extended abstract.

• Graphical Search and Replace
• Constraints from Multiple Snapshots
• Graphical Macros by Example
• Chimera: Graphical Editing by Example