Wie teste ich, ob ein Polygon in Bezug auf eine Linie monoton ist?

Es ist bekannt, dass monotone Polygone eine entscheidende Rolle bei der Polygon-Triangulation spielen .

Definition: Ein Polygon in der Ebene wird in Bezug auf eine gerade Linie L als monoton bezeichnet , wenn jede zu L orthogonale Linie P höchstens zweimal schneidet .$P$$L$$L$$P$

Gibt es bei einer gegebenen Linie und einem Polygon P einen effizienten Algorithmus, um zu bestimmen, ob ein Polygon P in Bezug auf L monoton ist ?$L$$P$$P$$L$

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

Spoiler ahoi:

IsMonotone (X [0..n-1], Y [0..n-1])
    local_mins ← 0
    für i ← 0 bis n-1
        wenn (X [i] <X [i + 1 mod n]) und (X [i] <X [i-1 mod n])
            local_mins ← local_mins + 1
    return (local_mins = 1)

Wenn Sie befürchten, dass Ihr Polygon vertikale Kanten haben könnte, verwenden Sie anstelle des Vergleichs die folgende Unterroutine X[i] < X[j], um Bindungen dauerhaft zu lösen:

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. Diese beiden Eckpunkte teilen die Grenze des Polygons in zwei Kurven: eine obere Kette und eine untere Kette.

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