Point-in-polygon tests by convex decomposition

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. [Copyright &y& Elsevier]