关键词: 多边形, 网格, 简便计算, 点在多边形内的检测

Abstract: Determining whether a point is inside a polygon is a fundamental computation in computational geometry and is required in many areas including computer graphics, geography information systems, and so on. For efficient implementation, many methods have been proposed to manage the polygon optimistically for reducing the polygon edges to be checked in answering a query point, among which the grid-based methods are always regarded the fastest ones, as the grid cell containing the query point can be determined at once due to the same size for grid cells, and the edges in a grid cell are always in a very small number. In our previous works, we have proposed a very fast grid-based method. It determines the inclusion property of the center points of grid cells in preprocess, and then produces the testing line from the query point to the center point of the grid cell that contains the query point, for answering the query point. With our endeavors, we have reduced the expected time complexities for preprocessing and answering a query point to be O(N)  and O( N ) respectively, where N is the number of the polygon edges. In this paper, we propose  novel measures for further speeding up point-in-polygon tests via a grid. In preprocessing, we determine the inclusion property of the corners instead of the center points of the grid cells. In answering a query point, we employ two line segments aligned with the two axes as the testing lines to connect the query point and one of its nearby corners, for reducing intersection computation. Experimental results show that we can have point-in-polygon tests sped up by twice.

Key words: polygon, grid, simple computation, point-in-polygon tests