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

É sabido que polígonos monótonos desempenham um papel crucial na triangulação de polígonos .

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.$P$$L$$L$$P$

Dada uma linha e um polígono , existe um algoritmo eficiente para determinar se um polígono é monótono em relação a ?$L$$P$$P$$L$

$x$$x$$O(n)$

Spoilers ahoy:

Isonotona (X [0..n-1], Y [0..n-1])
    local_mins ← 0
    para i ← 0 a n-1
        if (X [i] <X [i + 1 mod n]) e (X [i] <X [i-1 mod n])
            local_mins ← local_mins + 1
    return (local_mins = 1)

Se você estiver preocupado com o fato de seu polígono ter bordas verticais, use a seguinte sub-rotina no lugar da comparação X[i] < X[j]para romper de forma consistente:

IsLess(X, i, j):
    return ((X[i] < X[j]) or (X[i] = X[j] and i < j))

$L$$ax+by=c$IsLess

IsLess(X, Y, i, j):
    Di ← a·X[i] + b·Y[i]
    Dj ← a·X[j] + b·Y[j]
    return ((Dj < Dj) or (Di = Dj and i < j))

$x$

1. $x$$\mathcal{O}(n)$

2. Esses dois vértices dividem o limite do polígono em duas curvas: uma cadeia superior e outra inferior.

3. $x$$\mathcal{O}(n)$