UM  > 科技學院
 2D point-in-polygon test by classifying edges into layers WenchengWang1; JingLi1; Enhua Wu1 2005-06-01 Source Publication Computers and Graphics (Pergamon) ISSN 0097-8493 Volume 29Issue:3Pages:427-439 Abstract 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. Keyword Computational Geometry Layered Edges Point Containment Polygon DOI https://doi.org/10.1016/j.cag.2005.03.001 URL View the original Indexed By SCI Language 英语 WOS Research Area Computer Science WOS Subject Computer Science, Software Engineering WOS ID WOS:000230160300011 Publisher PERGAMON-ELSEVIER SCIENCE LTD, THE BOULEVARD, LANGFORD LANE, KIDLINGTON, OXFORD OX5 1GB, ENGLAND Fulltext Access Citation statistics Cited Times [WOS]:15   [WOS Record]     [Related Records in WOS] Document Type Journal article Collection Faculty of Science and Technology Corresponding Author WenchengWang Affiliation 1.Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080, China2.Graduate School of Chinese Academy of Sciences, Beijing 100039, China3.Faculty of Science and Technology, University of Macau, Macao, China Recommended CitationGB/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 Bookmark 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