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.
