UM  > 科技學院
Point-in-polygon tests by convex decomposition
Jing Li1,3; Wencheng Wang1; Enhua Wu1,2
Source PublicationComputers and Graphics (Pergamon)

The paper presents a new algorithm for point-in-polygon queries. By decomposing a polygon into a set of convex polygons and then constructing a BSP tree, the algorithm performs an inclusion query against the polygon in two steps. In the first step, it finds the convex polygon that is most likely to contain the query point through the BSP tree, and then in the second step, it tests whether the query point is in the convex polygon by employing advanced techniques for point-in-convex-polygon queries. The new algorithm is immune of singularity and has a performance of conducting a query by time demand in O(log n), and storage requirement in O(n). The time complexity of the preprocessing is O(n log n) for convex decomposition and BSP tree construction. The new algorithm has its performance in various aspects comparable to the state-of-art algorithms based on trapezoidation. Furthermore, as the number of convex polygons is always much fewer than the number of trapezoids in partitioning a polygon, and a high-quality search tree can always be constructed to manage the convex polygons, the new algorithm can run much faster than the trapezoidation-based algorithms, up to over double folds in maximum. 

KeywordBsp Trees Computational Geometry Convex Decomposition Point Containment Polygon
URLView the original
Indexed BySCI
WOS Research AreaComputer Science
WOS SubjectComputer Science, Software Engineering
WOS IDWOS:000250424300011
Fulltext Access
Citation statistics
Cited Times [WOS]:12   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionFaculty of Science and Technology
Corresponding AuthorJing Li
Affiliation1.State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
2.Department of Computer and Information Science, University of Macau, Macao, China
3.Graduate University of Chinese Academy of Sciences, Beijing, China
Recommended Citation
GB/T 7714
Jing Li,Wencheng Wang,Enhua Wu. Point-in-polygon tests by convex decomposition[J]. Computers and Graphics (Pergamon),2007,31(4):636-648.
APA Jing Li,Wencheng Wang,&Enhua Wu.(2007).Point-in-polygon tests by convex decomposition.Computers and Graphics (Pergamon),31(4),636-648.
MLA Jing Li,et al."Point-in-polygon tests by convex decomposition".Computers and Graphics (Pergamon) 31.4(2007):636-648.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Jing Li]'s Articles
[Wencheng Wang]'s Articles
[Enhua Wu]'s Articles
Baidu academic
Similar articles in Baidu academic
[Jing Li]'s Articles
[Wencheng Wang]'s Articles
[Enhua Wu]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Jing Li]'s Articles
[Wencheng Wang]'s Articles
[Enhua Wu]'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.