Research On Polygon Clipping Algorithm With Respect To Circle And Ellipse

Clipping is one of the fundamental techniques in computer graphics. There are many types of clipping among which 2D polygon clipping is currently a primary research topic. Many classical algorithms have been developed for polygon clipping against rectangle (or polygon), however the clipping algorithms of polygon against circle or ellipse are computationally inefficient due to solution of quadratic equations or computation of the square root.In the thesis polygon clipping against circle and ellipse is studied and efficient and effective algorithms are presented. Emphasis is focused on clipping against circle which avoids completely solution of quadratic equations or computation of the square root.Polygons are firstly identified as being completely visible, invisible, or partially invisible edges of which should be clipped against circle. The main techniques involved are as follows, the relationship between circle and the polygon edges are determined via region encoding and method of square distance; the intersection points between edges and circle are computed by using middle point segmentation algorithms; the boundary of edge segments is achieved through adjacent relation between intersection points and vertexes of polygon; finally the clipping results are obtained via sorting and pairing of intersection points.A circle is a special category of ellipse that has some specific properties. It is therefore impossible to extend straightforwardly the algorithms of clipping against circle to those against ellipse. By observing what is not appropriate for clipping algorithms against ellipse, we modify the algorithms relating to circle window to get effective algorithms of polygon clipping against ellipse.