Jak sprawdzić, czy wielokąt jest monotoniczny względem linii?

Powszechnie wiadomo, że wielokąty monotoniczne odgrywają kluczową rolę w triangulacji wielokątów .

Definicja: Wielokąt w płaszczyźnie jest nazywany monotonicznym w odniesieniu do linii prostej L , jeśli każda linia prostopadła do L przecina P najwyżej dwa razy.$P$$L$$L$$P$

Biorąc pod uwagę linię i wielokąt P , czy istnieje skuteczny algorytm do określania, czy wielokąt P jest monotoniczny względem L ?$L$$P$$P$$L$

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

Spojlery ahoy:

IsMonotone (X [0..n-1], Y [0..n-1])
    local_mins ← 0
    dla i ← 0 do n-1
        jeśli (X [i] <X [i + 1 mod n]) i (X [i] <X [i-1 mod n])
            local_mins ← local_mins + 1
    return (local_mins = 1)

Jeśli obawiasz się, że wielokąt może mieć pionowe krawędzie, zamiast porównania użyj następującego podprogramu, X[i] < X[j]aby stale zerwać więzi:

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. Te dwa wierzchołki dzielą granicę wielokąta na dwie krzywe: łańcuch górny i łańcuch dolny.

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