How do I test if a polygon is monotone with respect to an arbitrary line?

Definition: A polygon $P$ in the plane is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $P$ at most twice.

Given a polygon $P$, is it possible to determine if there exists any line $L$ such that the polygon $P$ is monotone with respect to $L$? If yes, how?

Previously, I asked a related question (where I asked how to determine if a polygon is monotone with respect to a particular line), but now I am interested in the case when $L$ is not given or specified in advance.

• Why not just rotate/shift the coordinate system such that $L$ becomes the $x$-axis and then run the old algorithm again? The additional work should be manageable in $\mathcal{O}(1)$. – HdM Jun 4 '12 at 14:24
• @HdM: Line L is not given as part of input. – Tsuyoshi Ito Jun 4 '12 at 16:12

It is possible.

Consider you polygon and consider the "concave" vertices. They define exactly which lines will intersect the polygon more than twice. In the following figure I marked the intervals (in red) of forbidden angles. If you put them together and see a hole in the red disk, then there are authorized angles $δ$ (in blue). The polygon is then monotonous with respect to any line of slope $-1/\tan δ$ (in green). Now the algorithm.

Let $v_i=(x_i, y_i)$ be the $i$th vertex of the polygon. First compute the absolute angle $α_i$ of the edge $(v_iv_{i+1})$ and the inner angle $β_i$ of the vertex $v_i$. Use the function atan2 available in all good programming languages.

$$α_i=\mbox{atan2}(y_{i+1}-y_i,x_{i+1}-x_i)$$ $$β_i = α_{i+1}-α_i+ \left\{ \begin{array}{ll} 0 & \mbox{ if } α_{i+1} ≥ α_i \\ 2π & \mbox{ if } α_{i+1} < α_i \\ \end{array} \right.$$

Reverse the order of the vertices if they are not in the counterclockwise order, i.e. if $s=\sum_i β_i-nπ$ is not negative. ($s=-2π$: counterclockwise, $s=2π$: clockwise).

The following is only for the $m$ inner angles bigger than $π$ that is, $β_j>π$. The red ones in my pic. The goal is to find an angle $δ$ that is not in $∪_j[α_{j+1},α_j]$ modulo $π$. Namely such that for all $j$ such that $β_j>π$:

$$(δ<α_{j+1} ∨ α_j<δ) \mbox{ if } α_{j+1}<α_j$$ $$(α_j<δ<α_{j+1}) \mbox{ if } α_j<α_{j+1}$$

where $α_j$ is here the normalized value of $α_j$ in $[0,π)$. The second case correspond to an interval that goes beyond $π$ (so this time $δ$ must be "inside").

There is probably a faster way to do this but one in $O(n^2)$ is to sort the values $α_j\mbox{ mod }π$ into $γ_1,…γ_m$ and to test for $δ∈\{\frac{γ_1}2,\frac{γ_1+γ_2}2,…,\frac{γ_{m-1}+γ_m}2,\frac{γ_m+π}2\}$.

If you have find some $δ$ then $L$ exists and is of slope $-1/\tan δ$. Otherwise $P$ is not monotonous.

• What software did you use to make that illustration? – jojman Mar 7 '18 at 19:56
• @jojman I don't remember but it had to be GIMP, I can't remember any other program I would have used back then. – jmad Mar 8 '18 at 13:48