In an answer to the problem of determining whether or not a point lies inside a given convex hull, a thesis is mentioned, which says :For repeated queries with preprocessing allowed, we develop a special  method that relies on the convexity of the polygon. Recalling Theorem  3.5, the vertices of a convex polygon occur in angular order about any interior point. Find such a point O and consider the N rays from O  that pass through the vertices of P. (Figure 4.8.) These rays  partition the plane into N pie-shaped wedges. Each wedge is divided  into two pieces by a single edge of P. One of these pieces is wholly  interior to P, the other wholly exterior. Treating O as the origin of  polar coordinates, we may find the wedge in which z lies by a single  binary search, since the rays occur in angular order.How would one do the binary search (assuming the convex hull's vertices are given in counter-clockwise order)?
The use of binary search when determining whether a point lies inside a given convex hull
algorithms;binary search;convex hull
So, the situation is that you have the vertices $\mathbf{v}_i$ of a polygon that defines a convex hull and a point $\mathbf{O}$ inside this polygon. Furthermore you have the vectors connecting $\mathbf{O}$ with each vertex of the polygon and the vertices are ordered. To construct a binary search algorithm that determines in which wedge the point $\mathbf{z}$ lies you have to find out on which side of a line connecting $\mathbf{O}$ and a given vertex $\mathbf{v}$ the point is.Consider $\mathbf{r}_v$ to be the connecting vector from $\mathbf{O}$ to vertex $\mathbf{v}$. A normal vector $\mathbf{n}_v$ to $\mathbf{r}_v$ is simply given by$\mathbf{n}_v = \left(\matrix{-{\mathbf{r}_v}_y \\ {\mathbf{r}_v}_x}\right)$.Let us now project the vector $\mathbf{r}_z$ connecting $\mathbf{O}$ and $\mathbf{z}$ on the normalized $\mathbf{n}_v$:$d_z = \frac{\mathbf{n}_v \mathbf{r}_{z}}{|\mathbf{n}_v|}$.With the sign of $d_z$ we can now decide on which side of the line z lies.Just draw down the situation and this construction and this will become obvious. There may be a more elegant way to do this but this approach will work.You probably have to construct some more logic because the vertices actually are in a cyclic arrangement but that should not be too difficult.