4. Algorithmus für Polygonvertexorder mit konstanter Normalenausrichtung gesucht!

Algorithmus für Polygonvertexorder mit konstanter Normalenausrichtung gesucht!

  • P

    volkard schrieb:

    dot schrieb:

    volkard schrieb:

    Und das ist immer so und soll immer so bleiben? Dann kannste Dir schon eine Sache ausdenken, daß dieses Kreuzprodukt immer nach +y zeigt.

    Exakt. Wenn ihm +y ausreicht was ja offenbar dann doch nicht der Fall was...

    Dann soll er endlich mal sagen, was seine Ausgangsdaten sind, zum Beispiel ob es Polygone oder Punktmengen (die ganz im Gegensatz zu Polygonen umsortiert werden dürfen) sind, und was das Ergebnis sein soll.
    Bis er das geschafft hat, halte ich mich raus.

    Entschuldige bitte, aber das tue ich die ganze Zeit!
    1. Ich habe nie von einer Punktewolke gesprochen. Es ist die ganze Zeit die Rede von einem Polygon, das sowohl konkav als auch konvex sein soll.
    2. Ich habe inzwischen mindestens 4 Mal geschrieben, dass ich eine Normale in Richtung der positiven y-Achse haben will.

    0
  • P

    dot schrieb:

    Warum überhaupt das rumprobieren. Bestimm einfach die Normale und wenn sie dir nicht passt extrudier in die andre Richtung!?

    Das wiederum habe ich ebenfalls vor 4 oder 5 Posts geschrieben. Aber ich schreibs auch gerne noch mal, um mir nicht vorwerfen zu lassen, ich würde nicht sagen, was ich will.

    1. Die Extrusion ist nur der erste Schritt einer Folge von Berechnungen, die auf die Normale aufbauen. Ich habe diese herausgezogen, da man sich unter "Extrusion" leichter etwas vorstellen kann.

    2. In den nachfolgenden Berechnungen will ich mich darauf verlassen können, dass die Vertexorder derart gewählt ist, dass die Normalen so ausgerichtet sind, wie ich es will (ALSO: positive y-Achse). Da ich das aber nicht in jeder Berechnung hart coden will, will ich einmal die Vertexorder derart anpassen, dass sie in den nachfolgenden Berechnungen passt.

    0
  • V

    PatrickWG schrieb:

    Das läuft ja im Prinzip auf meinen Trial-And-Error-Ansatz hinaus, bei dem ich immer den Startpunkt und die Reihenfolge variiere, bis rauskommt, was ich haben will.

    Nur daß ich sicher nach dem ersten Test ankomme.

    PatrickWG schrieb:

    Habe es mit Sortierung zunächst nach y- dann nach x-Werten probiert,

    Und es ist mit O(n) auch schneller als Sortieren mit O(n*log(n)). Und zufälliges Probieren ist so ungewiß. Würde aber auch funktionieren und recht schnell sein.

    Es schien immer, daß Du meim Trial&Error eine zufällige Reihenfolge erzeugst und die testest. Daher die Punktmenge, die auf einmal eine Wolke ist. In Punktwolke steckt für mich schon wieder viel mehr Struktur als in Punktmenge. Und Reihenfolge und Umlaufsinn sind eben auch viel unterschiedlich. Das verwirrt mich.

    0
  • P

    volkard schrieb:

    PatrickWG schrieb:

    Das läuft ja im Prinzip auf meinen Trial-And-Error-Ansatz hinaus, bei dem ich immer den Startpunkt und die Reihenfolge variiere, bis rauskommt, was ich haben will.

    Nur daß ich sicher nach dem ersten Test ankomme.

    PatrickWG schrieb:

    Habe es mit Sortierung zunächst nach y- dann nach x-Werten probiert,

    Und es ist mit O(n) auch schneller als Sortieren mit O(n*log(n)). Und zufälliges Probieren ist so ungewiß. Würde aber auch funktionieren und recht schnell sein.

    Es schien immer, daß Du meim Trial&Error eine zufällige Reihenfolge erzeugst und die testest. Daher die Punktmenge, die auf einmal eine Wolke ist. In Punktwolke steckt für mich schon wieder viel mehr Struktur als in Punktmenge. Und Reihenfolge und Umlaufsinn sind eben auch viel unterschiedlich. Das verwirrt mich.

    Ok, ich verstehe deine Verwirrung. Ich wollte eben nicht die Reihenfolge der Vertices variieren (dann würde ich ja neue Polygone bauen), sondern nur das Startvertex von dem ausgehend ich die aufspannenden Vektoren berechne. Der Sortierungsansatz war drauf ausgerichtet, ein Vertex zu bekommen, das auf der konvexen Hülle liegt (eben um das Problem konkaver Polygone rauszubrechen). Dadurch erhoffte ich mir aufspannende Vektoren, die zu der Zielnormalen in y-Achsen-Richtung führen. Das war aber leider zu kurz gedacht und nicht von Erfolg gekrönt. Die konvexe Hülle war eben nur ein Zwischenschritt, das eigentliche Polygon muss natürlich unverändert bleiben. Aber wie du ja richtig schriebst, ist es egal, welchen Startpunkt ich als Ausgangspunkt für die Bestimmung der aufspannenden Vektoren verwende, an der Reihenfolge der eigentlichen Vertices ändert sich nichts (damit das Polygon erhalten bleibt).
    Hoffe, das ist jetzt was klarer geworden?

    0
  • V

    PatrickWG schrieb:

    Hoffe, das ist jetzt was klarer geworden?

    Ich glaube, ja.

    Vielleicht habe ich mich auch zu unklar ausgedrückt.

    vector<Punkt> v;
    //irgendwie die Punkte besorgen

    //Beispiel: a b c d e f g h i j
    if(kreuzprodukt(b-a,c-b).y)>0)//wenn winkel gut ist
    return;

    //winkel(a,b,c) ist dumm, denn wir haben nicht returnt
    swap(v[0],v[2])
    //c b a d e f g h i j
    for(size_t links=3,rechts=v.size()-1);links<rechts;++links,--rechts)
    swap(v[links],v[rechts]);
    //c b a j i h g f e d

    Die neue Reihenfolge ist nicht geraten, sondern wird durch genau die drei Zeilen Code

    swap(v[0],v[2]);
for(size_t links=3,rechts=v.size()-1);links<rechts;++links,--rechts)
   swap(v[links],v[rechts]);

    zielsicher erzeugt.

    Vielleicht gibt es noch günstigere Methoden, eine gute Reihenfolge zielsicher zu erzeugen. Aber nicht immer. Ein konvexes Polygon, daas dfalschrum ist, muß eben komplett umgedreht werden. Und es ist auch so schon recht schnell, unter anderem braucht nur ein einziges Kreuzprodukt berechnet zu werden.

    0
  • P

    volkard schrieb:

    PatrickWG schrieb:

    Hoffe, das ist jetzt was klarer geworden?

    Ich glaube, ja.

    Vielleicht habe ich mich auch zu unklar ausgedrückt.

    vector<Punkt> v;
    //irgendwie die Punkte besorgen

    //Beispiel: a b c d e f g h i j
    if(kreuzprodukt(b-a,c-b).y)>0)//wenn winkel gut ist
    return;

    //winkel(a,b,c) ist dumm, denn wir haben nicht returnt
    swap(v[0],v[2])
    //c b a d e f g h i j
    for(size_t links=3,rechts=v.size()-1);links<rechts;++links,--rechts)
    swap(v[links],v[rechts]);
    //c b a j i h g f e d

    Die neue Reihenfolge ist nicht gearten, sondern wird durch genau die drei Zeilen Code

    swap(v[0],v[2]);
for(size_t links=3,rechts=v.size()-1);links<rechts;++links,--rechts)
   swap(v[links],v[rechts]);

    zielsicher erzeugt.

    Ah, ok, verstehe, ein paar Zeilen Code erleichtern das Verständnis doch enorm. Das ist auf jeden Fall ein eleganter Ansatz, werde ich mal umsetzen und schauen, ob sich dadurch meine Problem in Luft auflöst.

    Dank dir schon mal für deine Mühen!

    0
  • V

    Sogar zwei Zeilen, wenn man http://www.cplusplus.com/reference/algorithm/reverse/ benutzt.

    0

  • PatrickWG schrieb:

    1. Die Extrusion ist nur der erste Schritt einer Folge von Berechnungen, die auf die Normale aufbauen. Ich habe diese herausgezogen, da man sich unter "Extrusion" leichter etwas vorstellen kann.

    2. In den nachfolgenden Berechnungen will ich mich darauf verlassen können, dass die Vertexorder derart gewählt ist, dass die Normalen so ausgerichtet sind, wie ich es will (ALSO: positive y-Achse). Da ich das aber nicht in jeder Berechnung hart coden will, will ich einmal die Vertexorder derart anpassen, dass sie in den nachfolgenden Berechnungen passt.

    1. Und um was für weitere Berechnungen soll es da konkret geben bzw. inwiefern ist es für diese Berechnungen notwendig dass die Normale aus den Vertices berechnet wird, warum kannst du dir die gewünschte Normale nicht einfach mal berechnen und irgendwo speichern!? Denn
    2. wie bereits mehrmals gesagt ist es schon rein mathematisch unmöglich die Vertices so zu sortieren dass bei einem beliebigen Polygon das Kreuzprodukt aufeinanderfolgender Kantenvektoren immer in die selbe Richtung zeigt. Das geht per Definition nur mit konvexen Polygonen. D.h. das Beste was du machen kannst ist dein Polygon so zu sortieren dass die Kantenvektoren die du für die Berechnung der Normale verwendest (also z.B. die ersten 2 Kanten) das gewünschte Ergebnis liefern. Allerdings frag ich mich dann eben warum du nicht einfach checken kannst in welche Richtung die Normale zeigt und sie, wenn sie verkehrt ist, einfach umdrehest. Da du deinen Punkt 2. eben sowieso abschreiben musst (weils unmöglich ist) kommt das effektiv doch absolut aufs Gleiche raus mit dem Unterschied dass du nichts sortieren musst.

    Was du dir vielleicht auch überlegen könntest wäre dein allgemeines Polygon generell erstmal in konvexe Polygone zu zerschnippeln und dann nurmehr mit denen zu arbeiten. Konvexe Polygone sind eben einfach viel angenehmer...

    0
  • V

    PatrickWG schrieb:

    1. Die Extrusion ist nur der erste Schritt einer Folge von Berechnungen, die auf die Normale aufbauen. Ich habe diese herausgezogen, da man sich unter "Extrusion" leichter etwas vorstellen kann.

    Ich habe mir unter einer Extrusion sofort eine Zonentaxonomie vorgestellt. Das war zwar leicht, hat aber nicht so viel geholfen.

    0
  • V

    Noch ne Idee.
    Also Drehsinn ändern kostet einmal das ganze Array anfassen. Startpunkt ändern lostet auch so viel. Da ich nur maximal einmal über das Array laufe, dürfte es kaum schneller gehen.
    Aber mir würde es bessser gefallen, wenn alle Polygone linksrum (rechtsrum) laufen würden.

    Den Drehsinn könnte man ausrechnen
    http://www.matheboard.de/archive/419771/thread.html
    letztes Posting.
    Und gegebenenfalls auf linksrum (rechtsrum) zwingen durch Umdrehen des ganzen Arrays.

    Und dann muß man nur noch eine konvexe Ecke finden und das Array rotieren, daß diese Ecke an Arrayindex 1 liegt.

    Das wäre dann maximal dreimal übers ganze Array laufen.

    0
Anmelden zum Antworten