A New Projective Point in Convex Polygon Test with O(log N) Complexity*

This contribution describes a novel and fully projective algorithm for a point-in-convex polygon test with computational complexity of O(log N) in E<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>. The polygon vertices and tested points can be given in projective space, i.e., with the homogeneous coordinate w ≠ 0, without conversion to Euclidean space. It is independent of the polygon orientation. It uses vector-vector operations and is therefore aimed for implementation using SSE or AVX instructions. The algorithm is simple and robust, easy to implement.