Implementation

We implemented the algorithm in Common Lisp using exact (rational) arithmetic to express vertices and angles. We tested the algorithm on 1000 polygonal parts. For a few parts, we physically verified the resulting plans with a robot arm and modified gripper (see Figure 8). Geometric analysis and resulting plans for a 4-sided part are shown in Figures 9 and 10.

Click for a bigger JPEG image.
Figure 8: Robot with frictionless gripper.

Figure 9: Geometric analysis of the 4-sided part (4gon), showing diameter and squeeze functions. The horizontal bars show the interval at each stage in the algorithm.

Figure 10: Four traces of four-step squeeze plan for the 4-sided part.