16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – HdM Jun 4 '12 at 14:24
  • 4
    $\begingroup$ @HdM: Line L is not given as part of input. $\endgroup$ – Tsuyoshi Ito Jun 4 '12 at 16:12
16
$\begingroup$

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

Asteroids

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.

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

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.