Line clipping against a polygon based on convex decomposition

Residential College	false
Status	已發表Published
	Line clipping against a polygon based on convex decomposition
	Li J.1; Wang W.1; Wu E.1
	2007-04-01
Source Publication	Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics
ISSN	10039775
Volume	19 Issue:4 Pages:425-429
Abstract	A novel line clipping algorithm against a general polygon is proposed in the paper. By the approach, the polygon is first decomposed into a set of convex polygons without adding new points and then these convex polygons are organized in a binary space partition tree, as a search tree. In the clipping procedure, the search tree is used to find the candidate convex polygons that intersect the clipped line segment and then an efficient line clipping algorithm against a convex polygon is applied to each such candidate. The algorithm can adaptively decrease the time complexity for line clipping, ranging from O(log n) to 0(n), but less than (n) in most cases, where n is the number of the edges of the polygon. Although a preprocess is required, in many applications (e.g. clipping a polygon against another polygon), the total time consumed by the new method, including the time for preprocess and clipping calculation, is much less than that by the existing algorithms without preprocess.
Keyword	Acceleration Binary space partition tree Convex decomposition Line clipping Polygonal window
URL	View the original
Language	英語English
Fulltext Access	View Full-Text via Scopus
Document Type	Journal article
Collection	University of Macau
Affiliation	1.Institute of Software Chinese Academy of Sciences 2.Universidade de Macau 3.University of Chinese Academy of Sciences
Recommended Citation GB/T 7714	Li J.,Wang W.,Wu E.. Line clipping against a polygon based on convex decomposition[J]. Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics, 2007, 19(4), 425-429.
APA	Li J.., Wang W.., & Wu E. (2007). Line clipping against a polygon based on convex decomposition. Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics, 19(4), 425-429.
MLA	Li J.,et al."Line clipping against a polygon based on convex decomposition".Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics 19.4(2007):425-429.

Files in This Item:
There are no files associated with this item.

If you have any objections to this item, please fill out the form below and the administrator will contact you as soon as possible.
Content:
Email：	*
Affiliation No.
Verification Code:	Refresh

Any comments and suggestions are welcomed.
Title:	*
Content:
Email：	*
Verification Code:	Refresh