Residential College | false |
Status | 已發表Published |
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 | 10.1016/j.cag.2005.03.001 |
URL | View the original |
Indexed By | SCIE |
Language | 英語English |
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 |
Scopus ID | 2-s2.0-18844433320 |
Fulltext Access | |
Citation statistics | |
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, 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. |
Files in This Item: | There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment