A novel and efficient approach for line segment clipping against a convex polygon
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 partiall...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Ruhuna
2019-12-01
|
| Series: | Ruhuna Journal of Science |
| Subjects: | |
| Online Access: | https://rjs.ruh.ac.lk/index.php/rjs/article/view/152/262 |
| _version_ | 1819242998534242304 |
|---|---|
| author | K. R. Wijeweera S. R. Kodituwakku M. A. P. Chamikara |
| author_facet | K. R. Wijeweera S. R. Kodituwakku M. A. P. Chamikara |
| author_sort | K. R. Wijeweera |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-23T14:48:42Z |
| format | Article |
| id | doaj.art-6f621b77ec7b4a9195266806cea892c4 |
| institution | Directory Open Access Journal |
| issn | 2536-8400 |
| language | English |
| last_indexed | 2024-12-23T14:48:42Z |
| publishDate | 2019-12-01 |
| publisher | University of Ruhuna |
| record_format | Article |
| series | Ruhuna Journal of Science |
| spelling | doaj.art-6f621b77ec7b4a9195266806cea892c42022-12-21T17:43:02ZengUniversity of RuhunaRuhuna Journal of Science2536-84002019-12-0110216117310.4038/rjs.v10i2.81A novel and efficient approach for line segment clipping against a convex polygonK. R. Wijeweera0https://orcid.org/0000-0002-8933-1687S. R. Kodituwakku1M. A. P. Chamikara2Department of Computer Science, Faculty of Science, University of Ruhuna, Sri LankaDepartment of Statistics and Computer Science, Faculty of Science, University of Peradeniya, Sri Lanka3School of Computer Science and Information Technology, Royal Melbourne Institute of Technology, AustraliaThis 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.https://rjs.ruh.ac.lk/index.php/rjs/article/view/152/262computer graphics programmingline clipping algorithmscomputational geometryconvex analysistime complexity |
| spellingShingle | K. R. Wijeweera S. R. Kodituwakku M. A. P. Chamikara A novel and efficient approach for line segment clipping against a convex polygon Ruhuna Journal of Science computer graphics programming line clipping algorithms computational geometry convex analysis time complexity |
| title | A novel and efficient approach for line segment clipping against a convex polygon |
| title_full | A novel and efficient approach for line segment clipping against a convex polygon |
| title_fullStr | A novel and efficient approach for line segment clipping against a convex polygon |
| title_full_unstemmed | A novel and efficient approach for line segment clipping against a convex polygon |
| title_short | A novel and efficient approach for line segment clipping against a convex polygon |
| title_sort | novel and efficient approach for line segment clipping against a convex polygon |
| topic | computer graphics programming line clipping algorithms computational geometry convex analysis time complexity |
| url | https://rjs.ruh.ac.lk/index.php/rjs/article/view/152/262 |
| work_keys_str_mv | AT krwijeweera anovelandefficientapproachforlinesegmentclippingagainstaconvexpolygon AT srkodituwakku anovelandefficientapproachforlinesegmentclippingagainstaconvexpolygon AT mapchamikara anovelandefficientapproachforlinesegmentclippingagainstaconvexpolygon AT krwijeweera novelandefficientapproachforlinesegmentclippingagainstaconvexpolygon AT srkodituwakku novelandefficientapproachforlinesegmentclippingagainstaconvexpolygon AT mapchamikara novelandefficientapproachforlinesegmentclippingagainstaconvexpolygon |