I am interested in the repeated point in polygon problem, where one is given a polygon in a preprocessing phase and in the online phase, one is asked whether a point is in that polygon. The polygon is not necessarily simple. I am interested in the case where a polygon has many edges.
Let $n$ be the number of vertices of the polygon. I have an algorithm that performs the online phase in $O(\log n)$ time but the preprocessing phase requires $O(n^3)$ time and space in general, $O(n^2)$ time and space for simple polygons, and $O(n)$ time for star-shaped polygons.
Can we do better? Specifically, does anyone know lower or upper bounds, constructive or not, for the preprocessing phase given $O(\log n)$ query time?
I'm working in two dimensions, and the points have floating point coordinates (i.e., not integer coordinates).
My algorithm is similar to a standard algorithm and has similar performance characteristics. I discovered it independently so it differs in some immaterial ways but it's not original. It works as follows:
- Translate polygon into first quadrant. (This is to simplify later calculations but isn't strictly necessary.)
- Create a ray passing from the origin through every endpoint and intersection point of an edge. In each resulting cone no edge crosses another.
- For each cone, sort the edges crossing that cone by their distance from the origin.
- Apply the same translation to the query point as was applied to the polygon.
- Using binary search, find the cone containing the point, or if none, return false.
- Using binary search, find the number of edges in the point's cone for which the point and origin are on the same side. Return whether this number is odd.