Zusammenfassen von Polygonen

[dali]

Lustig

[rapso]

TGGC schrieb:

polygonezusammenfassen schrieb:

Ich suche einen Algorithmus, der mir einen Satz von Polygonen auf gemeinsame Kanten prüft und solche zu einem Polygon zusammenfasst.
Kennt jemand eine Bibliothek oder einen Algorithmus der das hinbekommt?

a) Suche Polygone mit gemeinsamen Kanten
b) wenn keines gefunden => STOP
c) wenn zwei Polygone gefunden => fasse zusammen
d) geha nach a

schön dass du seine frage nochmal umformuliert hast, nun ist sie viel einfacher zu verstehen.

rapso->greets();

[TGGC]

np

Bye, TGGC (Der Held bei Dir!)

[Jester]

Ich finde TGGC hat vollkommen recht. Das ist doch der Algorithmus. Wo ist jetzt noch das Problem? Das kann man nahezu wörtlich nach C++ übersetzen:

while(findAdjacentPolygon(polygonPair))
{
  join(polygonPair);
}

fertig.

Polygone finden ist auch recht einfach: Schleife drüber, jedes mit jedem vergleich und nachschauen. Natürlich könnte man auch zuvo sortieren um so etwas effizienter suchen zu können. Aber das steckt so in der Frage nicht drin.
Wie das Verbinden gemeint ist ist auch nicht weiter definiert, aber es sollte nicht allzuschwer sein einfach die beiden Polygone an der Kante zusammenzufassen.

MfG Jester

[interpreter]

Kann mich Jester nur anschließen und rapsos Beitrag nicht ganz nachvollziehen. Das ist der Algorithmus. Den Rest sollte er selber schaffen.

[Sgt. Nukem]

Wollt' ich auch gerade schreiben...

P.S.: Er schreibt ja nicht mal, in welcher API - geschweige denn Sprache - er es braucht! Was soll man da mehr bieten können als Pseudocode??

[Trienco]

Sgt. Nukem schrieb:

P.S.: Er schreibt ja nicht mal, in welcher API - geschweige denn Sprache - er es braucht!

?? was hat die api oder sprache damit zu tun? man braucht allerdings ein wenig phantasie und muß sich vermutlich dazudenken "gibt es da auch eine clevere, effiziente methode, bei der man nicht wie bescheuert tausendmal über alle polygone läuft?"

man könnte natürlich auch fragen, wofür das ganze überhaupt gebraucht wird, nur für den fall, daß da jemand auf die komisch idee kommt, er könnte in opengl irgendwas schneller bekommen, wenn er seine objekte als ein fettes polygon statt viele dreiecke darstellt.

ansonsten könnte das problem noch darin bestehen, nicht drauf zu kommen, woran man eine gemeinsame kante überhaupt erkennen kann... aber in dem fall könnte man auch unverschämt antworten: "wer sowas fragen muß, der sollte von grafikprogrammierung erstmal abstand nehmen" ,-)

[randa]

Man ermittelt die Kante, die beide Polygone gemeinsam haben. Wenn gefunden, die Rheienfolge der Punkte der Polygone so ändern, dass die Punkte eines bilden.
Also:

Polygon a: Ein Dreieck
Vertex1a
Vertex2a
Vertex3a

Polygon b: Ein Viereck
Vertex1b
Vertex2b
Vertex3b
Vertex4b

Rheienfolge im Uhrzeigersinn.

=> Finde gemeinsame Kante => hier (Vertex1a, Vertex2a) und (Vertex3b, Vertex4b) (Bsp.)

Wir beginnen hier mit Vertex1b, dem ersten Punkt von Polygon b.

=> Neue Ordnung: Gehe alle Punkte der Reihe nach durch.
Beachte die Kante nicht, sondern fahre bei Vertex3b fort. Es wird ermittelt, das Vertex3b 
der gleiche Punkt ist wie Vertex2a. Fahre bei Vertex 2a solange fort, bis du auf Vertex1a stösst. Dieser ist 
hier der gleiche wie Vertex4b. Wenn beim letzten Punkt angelangt (in diesem Fall ja), Abbruch.

Polygon c: Es wird beim ersten Punkt vom Polygon b begonnen (das Viereck)
Vertex1b
Vertex2b
Vertex3b (Vertex2a)
Vertex3a
Vertex4b (Vertex1a)

Falls du mit dem ersten Punkt des Dreiecks beginnst => Du stellst fest, das Vertex1a gleich Vertex4b 
(dem Endpunkt des Vierecks) ist und fährts nicht mit Vertex2a fort, sondern mit dem Startpunkt von Polygon b, 
also Vertex1b. Da du in der Rheienfolge feststellst, das Vertex4b der letzte Punkt ist, weißt du 
dass du nun als nächsten Punkt Vertex1b checken musst.

Polygon c: Beginnt beim ersten Punkt des Dreiecks:
Vertex1a (Vertex4b)
Vertex1b
Vertex2b
Vertex3b (Vertex2a)
Vertex3a

Keine Ahnung ob das verständlich war, mal es auf ein Blaat Papier dann kann man es besser nachvollziehen
Ich bin mir nicht ganz sicher, wie allgemeingültig das ist. Nur ne idee

Man kann diese Sache in einer Schleife optimal lösen. Die Regel ist: Sobald du auf einen Punk stößt, der Teil der gemeinsamen Kante ist, fährst du mit dem gleichen Punkt des anderen Dreiecks fort und speicherst diese als nächste Punkte des Ergebnispolygons.

[Sgt. Nukem]

Trienco schrieb:

Sgt. Nukem schrieb:

P.S.: Er schreibt ja nicht mal, in welcher API - geschweige denn Sprache - er es braucht!

?? was hat die api oder sprache damit zu tun?

...wenn er NICHT NUR Pseudocode will?!?

Zerstümmel meinen Satz nicht!

[rapso]

ich hatte ja nur geschrieben, dass er in der frage ja schon die antwort stehen hatte.

welchen spezialfall er meint muss er jetzt halt noch sagen (nur planaer flächen, nur convexe polys...). es gibt dazu auch nen artikel bei "asking midnight" auf flipcode.

rapso->greets();

[ChrisBorgolte]

ER hat gerade sein Passwort wiedergefunden.

Ich glaube, hier liegt ein Mißverständnis vor. Ich wollte in erster Linie nach einem tatsächlich bereits implementierten Algorithmus fragen. So wie es bspw. verschiedene Ansätze gibt, Polygone in Dreiecke zu fassen, könnte es ja sein, dass es auch für mein Problem bereits eine _vorhandene_ Lösung gibt.
Darum hatte ich ja auch unter "Rund um die Programmierung" geposted und hätte es auch sonste eher unter "Mathe" als "Grafikprogrammierung" versucht.

Welche Sprache? Vielleicht war ich ein wenig voreilig mit dem Posten, aber ich dachte, wenn die URL schon c-plusplus.net heißt, dann läge die Sprache auf der Hand.

@TGGC:
Leider muss ich sehr viele Polygone auch gemeinsame Kanten testen und da reicht Dein Ansatz wirklich nicht aus.

@Trienco:
Mit OpenGL hat das alles nix zu tun.
Tatsächlich kann man aber durch das Zusammenfassen der Polygone bei grosser Anzahl viel kleinere Dateien erzeugen und auch die Darstellung (wohlgemerkt nicht unter OpenGL, sondern ganz normal unter wxWidgets) erheblich beschleunigen.

Trotzdem schon mal vielen Dank für die Antworten.

Gruß
Chris

[ChrisBorgolte]

rapso schrieb:

es gibt dazu auch nen artikel bei "asking midnight" auf flipcode.

Hast Du vielleicht auch den Link zu diesem Artikel?

[noebef]

Ich würd's mal mit www.flipcode.com unter "Ask Midnight" versuchen.

[Trienco]

Sgt. Nukem schrieb:

...wenn er NICHT NUR Pseudocode will?!?

dann würde ich schnell die seiten wechseln, weil es zwei dinge gibt, bei denen jede hilfsbereitschaft flöten geht.

a) ich will dieses und jenes, postet mir mal jemand fertigen code, den ich dann am besten bloß noch mit copy/paste einfügen muß?

b) ich knall mal schnell 5 bildschirmseiten code hin. so, und das "funzt" nicht, wo ist der fehler?

aber bei der frage nach dem algo. bin ich stillschweigend davon ausgegangen, daß er wirklich nur eine clevere methode und keinen fertigen code sucht.

ist ein polygon überhaupt noch ein polygon, wenn es nicht planar ist? und kann man in dem fall in der praxis wirklich noch soviel einsparen? *grübel* naja, in ein paar jahren kein thema mehr, wenn selbst os-oberflächen nur noch in "3d" gemacht werden und "altmodische" 2d grafik endgültig ausgestorben ist *fg*

[Sgt. Nukem]

ChrisBorgolte schrieb:

Welche Sprache? Vielleicht war ich ein wenig voreilig mit dem Posten, aber ich dachte, wenn die URL schon c-plusplus.net heißt, dann läge die Sprache auf der Hand.

Dann guck' Dir die Foren hier mal genauer an...

Trienco schrieb:

*grübel* naja, in ein paar jahren kein thema mehr, wenn selbst os-oberflächen nur noch in "3d" gemacht werden und "altmodische" 2d grafik endgültig ausgestorben ist *fg*

Soweit wird's zum Glück niemals kommen!!
Jetzt können zunächst auch Mainstream-Handys alle 3D wie FarCry.
Dann gibt's mehr und mehr Waschmaschinen und Kühlschränke, die mit kleinen Computern und zunächst nur billigen LC-Displays ausgerüstet werden. Dort erleben dann die alten C64-Spiele wieder eine Renaissance...

[Trienco]

Sgt. Nukem schrieb:

Dann gibt's mehr und mehr Waschmaschinen und Kühlschränke, die mit kleinen Computern und zunächst nur billigen LC-Displays ausgerüstet werden. Dort erleben dann die alten C64-Spiele wieder eine Renaissance...

perfekt. dann wird wäsche waschen dank m.u.l.e. zum partyspaß und wer den highscore in tetris knackt bekommt seine cola extra kalt ,-)

[TGGC]

Sgt. Nukem schrieb:

Dort erleben dann die alten C64-Spiele wieder eine Renaissance...

Da fällt mir ein, ich wollte doch ein paar solche hochladen...

Bye, TGGC (Der Held bei Dir!)

[Jester]

ChrisBorgolte schrieb:

Leider muss ich sehr viele Polygone auch gemeinsame Kanten testen und da reicht Dein Ansatz wirklich nicht aus.

Das ist so nicht ganz richtig. Der Ansatz ist weder ineffizient noch sonstwas. Es steht nirgends, daß die Suche ungeschickt erfolgen muß oder sowas. Auf jeden Fall könntest Du es mal so implementieren. Das geht in ca. 20 Minuten, dann läuft es korrekt würde ich mal schätzen.
Von da an hast Du mal ne funktionierende Referenz. Das heißt, Du kannst wenn Du den Algorithmus verbesserst immer noch die funktionierende kahme Version mitlaufen lassen um so automatisch das Ergebnis zu verifizieren.
Dann nimmste mal ne vernünftig große Szenerie und haust die durch. Profiler verrät Dir dann die Bottle-Necks und Du kannst an's optimieren gehen.
Vielleicht nützt es was, wenn Du die Polygone vorher in eine Art BSP-Tree einsortierst etc. oder Dir beim durchlaufen zumindest merkst, wie weit Du schon verglichen hattest und nur das wieder vergleichst, was sich auch geändert haben kann. Aber das ist dann ne andere Frage.
Und zunächst einfach mal ne funktionierende Referenzimplementierung zu haben ist sicher was feines, wenn man nen ordentlichen Algorithmus bauen will.

MfG Jester

[ChrisBorgolte]

Jester schrieb:

Das geht in ca. 20 Minuten, dann läuft es korrekt würde ich mal schätzen.

Das ist der Irrglaube, dem man als Programmierer leider immer wieder erlegen ist. Dann fängst Du an zu hacken, debuggen und wenn es dann endlich klappt, mit dem Profiler nochmal die möglichen Bottlenecks rauszufiltern.
Anschließend probiert man es dann mal in einem realitätsnahen Einsatz von vielleicht 500.000 Polygonen aus und stellt dann fest, dass
1.man mal wieder irgendeinen Sonderfall übersehen hat
2.es viel zu langsam ist
3.der Speicher nicht ausreicht
4....

Dann sitzt man da, zerbricht sich den Kopf über mögliche Sortierverfahren, eine alternative Datenhaltung und weitere mögliche Sonderfälle, die man vielleicht noch nicht berücksichtigt hat, oder doch einen ganz anderen Ansatz, dieses Problem zu lösen. Schliesslich hat man ja noch nicht einmal das grösste bekannte Modell ausprobiert, sondern nur ein grosses.
Das dauert dann nicht mehr schlappe 20 Minuten.

Irgendwann, wenn man wirklich viel Zeit investiert hat, dann stolpert man zufällig im Internet über einen interessanten Beitrag: Da hat doch irgend so ein schlauer Mensch genau über Dein Problem eine Abhandlung verfasst und am besten gleich noch eine Bibliothek oder die Quellen zum Download bereit gestellt, und das Ganze läuft dann sogar schon seit einigen Jahren und ist von tausenden von Leuten getestet worden.
Dann fällt dir die Grundregel wieder ein, die Du mal in jedem Buch, das mit Softwareentwicklung zu tun hat, gelesen hast: „Versuche nicht das Rad neu zu erfinden“.

Wie bereits erwähnt, hatte mit meinem Posting erhofft, jemand könnte mir mitteilen, dass es tatsächlich bereits eine Lösung für mein Problem gäbe. Es gibt schliesslich in diesem Bereich einige vorhandene Algorithmen, bzw. mathematische Disziplinen, ob es nun Triangulation oder Mesh Simplification oder sonst noch was ist.

Darum hatte ich auf so eine Antwort gehofft, wie:
„Klar, so was gibt's schon. Schau doch mal bei „...“ unter der Rubrik „...“ nach.“
(Leider habe ich trotz der grandiosen Hilfe von noebef den entsprechenden Artikel unter "Ask Midnight" nicht gefunden, vielleicht kannst Du mir da nochmal weiterhelfen, rapso.)

Ich wollte weder Pseudo-, noch realen Code, den irgendwer mal nach zwei Minuten nachdenken niedergeschrieben hat. Mir ist schon bewusst, dass es sich dabei nicht um Raketenphysik handelt (auch wenn ich Deinen Algorithmus schon als äußerst nahe daran bezeichnen möchte, TGGC), aber hier liegt der Teufel tatsächlich im Detail, bzw. in der Performance und im Speichermanagement.

mfG
chris

[Trienco]

in dem fall würde mir höchstens eine google suche zwecks progressive meshes oder allgemein dynamic lod einfallen. ist zwar nicht ganz das gleiche, aber das grundlegende problem möglichst schnell (bevorzugt echtzeit) das modell zu vereinfachen bzw. die nötigen infos dafür dürften ähnlich ausfallen.