Umlaufsinn eines Polygons

12.04.2007, 10:26

pkautz

Auf diesen Beitrag antworten »

Umlaufsinn eines Polygons

Hallo zusammen,

ich habe folgendes Problem: gegeben sind eine Anzahl von Punkten und Geraden (beschrieben durch jeweils zwei Punkte); gesucht wird ein Polygon, dessen Umlaufsinn dem Uhrzeigersinn entgegengesetzt ist (also positiven Umlaufsinn besitzt). Irgendwie stehe ich auf dem Schlauch verwirrt

verwirrt

.

Als einfaches Beispiel:

Punkte:
$\begin{eqnarray*} p_0 (0; 0)\\p_1 (1; 0)\\p_2 (1; 1)\\p_3 (0; 1) \end{eqnarray*}$

Kanten:
$\begin{eqnarray*} k_0 (p_0, p_1)\\k_1 (p_0, p_3)\\k_2 (p_3, p_2)\\k_3 (p_2, p_1) \end{eqnarray*}$

Nun habe ich gedacht ich könnte für die Kanten Vektoren nehmen:
$\begin{eqnarray*} v_0 = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}; v_1 = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}; v_2 = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}; v_3 = \begin{pmatrix} 0 \\ -1 \\ 0 \end{pmatrix} \end{eqnarray*}$
und mit dem Kreuzprodukt von zwei Vektoren die Richtung bestimmen, aber irgendwie stelle ich mich zu blöde an. Reichen meine Ausgangsdaten überhaupt aus? Woher weiß man z.B. von welchen Vektorenpaar man das Kreuzprodukt berechnen muss?

Gruß
Patrick

12.04.2007, 10:50

integralschokolade

Auf diesen Beitrag antworten »

Du musst das Kreuzprodukt zwischen zwei benachbarten Vektoren
(z.B. zwischen v1 und v2) bilden. Das Kreuzprodukt hat negativen Wert, wenn die beiden Vektoren einen Umlaufsinn entgegen des
Uhrzeigersinns haben, einen positiven - wenn Umlaufsinn im Uhrzeigersinn. Wähle die Abfolge der Vektoren immer so, dass das
Kreuzprodukt einen negativen Wert hat! Sollte bei einem Kreuzprodukt
ein positiver Wert rauskommen, vertauschst du die Vektoren.
Beispiel: v_a x v_b = positiv -> v_b x v_a = negativ -> Abfolge: v_b
und dann kommt v_a

12.04.2007, 11:12

pkautz

Auf diesen Beitrag antworten »

Das verstehe ich ja. Wo ich aber ein Problem sehe, ist angenommen ich betrachte $\begin{eqnarray*} v_0 \end{eqnarray*}$ und $\begin{eqnarray*} v_3 \end{eqnarray*}$ , auf Grund der Kanten weiß ich, dass die beiden den Punkt $\begin{eqnarray*} p_1 \end{eqnarray*}$ besitzen (dummerweise beide als Endpunkt). Demnach zeigen beiden Vektoren auf den gleichen Punkt und sind "entgegengesetzt", laut Kreuzprodukt erhalte ich, einen negativen Umlaufsinn. Also tausche ich die Vektoren => Abfolge: erst $\begin{eqnarray*} v_3 \end{eqnarray*}$ und dann $\begin{eqnarray*} v_0 \end{eqnarray*}$ . Wenn ich mir das Ganze mal skizziere, dann ist die Richtung jetzt aber falsch herum, sprich mit dem Uhrzeiger.
Also eigentlich muss ich irgendwie mitbekommen, dass die Vektoren auf den gleichen Punkt zeigen, herausfinden welcher Vektor "falsch" herum ist und ihn umdrehen (Anfangs- und Endpunkt wechseln). Ist das verständlich?

Gruß
Patrick

12.04.2007, 11:31

riwe

Auf diesen Beitrag antworten »

eine möglichkeit verwirrt

verwirrt

Punkte:
$\begin{eqnarray*} p_0 (0; 0)\\p_1 (1; 0)\\p_2 (1; 1)\\p_3 (0; 1) \end{eqnarray*}$

wähle $\begin{eqnarray*} P_0 \end{eqnarray*}$ als "ausgangspunkt" und die richtung der positiven x-achse als "ausgangsvektor".

$\begin{eqnarray*} \vec{v}_0=\begin{pmatrix} 1 \\0 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \vec{v}_1=\begin{pmatrix} 1 \\0 \end{pmatrix} \quad{ }\vec{v}_2=\begin{pmatrix} 1 \\1 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \vec{v}_3=\begin{pmatrix} 0\\1 \end{pmatrix} \quad{ }\text{...} \end{eqnarray*}$
mit dem skalarprodukt bestimmst du nun die winkel "zwischen den einzelnen punkten":

$\begin{eqnarray*} cos\alpha_1=1\to \alpha_1=0\quad{ }\alpha_2=45°\quad{ }\alpha_3=90° \quad{ }\text{...} \end{eqnarray*}$

und jetzt sortierst du die punkte nach der größe der winkel:

$\begin{eqnarray*} P_0, P_1, P_2, P_3....\to P_0 \end{eqnarray*}$

verwirrt

verwirrt

werner

12.04.2007, 11:50

pkautz

Auf diesen Beitrag antworten »

Wenn ich das richtig verstehe, wird von Punkt $\begin{eqnarray*} p_0 \end{eqnarray*}$ ausgehend ein Strahlenfächer erstellt und dann die Punkte nach aufsteigendem "Anstieg" sortiert. Das funktioniert leider für komplexere Polygone nicht.

Gruß
Patrick

12.04.2007, 12:17

riwe

Auf diesen Beitrag antworten »

was verstehst du unter komplexer verwirrt

verwirrt

komplexer

verwirrt

werner

Anzeige

12.04.2007, 13:44

pkautz

Auf diesen Beitrag antworten »

Ja, genau sowas.

Gruß
Patrick

12.04.2007, 14:23

riwe

Auf diesen Beitrag antworten »

sowas geht aber "problemlos".
soweit ich das durchschaue, hast du (nur) probleme, wenn mehrere punkte exakt auf einer geraden liegen.
aber ich fürchte, die hast du dann immer Big Laugh

Big Laugh

werner

12.04.2007, 14:38

pkautz

Auf diesen Beitrag antworten »

Aber mal angenommen man wählt in Deinem Beispiel den Punkt $\begin{eqnarray*} D \end{eqnarray*}$ als Ausgangspunkt und die Richtung der positiven x-Achse als Ausgangsvektor, dann wäre ja der Winkel zwischen Ausgangsvektor und $\begin{eqnarray*} \vec{DH} \end{eqnarray*}$ kleiner als der Winkel zwischen Ausgangsvektor und $\begin{eqnarray*} \vec{DL} \end{eqnarray*}$ . Was wiederum, wenn ich Dich richtig verstanden habe, heißen würde, dass der Punkt $\begin{eqnarray*} H \end{eqnarray*}$ vor dem Punkt $\begin{eqnarray*} L \end{eqnarray*}$ kommt, was laut Zeichnung aber nicht der Fall ist. Oder habe ich da jetzt einen Denkfehler drin?

Gruß
Patrick

12.04.2007, 15:19

riwe

Auf diesen Beitrag antworten »

nein da hast du keinen denkfehler.
aber es wäre doch kein problem, mit dem punkt zu beginnen, der den kleinsten y-wert hat.

meine vermutung ist halt, dass alle probleme/spezialfälle, die bei dieser einfachen version auftauchen, auch bei allen anderen zu untersuchen sind.
wie willst du denn das z.b. mit dem exprodukt - das viel aufwendiger ist als das skalare pendant - umschiffen?

oder bessere ( verwirrt

verwirrt

)variante:
beginne bei D, suche den minimalen winkel -> B,
nun bestimme den minimalen winkel von B aus -> M....

wozu gibt es schließlich computer
(wenn´s nicht gerade 1000000...punkte sind,
dann mußt halt den handlungsreisenden befragen unglücklich

unglücklich

)

ist das das berühmte ei verwirrt

verwirrt

werner

12.04.2007, 15:56

pkautz

Auf diesen Beitrag antworten »

Zitat:

Original von wernerrin
oder bessere ( verwirrt

verwirrt

)variante:
beginne bei D, suche den minimalen winkel -> B,
nun bestimme den minimalen winkel von B aus -> M....

Das klingt ganz gut, aber was passiert bei M? Minimaler Winkel zu L, aber es müsste J kommen. Leider.

Anderer Vorschlag:
Ich wähle den Punkt aus, der den kleinsten x-Wert besitzt. Sollten mehrere Punkte den gleichen minimalen x-Wert haben, wird der mit dem maximalen y-Wert ausgewählt => $\begin{eqnarray*} p^* \end{eqnarray*}$ . Jeder Punkt kann nur mit zwei anderen Punkten verbunden sein. Dann nehme ich die Kante welche den größeren Winkel besitzt und setze den Endpunkt der Kante als Startpunkt und $\begin{eqnarray*} p^* \end{eqnarray*}$ als zweiten Punkt. Nun müsste ich auf Grund der Prämisse, dass jeder Punkt nur zwei Nachbarn besitzt, durch eine geeignete Datenstruktur iterieren und den Polygonzug zusammenbasteln.

Im Beispiel:
$\begin{eqnarray*} p^* = G \end{eqnarray*}$
Winkel $\begin{eqnarray*} \vec{GH} < \vec{GD} \end{eqnarray*}$ => H ist Startpunkt, gefolgt von G dann D, B, M, ...

Oder gibt es irgendwelche Einwände?!

Gruß
Patrick

12.04.2007, 16:11

riwe

Auf diesen Beitrag antworten »

ja das war ein faules ei.
wie schön, dass es dein problem ist. Big Laugh

Big Laugh

den rest muß ich noch bebrüten,
wie wäre es mit ein paar daten, damit man sich nicht an "meiner" skizze festrennt!
ich versuch´s dann mit dem minimum von y usw.
werner

12.04.2007, 17:04

pkautz

Auf diesen Beitrag antworten »

Hier ein paar Daten.

Punkte:
$\begin{eqnarray*} p_{0} = (0; 3)\\p_{1} = (2; 0)\\p_{2} = (5; 1)\\p_{3} = (8; 3)\\p_{4} = (5; 4)\\p_{5} = (3; 6)\\p_{6} = (4; 8)\\p_{7} = (2; 7)\\p_{8} = (3; 4)\\p_{9} = (3; 2) \end{eqnarray*}$

Kanten:
$\begin{eqnarray*} k_{0} = (p_{0}, p_{1})\\k_{1} = (p_{1}, p_{9})\\k_{2} = (p_{2}, p_{9})\\k_{3} = (p_{2}, p_{3})\\k_{4} = (p_{4}, p_{3})\\k_{5} = (p_{0}, p_{8})\\k_{6} = (p_{7}, p_{8})\\k_{7} = (p_{6}, p_{5})\\k_{8} = (p_{6}, p_{7})\\k_{9} = (p_{5}, p_{4}) \end{eqnarray*}$

Gruß
Patrick

12.04.2007, 17:32

riwe

Auf diesen Beitrag antworten »

verstehe ich da was falsch?
also ich dachte, du hast die punkte gegeben und suchst IRGENDEINEN (orientierten) polygonzug.
erkenntnis neu:
du hast die punkte und jeweils die beiden nachbarpunkte bereits gegeben?
was suchst du dann genau?
werner

12.04.2007, 17:49

AD

Auf diesen Beitrag antworten »

Ich hab den Thread nur überflogen, deswegen verzeiht, wenn ich das eine oder andere gesagte übersehen habe...

Du hast also ein Polygon in der Ebene, nicht notwendig konvex, aber doch (hoffentlich) nicht "überschlagen" und suchst nun den Umlaufsinn: positiv oder negativ.

Dann berechne doch die vorzeichenbehaftete Fläche des Polygons

$\begin{eqnarray*} F = \frac{1}{2} \sum_{k=1}^n (x_iy_{i+1}-x_{i+1}y_i) \end{eqnarray*}$ ,

dabei ist natürlich $\begin{eqnarray*} x_{n+1}=x_1,y_{n+1}=y_1 \end{eqnarray*}$ zu setzen, die Summanden sind quasi die z-Komponenten des Kreuzprodukes $\begin{eqnarray*} \begin{pmatrix} x_i\\ y_i\\ 0\end{pmatrix} \times \begin{pmatrix} x_{i+1}\\ y_{i+1}\\ 0\end{pmatrix} \end{eqnarray*}$ .

Das erhaltene Vorzeichen von $\begin{eqnarray*} F \end{eqnarray*}$ entspricht nun dem Umlaufsinn des Polygons: positiv - positiv, negativ - negativ.

Bei Null ist der Flächeninhalt Null, da kann man von keinem Umlaufsinn sprechen.

12.04.2007, 18:20

riwe

Auf diesen Beitrag antworten »

hallo arthur,
ich habe da offensichtlich alles falsch verstanden,
nun noch eine frage dazu:
genügt es nicht - im sinne der pkautz ´schen anfangsvermutung - so vorzugehen:

ich nehme irgendeinen punkt z.b $\begin{eqnarray*} P_0 \end{eqnarray*}$ , dessen nachbarpunkte sind nun bekannt mit $\begin{eqnarray*} P_1 \end{eqnarray*}$ und $\begin{eqnarray*} P_8 \end{eqnarray*}$ .
da
$\begin{eqnarray*} \overrightarrow{P_0P_1}\times\overrightarrow{P_0P_8}=\begin{pmatrix} 0 \\ 0 \\ 11 \end{pmatrix} \end{eqnarray*}$
heißt das doch, mit $\begin{eqnarray*} P_0 \to P_1.... \end{eqnarray*}$ wandere ich gegen den uhrzeigersinn, und der rest ist ja damit festgelegt verwirrt

verwirrt

irgendwie kommt mir das zu einfach vor,
aber ich verstehe eben das problem nicht (mehr oder noch nicht) verwirrt

verwirrt

werner

12.04.2007, 19:22

AD

Auf diesen Beitrag antworten »

Bei einem konvexen Polygon würde das stimmen, aber i.a. nicht bei so einem Zick-Zack-Polygon, wie du es oben aufgemalt hast. Augenzwinkern

Augenzwinkern

12.04.2007, 20:44

riwe

Auf diesen Beitrag antworten »

danke schön
werner

13.04.2007, 09:21

pkautz

Auf diesen Beitrag antworten »

Also ich habe (wie schon im ersten Thread beschrieben) die Punkte und Kanten gegeben und suche ein positiv orientiertes Polygon. War wohl etwas dämmlich formuliert. Vielleicht wird es so klarer. Ich suche die Reihenfolge der Punkte und damit auch Kanten, so dass sich für das beschriebene Polygon ein positiver Umlaufsinn ergibt.
Benötige die ganze Sache für die anschließende Triangulation des Polygons. Um konsistente Vorgänger-Nachfolger-Beziehungen zu erhalten müssen alle Kanten des Polygons die gleiche Orientierung haben.

Gruß
Patrick

13.04.2007, 09:32

AD

Auf diesen Beitrag antworten »

Das ist immer noch etwas unklar formuliert, wenn du sagst, dass du die Reihenfolge suchst...

Ist es nicht eher so: Wenn du Punkte und Kanten hast, dann besteht doch nur noch die Alternative zwischen zwei Richtungen - "hin" oder "zurück". Also bei deinem Polygon $\begin{eqnarray*} P_0,P_1,\ldots,P_9 \end{eqnarray*}$ oder $\begin{eqnarray*} P_9,P_8,\ldots,P_0 \end{eqnarray*}$ .

13.04.2007, 09:41

riwe

Auf diesen Beitrag antworten »

genau darauf zielte meine frage.
jetzt bin ich so klug als wie zuvor
ich armer tor verwirrt

verwirrt

werner

13.04.2007, 09:48

pkautz

Auf diesen Beitrag antworten »

An sich ja. Wobei die Punkte nicht geordnet sind, d.h. das Polygon auch so $\begin{eqnarray*} P_0, P_5, P_9,\ldots, P_2 \end{eqnarray*}$ aussehen kann. Des Weiteren kann die Orientierung der Kanten unterschiedlich sein. Was aber im Endeffekt egal sein müsste, wenn ich als erstes meine Daten einmal durchlaufe und mir eine Nachbarschaftsliste der Punkte erstelle, mit dieser dann weiterarbeite und nach der Vorgehensweise ein paar Beiträge weiter oben meine Punkte "sortiere".

Gruß
Patrick

13.04.2007, 10:15

AD

Auf diesen Beitrag antworten »

Zitat:

Original von pkautz
An sich ja. Wobei die Punkte nicht geordnet sind, d.h. das Polygon auch so $\begin{eqnarray*} P_0, P_5, P_9,\ldots, P_2 \end{eqnarray*}$ aussehen kann.

Jetzt bin ich vollkommen verwirrt: Ich denke, die Kante $\begin{eqnarray*} P_0P_5 \end{eqnarray*}$ ist gar nicht dabei???

EDIT: Hab mir den Thread doch noch mal genauer durchgelesen, insbesondere dein obiges Beispiel mit dem Zehneck. Die richtige Aneinanderreihung der Kanten ist doch ein vorgelagertes Problem, das kann man doch von dem anderen Problem des Umlaufsinns abtrennen:

$\begin{eqnarray*} k_0 = (p_0, p_1)\\ k_1 = (p_1, p_9)\\ k_2 = (p_9, p_2)\\ k_3 = (p_2, p_3)\\ k_4 = (p_3, p_4)\\ k_9 = (p_4, p_5)\\ k_7 = (p_5, p_6)\\ k_8 = (p_6, p_7)\\ k_6 = (p_7, p_8)\\ k_5 = (p_8, p_0) \end{eqnarray*}$

Ist doch unübersichtlich und schlecht, das so durcheinanderzumengen. Ich hab die ganze Zeit gedacht, es geht um einen bereits "richtig" sortierten Kantenzug bzw. Polygon.

13.04.2007, 10:24

pkautz

Auf diesen Beitrag antworten »

Sorry, Fehler vom Amt, war so aus dem Hut gegriffen und nicht auf das Beispiel bezogen. Für die Beispieldaten: $\begin{eqnarray*} P_0, P_8, P_7, \ldots, P_1 \end{eqnarray*}$ (negativer Umlaufsinn) bzw. $\begin{eqnarray*} P_0, P_1, P_9, \ldots, P_8 \end{eqnarray*}$ (positiver Umlaufsinn).

Gruß
Patrick

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »