Clipping a Polygon

The basic routine of the package is a function that clips a polygon along a curve given by an implicit equation . The coordinates of a vertex are substituted into . Those vertices for which the result is positive are discarded and those for which the result of the substitution is negative or zero are kept. Figures 5 and 6 illustrate the process for a square clipped by the circle .

Figure 5. Circle and square.

Figure 6. Clipped square.

In Figure 5 a square polygon, shown in outline, is crossed by the circle, only a portion of which is shown. In Figure 6 the polygon has been clipped by discarding the vertex that lies outside the circle and adding vertices where the circle crosses the sides of the polygon. The clipped polygon lies entirely within or on the clipping circle.

The new vertices are computed as follows. Suppose that and are adjacent vertices on which the clipping function has different signs. The edge joining and may be parametrized as , and then is a real-valued function of the real variable , which has at least one root between 0 and 1. A root is located with FindRoot and the value substituted into to define the new vertex.

Since vertex coordinates are converted to approximate real numbers for this computation, problems with roundoff may occasionally arise. For this reason the test for retaining a vertex is not but where is small number internally referred to as Fuzz. The default value of Fuzz is but may be changed by the user.