Graphics Reference
In-Depth Information
Figure 3.11.
Weiler polygon clipping.
(a) Remove an intersection vertex from the entering list. If there is none,
then we are done.
(b) Follow the subject polygon vertices to the next intersection.
(c) Jump to the clip polygon vertex list.
(d) Follow the clip polygon vertices to the next intersection.
(e) Jump back to the subject polygon vertex list.
(f)
Repeat (b)-(e) until we are back to the starting point.
This process creates the polygons inside the clip polygon. To get those that
are outside, one repeats the same steps, except that one starts with a vertex
from the leaving list and the clip polygon vertex list is followed in the
reverse
direction. Finally, all holes are attached to their associated exterior contours.
3.3.2.1 Example.
Consider the polygons in Figure 3.11. The subject polygon ver-
tices are labeled
S
i
, those of the clip polygon are labeled
C
i
, and the intersections are
labeled
I
i
. The entering list consists of
I
2
,
I
4
,
I
6
, and
I
8
. The leaving list consists of
I
1
,
I
3
,
I
5
, and
I
7
. Starting Step 4(a) with the vertex
I
2
will generate the inside contour
IIISIIIISII
234 35678 612
.
Starting Step 4(a) with vertices
I
1
,
I
3
,
I
5
, and
I
7
will generate the outside contours
ISSII ISII ISII
,
,
,
and
ISII
.
17121 3243 5465
7587
3.3.3
Liang-Barsky Polygon Clipping
This section gives a brief outline of the Liang-Barsky polygon-clipping algorithm
([LiaB83]). The algorithm is claimed to be twice as fast as the Sutherland-Hodgman
clipping algorithm. This algorithm and the next one, the Maillot algorithm, base their
success on their ability to detect turning points efficiently. Before we get to the algo-
rithm, some comments on turning points are in order.
