Robust and Optimized Algorithms for the Point-in-Polygon Inclusion Test without Pre-processing
No Thumbnail Available
Date
2009
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and Blackwell Publishing Ltd
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.
Description
@article{10.1111:j.1467-8659.2009.01481.x,
journal = {Computer Graphics Forum},
title = {{Robust and Optimized Algorithms for the Point-in-Polygon Inclusion Test without Pre-processing}},
author = {Jimenez, J. J. and Feito, F. R. and Segura, R. J.},
year = {2009},
publisher = {The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {10.1111/j.1467-8659.2009.01481.x}
}