UM  > 科技學院
2D point-in-polygon test by classifying edges into layers
WenchengWang1; JingLi1; Enhua Wu1
Source PublicationComputers and Graphics (Pergamon)

The 2D point-in-polygon test is a fundamental problem in geometry, and of importance in various applications in computer graphics and other areas. In taking advantage of the basic idea of the polygon scan conversion algorithm, a novel method for the point-in-polygon test is proposed in this paper, capable of handling simple polygons in arbitrary shapes, possibly with holes. In the preprocess of the method, the edges of the polygon are classified into layers according to the occlusion relations between the edges viewed orthogonally in a direction, called the test direction, which guarantees that the edges of a layer can be occluded by only the edges of its preceding layers. At the same time, the edges at each layer are queued up respectively along the direction vertical to the test direction because there is no occlusion relation between the edges of the same layer. As a result, based on the layers, the calculation of the segments by the line through the tested point to intersect the polygon along the test direction, and then the inclusion test of the point against the segments could be feasibly made. The method has a low storage requirement in O(n), here, n is the number of the edges of the polygon. The time complexity of its preprocess ranges from O(n) to O(n), depending on the polygon shape and the test direction. And its inclusion test has a time complexity between O(log(n)) and O(n), but less than O((log(n))) in most cases, depending on the construction of the layers. In the case of convex polygons and monotone polygons, the time complexity for the preprocess and the inclusion test could be O(n) and O(log(n)), respectively. On the other hand, the method is also easy to integrate with a variety of existing methods such as ray crossing methods and grid-based methods for improving the inclusion test further. Experimental results show that the method is robust and efficient in computation. 

KeywordComputational Geometry Layered Edges Point Containment Polygon
URLView the original
Indexed BySCI
WOS Research AreaComputer Science
WOS SubjectComputer Science, Software Engineering
WOS IDWOS:000230160300011
Fulltext Access
Citation statistics
Cited Times [WOS]:15   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionFaculty of Science and Technology
Corresponding AuthorWenchengWang
Affiliation1.Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080, China
2.Graduate School of Chinese Academy of Sciences, Beijing 100039, China
3.Faculty of Science and Technology, University of Macau, Macao, China
Recommended Citation
GB/T 7714
WenchengWang,JingLi,Enhua Wu. 2D point-in-polygon test by classifying edges into layers[J]. Computers and Graphics (Pergamon),2005,29(3):427-439.
APA WenchengWang,JingLi,&Enhua Wu.(2005).2D point-in-polygon test by classifying edges into layers.Computers and Graphics (Pergamon),29(3),427-439.
MLA WenchengWang,et al."2D point-in-polygon test by classifying edges into layers".Computers and Graphics (Pergamon) 29.3(2005):427-439.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[WenchengWang]'s Articles
[JingLi]'s Articles
[Enhua Wu]'s Articles
Baidu academic
Similar articles in Baidu academic
[WenchengWang]'s Articles
[JingLi]'s Articles
[Enhua Wu]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[WenchengWang]'s Articles
[JingLi]'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.