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 O (N) 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. It could be observed that the endpoints of completely outside line segments coincide after the pruning process. The algorithm was developed based on this observation. The proposed algorithm was compared against the four existing algorithms both theoretically and experimentally. The proposed algorithm is faster than Cyrus Beck algorithm and it is slower than ECB, Rappaport, and Skala algorithms. Keywords: Computer Graphics Programming, Line Clipping Algorithms, Computational Geometry, Convex Analysis, Time Complexity.References
Cohen D. 1969. Incremental methods for computer graphics. PhD Thesis, University of Harvard, Massachusetts.
Cyrus M, Beck J. 1978. Generalized two and three dimensional clipping. Computers & Graphics 3(1): 23-28.
Green SL. 1991. Advanced level pure mathematics. North Point, Hong Kong: University Tutorial Press.
Hearn D and Baker MP. 1998. Computer graphics: c version, 2nd Edition. Prentice Hall, Inc. Upper Saddle River. 224-237.
Kodituwakku SR, Wijeweera KR, Chamikara MAP. 2012. An efficient line clipping algorithm for 3D space. International Journal of Advanced Research in Computer Science and Software Engineering 2 (5): 96-101.
Kodituwakku SR, Wijeweera KR, Chamikara MAP. 2013. An efficient algorithm for line clipping in computer graphics programming. Ceylon Journal of Science (Physical Sciences) 17: 1-7.
Liang YD, Barsky BA. 1983. An analysis and algorithms for polygon clipping. CACM 26 (11): 868-876.
Liang YD, Barsky BA. 1984. A new concept and method for line clipping. ACM Transactions on Graphics 3 (1): 1-22.
Preparata PF, Shamos MI 1985. Computational geometry: an introduction. Springer-Verlag, New York.
Rappaport A. 1991. An efficient algorithm for line and polygon clipping. The Visual Computer 7 (1): 19-28.
Skala V. 1993. An efficient algorithm for line clipping by convex polygon. Computers & Graphics 17 (4): 417-421.
Skala V. 1994. O (lg N) line clipping algorithm in E2. Computers & Graphics 18 (4): 517-524.
Downloads
Published
Issue
Section
License
From Volume 7 (2016) onwards, all articles published in Ruhuna Journal of Science are Open Access articles published under the Creative Commons CC BY-NC 4.0 International License. This License permits use, distribution and reproduction in any medium, provided the original work is properly cited and is not used for commercial purposes.
Copyright on any research article published in RJS is retained by the respective author(s).
Authors who publish with this journal agree to the following terms:
a) Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC-BY-NC 4.0 International, that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
b) Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
c) Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
