Solution Modification

While the heuristics employed in solution selection often select the user's intended solution, there are times when the solution displayed does not meet the user's expectations. Conceptually, all possible solutions of a constraint problem can be arranged in a tree whose leaves are the different solutions, and whose internal nodes correspond to stages in the placement of elements or clusters. The different branches from a particular node are the different choices for placing the element or cluster. The tree has depth proportional to the number of elements and clusters. Browsing through all possible solutions would be exponential in the number of elements and would be inappropriate, but stepping from one solution to another one is proportional to the tree depth only.

We have added to our solver an incremental mode in which the user can browse through the construction tree and be visually informed which elements have been placed at a particular moment. With a button, the user steps forward or backwards in the construction sequence, thus traversing the tree path backwards, towards the root, or forward, towards a leaf. At each level, the geometric element(s) placed at that point are highlighted, and a panel displays the number of possible positions. The user can then select which one of the possible choices should be used.

The two control elements for solution selection are the arrow keys along the top of the display. The leftmost one controls the particular solution, while the one to its right controls the level. Each level corresponds to one construction step, and the geometries involved in that step are highlighted in purple. The user can step through the levels until the geometries involved in the aspect of the sketch to be changed are highlighted. At any given level there may be from one to eight different solutions. By choosing a new solution and regenerating, a new configuration will be displayed. Note, however, that some solutions may represent repeated roots and the display will be the same as before regeneration. The user may alter the solution choice one level at a time. That is, Regenerate must be called after choosing a new solution at a given level before trying to pick a different solution at another level. The sequence of solutions generated throughout this interactive solution selection process is stored. The rightmost arrow keys allow the user to browse through all solutions generated so far. A final assistant in the solution selection process is the Complement button in the Edit menu. This handles the special case of swapping an arc with its complement.

Example

In this example we demonstrate how to look for and select an alternate solution to a geometric constraint solver. If you are running the profile editor from the tutorial, read the file www1.src from the directory new_parser/new_tests/tests and press Regenerate. The figures you obtain by following the steps described below will match the pictures displayed along with the text.

The profile which is obtained based on the initial sketch and the input constraints is shown here:

Note that the current level is 17 and there is exactly one placement for the two purple elements.

If we step to level 16 using the Level arrow buttons, we find there are two solutions, and that solution 2 is the one which was used in the displayed configuration. The construction at level 16 involves the three geometries highlighted in purple, specifically the two arcs below and the one segment completely above the horizontal line. Using the Solution arrow keys, change the level 16 solution to solution 1 and click Regenerate. This results in the following solution:

Note that there are only two purple elements in new picture. The length of the line segment has become zero in this solution.

Another different solution can be found at level 14, solution 2.

In this solution, the line segment which had length zero in the previous solution has regained positive length, but the tangency types between the arcs adjacent to that segment have changed in the transition from zero to positive length. Also, the tangency type between the two purple entities has changed from the previous solution.

There are many other solutions to this example. If you are using the profile editor interactively, you are encouraged to explore the various levels and solutions to find as many different solutions as possible.