A new fully projective O(log N) point-in-convex polygon algorithm: a new strategy

A novel and fully projective algorithm for a point-in-convex polygon test with computational complexity of O(log N) in 2D is described in this contribution. The polygon vertices and tested points can be given in projective space without conversion to Euclidean space. The proposed algorithm is simple, robust, easy to implement, and invariant to the convex polygon orientation. It can be easily modified for use in Euclidean space and CPU implementation. Vector–vector operations are used, making it suitable for implementation using SSE, AVX, and FMA instructions. Due to the vector–vector formulation, additional speed-up can be expected due to better data caching.