On the Reduction of the Spherical Point-in-Polygon Problem for Antipode-Excluding Spherical Polygons
This work provides a practical solution for a known bottleneck in computational geometry for spherical polygons that are BAE, which includes all polygons within an open hemisphere.
The authors prove that for spherical polygons whose boundary does not intersect its antipode (BAE polygons), the spherical point-in-polygon problem can be reduced to the planar point-in-polygon problem using winding numbers. They provide two reduction methods and demonstrate correct and efficient solutions for BAE polygons, including cases problematic for prior work.
Spherical polygons used in practice are nice, but the spherical point-in-polygon problem (SPiP) has long eluded solutions based on the winding number (wn). That a punctured sphere is simply connected is to blame. As a workaround, we prove that requiring the boundary of a spherical polygon to never intersect its antipode is sufficient to reduce its SPiP problem to the planar, point-in-polygon (PiP) problem, whose state-of-the-art solution uses wn and does not utilize known interior points (KIP). We refer to such spherical polygons as boundary antipode-excluding (BAE) and show that all spherical polygons fully contained within an open hemisphere is BAE. We document two successful reduction methods, one based on rotation and the other on shearing, and address a common concern. Both reduction algorithms, when combined with a wn-PiP algorithm, solve SPiP correctly and efficiently for BAE spherical polygons. The MATLAB code provided demonstrates scenarios that are problematic for previous work.