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

Definition : Ein Polygon in der Ebene heißt monoton in Bezug auf eine Gerade , wenn jede zu orthogonale Linie höchstens zweimal schneidet . $P$ $L$ $L$ $P$

Ist es möglich, bei gegebenem Polygon zu bestimmen, ob irgendeine Linie existiert, so dass das Polygon in Bezug auf monoton ist ? Wenn ja, wie? $P$ $L$ $P$ $L$

Früher fragte ich eine ähnliche Frage (wo ich gefragt , wie zu bestimmen , ob ein Polygon monoton in Bezug auf eine bestimmte Linie ist), aber jetzt bin ich in dem Fall interessiert , wenn ist nicht gegeben oder im Voraus festgelegt. $L$

algorithms computational-geometry com
quelle

Warum nicht einfach das Koordinatensystem so drehen / verschieben, dass

L

$L$ zur

x

$x$ Achse wird und dann den alten Algorithmus erneut ausführen? Die Zusatzarbeit soll in

überschaubar sein

O (1)

$\mathcal{O}(1)$ .

HdM

@HdM: Zeile L wird nicht als Teil der Eingabe angegeben.

Tsuyoshi Ito

Es ist möglich.

Betrachten Sie Ihr Polygon und die "konkaven" Eckpunkte. Sie definieren genau, welche Linien das Polygon mehr als zweimal schneiden. In der folgenden Abbildung habe ich die Intervalle (in rot) der verbotenen Winkel markiert. Wenn Sie sie zusammenfügen und ein Loch in der roten Scheibe sehen, gibt es zulässige Winkel (in blau). Das Polygon ist dann in Bezug auf jede Steigungslinie eintönig (in Grün). $δ$ $-1/\tan δ$

Asteroiden

Nun der Algorithmus.

$v_i=(x_i, y_i)$ $i$ $α_i$ $(v_iv_{i+1})$ $β_i$ $v_i$ atan2

α_{i} = atan2 (y_{i + 1} - y_{i}, x_{i + 1} - x_{i})

$α_i=\mbox{atan2}(y_{i+1}-y_i,x_{i+1}-x_i)$

β_{i} = α_{i + 1} - α_{i} + {\begin{cases} 0 & if α_{i + 1} \geq α_{i} \\ 2 π & if α_{i + 1} < α_{i} \end{cases}

$β_i = α_{i+1}-α_i+ \left\{ \begin{array}{ll} 0 & \mbox{ if } α_{i+1} ≥ α_i \\ 2π & \mbox{ if } α_{i+1} < α_i \\ \end{array} \right.$

Kehre die Reihenfolge der Eckpunkte um, wenn sie nicht im Gegenuhrzeigersinn liegen, dh wenn $s=\sum_i β_i-nπ$ $s=-2π$ $s=2π$

Das Folgende gilt nur für die Innenwinkel, die größer als sind, . Die roten auf meinem Bild. Ziel ist es, einen Winkel zu finden , der nicht in modulo . Nämlich so, dass für alle so, dass : $m$ $π$ $β_j>π$ $δ$ $∪_j[α_{j+1},α_j]$ $π$ $j$ $β_j>π$

(δ < α_{j + 1} \lor α_{j} < δ) if α_{j + 1} < α_{j}

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

(α_{j} < δ < α_{j + 1}) if α_{j} < α_{j + 1}

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

wobei hier der normalisierte Wert von in . Der zweite Fall entspricht einem Intervall, das über hinausgeht (also muss diese Zeit "innen" sein). $α_j$ $α_j$ $[0,π)$ $π$ $δ$

Es gibt wahrscheinlich einen schnelleren Weg, dies zu tun, aber einer in besteht darin, die Werte in zu und auf zu testen. . $O(n^2)$ $α_j\mbox{ mod }π$ $γ_1,…γ_m$ $δ∈\{\frac{γ_1}2,\frac{γ_1+γ_2}2,…,\frac{γ_{m-1}+γ_m}2,\frac{γ_m+π}2\}$

Wenn Sie etwas dann existiert und hat eine Steigung von . Ansonsten ist nicht eintönig. $δ$ $L$ $-1/\tan δ$ $P$

jmad
quelle

Mit welcher Software haben Sie diese Illustration erstellt?

Jojman

@jojman Ich erinnere mich nicht, aber es musste GIMP sein. Ich kann mich an kein anderes Programm erinnern, das ich damals verwendet hätte.

Jmad

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

Antworten: