Comment puis-je tester si un polygone est monotone par rapport à une ligne arbitraire?

Définition : Un polygone $P$ dans le plan est appelé monotone par rapport à une droite $L$ , si chaque ligne orthogonale à $L$ coupe $P$ au plus deux fois.

Étant donné un polygone $P$ , est-il possible de déterminer s'il existe une ligne $L$ telle que le polygone $P$ soit monotone par rapport à $L$ ? Si oui, comment?

Auparavant, j'ai posé une question connexe (où j'ai demandé comment déterminer si un polygone est monotone par rapport à une ligne particulière), mais maintenant je m'intéresse au cas où $L$ n'est pas donné ou spécifié à l'avance.

C'est possible.

Considérez votre polygone et considérez les sommets "concaves". Ils définissent exactement les lignes qui intersecteront le polygone plus de deux fois. Dans la figure suivante, j'ai marqué les intervalles (en rouge) des angles interdits. Si vous les assemblez et voyez un trou dans le disque rouge, alors il y a des angles autorisés (en bleu). Le polygone est alors monotone par rapport à toute ligne de pente - 1 / tan δ (en vert).$δ$$-1/\tan δ$

Maintenant l'algorithme.

Soit le i ème sommet du polygone. Calculez d'abord l'angle absolu α i du bord ( v i v i + 1 ) et l'angle intérieur β i du sommet v i . Utilisez la fonction disponible dans tous les bons langages de programmation.$v_i=(x_i, y_i)$$i$$α_i$$(v_iv_{i+1})$$β_i$$v_i$atan2

β i = α i + 1 - α i + { 0  si  α i + 1 ≥ α i 2 π  si  α i + 1 < α

$$α_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.$$

Inversez l'ordre des sommets s'ils ne sont pas dans le sens antihoraire, c'est-à-dire si n'est pas négatif. ( s = - 2 π : dans le sens antihoraire, s = 2 π : dans le sens horaire).$s=\sum_i β_i-nπ$$s=-2π$$s=2π$

Ce qui suit ne concerne que les angles intérieurs supérieurs à π, c'est-à-dire β j > π . Les rouges sur ma photo. Le but est de trouver un angle δ qui n'est pas dans ∪ j [ α j + 1 , α j ] modulo π . A savoir tel que pour tout j tel que β j > π :$m$$π$$β_j>π$$δ$$∪_j[α_{j+1},α_j]$$π$$j$$β_j>π$

( α j < δ < α j + 1 )  si  α j < α j +

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

où est ici la valeur normalisée de α j dans [ 0 , π ) . Le deuxième cas correspond à un intervalle qui dépasse π (donc cette fois δ doit être "à l'intérieur").$α_j$$α_j$$[0,π)$$π$$δ$

Il existe probablement un moyen plus rapide de le faire, mais l'un dans consiste à trier les valeurs α j  mod  π en γ 1 , … γ m et à tester pour δ ∈ { γ$O(n^2)$$α_j\mbox{ mod }π$$γ_1,…γ_m$$δ∈\{\frac{γ_1}2,\frac{γ_1+γ_2}2,…,\frac{γ_{m-1}+γ_m}2,\frac{γ_m+π}2\}$

$δ$$L$$-1/\tan δ$$P$