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 $α_jmbox{ 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.
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 $α_jmbox{ 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
