Diskussion:Gitter (Geometrie)

Sammelartikel

Ich habe mal versucht, in diesem Artikel eine ganze Reihe eher rudimentärer Artikel zu mehr oder weniger dem gleichen Thema zusammenzufassen. Konkret handelt es sich dabei um die (jetzt ehemaligen) Artikel Rechengitter, Meshing, Adaptives Meshing, Triangulation (Punktemenge) und Dreiecksnetz, die ich jeweils durch eine Weiterleitung auf diesen Artikel ersetzt habe. Weiterhin ist geringes Material ist aus dem Artikel Diskretisierung eingeflossen, der verschlankt wurde. Ich hoffe, dass durch diese Bearbeitungen keine wichtigen Aspekte verloren gingen, die mir evt. nicht bewusst waren.--KMic 00:05, 29. Jun. 2011 (CEST)

Also überflogen sieht der Artikel sehr gut aus. Was ich persönlich etwas schade finde, ist dass dabei manchmal die Zuordnung zu fremdsprachigen Artikeln unter die Räder gerät. Zum Beispiel müssten jetzt die Artikel en:Triangulation (geometry) und en:Regular grid beide auf Gitter (Geometrie) verweisen und umgekehrt, was natürlich nicht geht. Das ist halt ein kleiner Nachteil, den man bei solchen Zusammenlegungen leider immer hat. --Bananenfalter 22:21, 29. Jun. 2011 (CEST)

Nachbarzellen in unstrukturierten Gitter lassen sich nicht berechnen?

Unstrukturierte Gitter sind sehr flexibel und einfach einzusetzen, da sie einfach automatisch erzeugt werden können. Die Datenverwaltung ist allerdings sehr aufwändig, da nicht berechnet werden kann, welche die Nachbarzellen einer bestimmten Zelle sind, sondern diese Information explizit gespeichert werden muss. Unstrukturierte Gitter benötigen daher bei der Speicherung häufig ein Mehrfaches des Speicherbedarfs von strukturierten Gittern.

Weiß jemand woher die Aussage stammt, dass Nachbarschaften in unstrukturierten Gittern nicht berechnet werden können? Ich habe es mit zu diesem Beitrag zurückverfolgt, eine Quelle ist aber nicht angegeben. Eigentlich sollte es kein Problem sein, in einem solchen Gitter die Nachbarzelle zu berechnen. Die Zellen haben eine gemeinsame Kante und gemeinsame Knoten, die nur in dem Datenbestand gefunden werden muss. Es ist nicht unmöglich, sondern einfach nur aufwendiger.

Der Datenbestand wird dann auch nicht zwingend größer, eben nur wenn Informationen zu den Nachbarschaften zusätzlich abgespeichert werden. Wenn niemand was dagegen hat, sollten wir das anpassen. Viele Grüße, --Adrian Lange ☎ 14:37, 30. Jun. 2011 (CEST)

Vielleicht ist der Begriff "berechnen" an dieser Stelle ein wenig doppeldeutig. Natürlich erhält man auch in unstrukturierten Gittern die Nachbarzellen, aber nur wenn vorher die Nachbarschaftsinformationen explizit abgespeichert wurden. In strukturierten Gittern ist dies gerade nicht notwendig, und das ist auch der Punkt: In unstrukturierten Gittern sind einfach mehr Verwaltungsinformationen notwendig, und diese müssen zur Laufzeit auch noch ausgewertet werden.

Ein Beispiel: Stell dir ein gleichmäßiges Gitter für ein zweidimensionales Rechteck vor. An Verwaltungsinformationen benötigst du die Koordinaten eines Eckpunktes des Rechtecks, die Gittergröße in x- und y-Richtung und die Anzahl der Zellen in x- und y-Richtung. Damit ist das Gitter vollständig beschrieben, alle Gitterpunkte etc. lassen sich hieraus (analytisch!) berechnen. Die Nutzdaten werden in einem zweidimensionalen Array gespeichert. Willst du den rechten Nachbarn vom Element (i,j) haben, so ist dies das Element (i,j+1).

In einem unstrukturierten Gitter ist es dagegen viel komplizierter. Hier musst du zu jedem Element alle zugehörigen Eckpunkte abspeichern und zudem zu jeder Kante das zugehörige Nachbarelement. Und wenn das Gitter jetzt auch noch ein adaptives Gitter ist, können an einer Kante sogar mehrere Nachbarn liegen...

Ansonsten übrigens noch Danke für deine Änderungen/Korrekturen!--KMic 21:05, 30. Jun. 2011 (CEST)

Okay, das leuchtet mir jetzt ein. Aber die aktuelle Formulierung finde ich dennoch etwas missverständlich. Die Nachbarschaftsinformationen müssen nicht explizit gespeichert werden, sondern können auch durch die Eckpunkte ermittelt werden. Da kommt es auf die Rahmenbedingungen und den Einsatzzweck an. Und müssen zu nicht-gleichmäßigen strukturierten Gittern nicht auch Eckpunktkoordinaten gespeichert werden? Demnach kann der Speicherbedarf eines unstrukturierten dem eines strukturierten Gitters gleichen, allein die Einfachheit des Ermittelns einer Nachbarzelle ist unterschiedlich.

Meine Änderungen waren ja nur Kleinigkeiten ;-) Viele Grüße, --Adrian Lange ☎ 12:17, 1. Jul. 2011 (CEST)

Stimmt, du hast Recht, die Nachbarschaftsinformationen können tatsächlich aus den Gitterpunkten errechnet werden, war mir garnicht so bewusst. Aus Effizienzgründen macht das aber keinen Sinn, da man dann zur Bestimmung des Nachbars im schlimmsten Fall alle Gitterelemente durchlaufen müsste um zu schauen, welches Element genau die entsprechenden Gitterpunkte verwendet. Das Argument mit dem Speicherbedarf bleibt aber dennoch richtig (wenn auch im Artikel falsch begründet), da strukturierte Gitter per Definition eine Struktur besitzen, die man irgendwie ausnutzen kann und wird. Beim rechtwinkligen Gitter reicht etwa eine Folge von Schrittweiten pro Koordinatenachse, um das Gitter vollständig zu bestimmen. Falls du motiviert bist, kannst du diese Information ja gerne in den Artikel einbauen, ansonsten schau ich es mir die Tage mal an.--KMic 13:54, 1. Jul. 2011 (CEST)

Es ist interessant anzuschauen, wie unterschiedlich die Sichtweisen von Personen aus der Mathematik und aus der Informatik auf eine Problemstellung sind ;) Ich habe den Absatz mal wie folgt umgeschrieben. Für mich ist so verständlicher, du kannst aber gerne noch an der Formulierung feilen.

Unstrukturierte Gitter sind sehr flexibel einzusetzen und können zudem einfach automatisch erzeugt werden. Die Datenverwaltung ist allerdings aufwändiger als bei strukturierten Gittern, weil die Nachbarzellen nicht analytisch berechnet werden können, sondern aus explizit abgespeicherten Informationen ausgelesen werden müssen. Aufgrund der regelmäßigen Topologie strukturierter Gitter können Gitterzellen über einen Index aufgerufen und die Position unter diesem abgespeichert werden. Da unstrukturierte Gitter dagegen keinerlei Regelmäßigkeiten aufweisen, müssen zum Suchen einer Gitterzelle im schlechtesten Fall alle Gitter durchlaufen werden. Dabei kann es sinnvoll sein, neben den Positionen aller Zelleneckpunkte auch Nachbarschaftsinformationen abzuspeichern. Daher benötigen unstrukturierte Gitter im Allgemeinen einen höheren Rechenaufwand oder bei der Speicherung ein Mehrfaches des Speicherbedarfs von strukturierten Gittern.

Das mit der Effizienz kommt auf die Größe des Gitters an. Bei kleinen Gittern kann es schon vorkommen, dass das Abfragen und Verarbeiten der Nachbarschaftsinformationen aus einem persistenten Speicher ineffizienter ist als die Berechnung der Nachbarschaften. Die Komplexität zum Ermitteln einer Nachbarschaft in strukturierten Gittern ist $\theta (1)$, in unstrukturierten Gittern $\theta (n)$. Beim Bestimmen aller Nachbarschaften jeder Zelle steigt die Komplexität der Berechnung bei unstrukturierten Gittern sogar auf $\theta (n^{2})$, bei strukturierten Gittern ist es dann nur $\theta (n)$. Somit spielt auch die Art der Anwendung eine Rolle. Wenn nur Nachbarschaftsinformationen einer einzelnen Zelle ermittelt werden sollen, kann es noch effizient sein, es zu errechnen. Außerdem müssen die Nachbarschaften vor dem expliziten Abspeichern auch erst berechnet werden, weshalb habe ich es als optional formuliert habe. Viele Grüße, --Adrian Lange ☎ 09:45, 6. Jul. 2011 (CEST)

Habe auf Basis deines den entsprechenden Abschnitt überarbeitet. Ich hoffe keinen Gesichtspunkt vergessen zu habe und das ganze dennoch verständlich dargestellt zu haben. Wenn nicht, einfach korrigieren ;-) --KMic 06:17, 8. Jul. 2011 (CEST)

Deine Änderungen gefallen mir sehr gut, ich habe aber noch im darauf folgenden Abschnitt eine kleine Umformulierung gemacht. Ich hoffe es gefällt ;) Viele Grüße, --Adrian Lange ☎ 13:30, 14. Jul. 2011 (CEST)

Ja, auf jeden Fall. "Ermitteln" klingt hier auch definitiv besser als das irgendwie mehrdeutige "berechnen".--KMic 16:37, 14. Jul. 2011 (CEST)