2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, it seems somewhat trivial in the end. I got confused because of an alternative algorithm that first determines the vertices with maximum and minimum y-coordinate, which apparently requires a variation of binary search explained here (instead of taking the middle, the point at index 1/3 and that at index 2/3 are used). $\endgroup$ – Bruno Vandekerkhove Aug 19 '17 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.