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

Simple item page
dc.contributor.authorJimenez, J. J.en_US
dc.contributor.authorFeito, F. R.en_US
dc.contributor.authorSegura, R. J.en_US
dc.date.accessioned2015-02-23T09:30:11Z
dc.date.available2015-02-23T09:30:11Z
dc.date.issued2009en_US
dc.description.abstractIn 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.en_US
dc.description.number8en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume28en_US
dc.identifier.doi10.1111/j.1467-8659.2009.01481.xen_US
dc.identifier.issn1467-8659en_US
dc.identifier.pages2264-2274en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2009.01481.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltden_US
dc.titleRobust and Optimized Algorithms for the Point-in-Polygon Inclusion Test without Pre-processingen_US
Files
Collections
28-Issue 8