An efficient line clipping algorithm against a convex polygon

Abstract

This work proposes a new line clipping algorithm against a convex polygon. Cyrus Beck algorithm is the most widely used algorithm for line clipping against a convex polygon. Many algorithms have been proposed by modifying Cyrus Beck algorithm considering special distributions of line segments on the plane. However Cyrus Beck algorithm is the fastest algorithm available in literature when line segments are normally distributed. The proposed algorithm uses a novel approach based on intersection d etection. There are three possible situations for a given line segment: (1) Line segment is completely inside. (2) Line segment is completely outside. (3) Line segment is intersecting the boundary of the convex polygon. Note that being end points of a line segment outside does not guarantee that the line segment is completely outside. This makes the clipping algorithms complicated. The Cyrus Beck algorithm computes all the intersection points and selects the actual end points of the clipped line segment. Th e proposed algorithm is capable of detecting completely inside line segments without doing any intersection calculations. Further the proposed algorithm avoids some of the intersection calculations when the line segment is intersecting the boundary of the convex polygon. Thus proposed algorithm is faster than the Cyrus Beck algorithm theoretically. According to the experimental results, the proposed algorithm is 1.012 times faster than Cyrus Beck algorithm when the convex polygon is a triangle. And the prop osed algorithm is 1.147 times faster than the Cyrus Beck algorithm when the convex polygon is an octagon. The performance of the proposed algorithm against Cyrus Beck is significant when the number of edges of the convex polygon is increased since then mor e intersection calculations can be avoided.