Testing Polygon for Monotonicity with respect to any arbitrary line

Problem Detail: 

Definition: monotone polygon - 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.

I am wondering if and how it is possible to test whether there is a line $L$ for a given polygon $P$ so that $P$ is monotone with respect to $L$.

Previously I've asked for help with the similar problem when $L$ is the x-axis, and now I am interested in the case when $L$ is not given in advance.

Asked By : com

Answered By : jmad

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2197