UM  > 科技學院  > 電腦及資訊科學系
Line Clipping by Managing Polygon Edges in Convex Polylines
Wencheng Wang; Chunjuan Sun; Jing Li; Enhua Wu
2008
Source PublicationJournal of Graphics Tools
ISSN2165-347X
Volume13Issue:2
Abstract

Existing algorithms for clipping line segments against a concave polygon always need to compute all edges, resulting in a time complexity O(n) for computing intersection points, where n is the number of edges of the clipping polygon. This paper presents a new algorithm that first separates polygon edges into convex polylines and then clips lines against them, where a convex polyline is a sequence of edges that can form a convex polygon by themselves. As a result, the time complexity for computing intersection points is reduced, varying adaptively between O(log n) and O(n), and is lower than O(n) in most cases. To further improve clipping efficiency the new algorithm is combined with an axis-aligned BSP tree that is used to manage convex polylines for quickly finding convex polylines that might intersect the clipped lines. Examples show that the new algorithm can be several times faster than existing algorithms for line clipping.

DOIhttps://doi.org/10.1080/2151237X.2008.10129261
Language英语
Fulltext Access
Citation statistics
Document TypeJournal article
CollectionDEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Faculty of Science and Technology
AffiliationState Key Lab of Computer Science, Institute of Software, Chinese Academy of Sciences
Recommended Citation
GB/T 7714
Wencheng Wang,Chunjuan Sun,Jing Li,et al. Line Clipping by Managing Polygon Edges in Convex Polylines[J]. Journal of Graphics Tools,2008,13(2).
APA Wencheng Wang,Chunjuan Sun,Jing Li,&Enhua Wu.(2008).Line Clipping by Managing Polygon Edges in Convex Polylines.Journal of Graphics Tools,13(2).
MLA Wencheng Wang,et al."Line Clipping by Managing Polygon Edges in Convex Polylines".Journal of Graphics Tools 13.2(2008).
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Wencheng Wang]'s Articles
[Chunjuan Sun]'s Articles
[Jing Li]'s Articles
Baidu academic
Similar articles in Baidu academic
[Wencheng Wang]'s Articles
[Chunjuan Sun]'s Articles
[Jing Li]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Wencheng Wang]'s Articles
[Chunjuan Sun]'s Articles
[Jing Li]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.