A novel and efficient approach for line segment clipping against a convex polygon

Abstract

This paper proposes a new line clipping algorithm against a convex polygon with 𝑂(𝑁) time complexity. The line segment is pruned against each extended edge of the polygon as the first step of the proposed algorithm. Then, the pruning process gives accurate outcomes for completely inside and partially inside line segments only. The algorithm was developed based on the observation that the endpoints of completely outside line segments coincide after the pruning process. Theoretical and experimental comparisons of the current algorithm against existing ones reveal that it is faster than the Cyrus Beck algorithm but is slower than ECB, Rappaport, and Skala algorithms.

Keywords

• computer graphics programming
• line clipping algorithms
• computational geometry
• convex analysis
• time complexity