Como testar se um polígono é monótono em relação a uma linha arbitrária?

Definição : Um polígono no plano é chamado monotônico em relação a uma linha reta , se todas as linhas ortogonais a cruzarem no máximo duas vezes.L L $P$$L$$L$$P$

Dado um polígono , é possível determinar se existe alguma linha modo que o polígono seja monótono em relação a ? Se sim, como?L P $P$$L$$P$$L$

Antes, eu fazia uma pergunta relacionada (onde perguntava como determinar se um polígono é monótono em relação a uma linha específica), mas agora estou interessado no caso em que não é fornecido ou especificado com antecedência.$L$

É possível.

Considere seu polígono e considere os vértices "côncavos". Eles definem exatamente quais linhas cruzarão o polígono mais de duas vezes. Na figura a seguir, marquei os intervalos (em vermelho) dos ângulos proibidos. Se você juntá-las e vir um buraco no disco vermelho, existem ângulos autorizados $δ$ (em azul). O polígono é então monótono em relação a qualquer linha de inclinação $-1/\tan δ$ (em verde).

Agora o algoritmo.

Seja o ésimo vértice do polígono. Primeiro calcule o ângulo absoluto da aresta e o ângulo interno do vértice . Use a função disponível em todas as boas linguagens de programação.i α i ( v i v i + 1 ) β i v $v_i=(x_i, y_i)$$i$$α_i$$(v_iv_{i+1})$$β_i$$v_i$atan2

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

Inverta a ordem dos vértices se eles não estiverem no sentido anti-horário, ou seja, se não for negativo. ( : sentido anti-horário, : sentido horário).$s=\sum_i β_i-nπ$$s=-2π$$s=2π$

O seguinte é apenas para os ângulos internos maiores que ou seja, . Os vermelhos na minha foto. O objectivo é encontrar um ângulo que não é em módulo . Nomeadamente tal que para todos os tais que :$m$$π$$β_j>π$$δ$$∪_j[α_{j+1},α_j]$$π$$j$$β_j>π$

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

onde é aqui o valor normalizado de em . O segundo caso corresponde a um intervalo que vai além de (portanto, esse tempo deve estar "dentro").$α_j$$α_j$$[0,π)$$π$$δ$

Provavelmente existe uma maneira mais rápida de fazer isso, mas uma em é classificar os valores em e testar .$O(n^2)$$α_j\mbox{ mod }π$$γ_1,…γ_m$$δ∈\{\frac{γ_1}2,\frac{γ_1+γ_2}2,…,\frac{γ_{m-1}+γ_m}2,\frac{γ_m+π}2\}$

Se você encontrar algum então existe e é da inclinação . Caso contrário, não é monótono.$δ$$L$$-1/\tan δ$$P$