The use of binary search when determining whether a point lies inside a given convex hull

Question

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)?

Answer 1

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.