Robust and Optimized Algorithms for the Point-in-Polygon Inclusion Test without Pre-processing

Abstract

In this work we present new point inclusion algorithms for non-convex polygons. These algorithms do not perform any pre-processing or any type of decomposition nor features classification, which makes them especially suitable for deformable or moving polygons. The algorithms are more accurate and robust than others in the sense that they consider the inclusion of the point in the vertices and edges of the polygon, and deal with the special cases correctly. In order to perform this inclusion test efficiently, they use the sign of the barycentric coordinates of the test point with regard to the triangles formed by the edges and an origin that depends on the test point. This set of triangles, which is a special simplicial covering of the polygon, is constructed after a transformation of the polygon that simplifies the calculations involved in the inclusion test. Then, an appropriate ordering of the rejection tests allows us to optimize this method. Our algorithms have been tested for robustness and compared with ray-crossing methods, showing a significant improvement.