Weiler-Atherton polygon clipping algorithm
This is a common polygon clipping algorithm, can also crop cutting convex polygon concave multilateral.
During the execution of the algorithm is described by the following figure
DCBA the crop window dcba polygon you want to crop. Polygons and the intersection of the crop window before algorithm execution were added to the sequence of vertices. That the figure of 123,456.
The polygon sequence: a, 6,5, d, 4,3, c, 2, b, 1
Clipping window sequence: A, 5,4, D, C, 1, B, 2,3,6
Vertices of the polygon from the polygon vertices a counterclockwise traversal. Reach the point of intersection of the boundary polygon clipping 6, the line segment from the outside of the cropped area inside the cutting area
(6 entering the intersection intersection), continue to traverse the polygon sequence until it finds the first "out" from the boundary point or a point has been traversed, shown in the figure at the intersection of 5 (intersection of one exiting intersection);
Segment from the cutting area out, then counterclockwise through the crop window sequence current vertex (in this case the intersection 5) to reach the intersection of 4 segments d4 points to the interior of the polygon, the intersection is an intersection entering;
Converted to a polygon sequence to continue the walk to the intersection point 3, the intersection is an exiting The intersection;
Converted to crop window sequence counter-clockwise traversal has visited, the sequence of vertices 6543, that is, a polygon to draw to the intersection point 6;
Then return to the last exiting The intersection, vertex in the polygon sequence traversal, find a entering INTERSECTION, point 2, and then follow the above process a vertex sequence 2b1B, the polygon point have access to the end of the algorithm ;
The whole algorithm is to calculate the sequence of vertices of the polygon clipping window, then the intersection is an entering intersection or exiting intersection traverse in a different sequence of vertices, until all points are finished access
Input given the polygon sequence and the sequence of the crop window, first to a pretreatment their intersection by sequentially inserted into each sequence, a more direct way, can traversed counterclockwise these two sequences, each taking two each edge points form a segment with another sequence comparison to calculate the intersection point, draw a set of points to be inserted, and then follow the concentration of each point of the distance to the starting point of the line segment inserted sequence, from the starting point near the first insert ;
"Computer Graphics" Hearn