Zusammenfassen von Polygonen

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?

Vielen Dank

C++ Forumbot

Dieser Thread wurde von Moderator/in kingruedi aus dem Forum Rund um die Programmierung in das Forum Spiele-/Grafikprogrammierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

TGGC

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

Bye, TGGC (Der Held bei Dir!)

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