Project a vertical line through every vertex of our convex polygon $P$. Such a set of lines cuts the boundary of $P$ through two points (except for the lines through the leftmost and rightmost vertices). These lines also subdivide the plane into vertical slabs, which can be ordered left-to-right by a simple sorting step (that can even be implemented in $O(n)$ time if we use the ordering information around $P$). Given this ordered set of slabs, we can perform polygon inclusion by first determining the slab that contains our query point $q$ using a binary search. Then in constant additional time we can determine if $q$ is inside the part of $P$ that this slab cuts (there are at most two more line comparisons to do this).