In some applications, it is often necessary to clip lines against arbitrarily shaped polygons. Algorithms based on parametric line equations, such as the Liang-Barsky method and the earlier Cyrus-Beck approach, can be extended easily convex polygon windows. We do this by modifying the algorithm to include the parametric equations for the boundaries oi the clip region. Preliminary screening of line segments can be accomplished by processing lines against the coordinate extents of the clipping polygon. For concave polygon-clipping regions, we can still apply these parametric clipping procedures if we first split the concave polygon into a set of convex polygons.
Circles or other curved-boundary clipping regions are also possible, but less commonly used. Clipping algorithms far these areas are slower because intersection calculations involve nonlinear curve equations. At the first step, lines can be clipped against the bounding rectangle (coordinate extents! of the curved clip ping region. Lines that can be identified as completely outside the bounding rectangle are discarded. To identify inside lines, we can calculate the distance of line endpoints from the circle center. If the square of this distance for both endpoints of a line 1s less than or equal to the radius squared, we can save the entire line. The remaining lines arc then processed through the intersection calculations, which must solve simultaneous circle-line equations
Splitting Concave Polygons:
We can identify a concave polygon by calculating the cross products of successive edge vectors in order around the polygon perimeter. If the z component ofsome cross products is positive while others have a negative z component, we have a concave polygon. Otherwise, the polygon is convex. This is assuming that no series of three successive vertices are collinear, in which case the cross product of the two edge vectors for these vertices is zero. If all vertices are collinear, we have a degenerate polygon (a straight line). Figure 6-14 illustrates the edge vector cross-product method for identifying concave polygons.
A vector method for splitting a concave polygon in the xy plane is to calculate the edge-vector cross products in a counterclockwise order and to note the sign of the z component of the cross products. If any z component turns out to be negative (as in Fig. 6-141, the polygon is concave and we can split ~t along the line of the first edge vector in the crossproduct pair. The following example illustrates this method for splitting a concave polygon.
0 Comments