Eigenschaften von Polygonnetzen
-
Ich habe ein Polygonnetz und möchte dessen Eigenschaften feststellen. Konkret geht es um die Charakterisierung von hexagonalen Gittern mit Fehlstellen:
http://postimg.org/image/beazt7jxn/fc7ac1be/
Das sind Messdaten, die genauen Werte können daher nicht als perfekt angesehen werden. Genauer gesagt, sind die Eckpunkte gemessen und die Kanten sind dann eingezeichnet als Verbindungen zwischen den Punkten bis zu einem festen Maximalabstand. Die "wilden" Bereiche, wie in dem Bild rechts oben, kann ich vom Rest unterscheiden, weil dort bei der Messung etwas anders war. Es gibt noch andere Messreihen, bei denen der hexagonale Teil mehr oder weniger Fehlstellen aufweist; oder der wilde Teil mehr oder weniger wild ist. Diese Eigenschaften würde ich gerne in konkreten Zahlen ausdrücken.
Ich komme aber nicht wirklich auf gute Ideen. Die Anzahl der Kanten pro Knoten wäre eine offensichtliche Charakteristik. Und vielleicht auch noch dessen Varianz. Aber wie kann ich ausdrücken, wie "verzerrt" das Hexagongitter ist? Da müssen also irgendwie Längen und Winkel einfließen.
Das ganze klingt nach einer Standardproblemstellung, aber ich finde nichts passendes und weiß auch nicht so recht, nach welchen Stichworten ich überhaupt suche. Vielleicht weiß ja jemand was oder hat ein paar schöne Ideen zu Charakteristiken.P.S.: Die Daten sind genau genommen 3D, aber eine Projektion auf 2D zur Vereinfachung wäre absolut akzeptabel. Die dritte Dimension ist hier nämlich praktisch flach.
-
SeppJ schrieb:
Die Anzahl der Kanten pro Knoten wäre eine offensichtliche Charakteristik. Und vielleicht auch noch dessen Varianz. Aber wie kann ich ausdrücken, wie "verzerrt" das Hexagongitter ist? Da müssen also irgendwie Längen und Winkel einfließen.
Ich brainstorme mal dumm rum.
Mir fällt zuerst ein, die "langen Geraden" anzuschauen, die ich als Mensch da sehe und zu schauen, wie krumm sie doch sind.
Mist, die "Geraden", die ich sehe, sind die Flächenmittelpunkverbindungsgeraden.
Ne kleine Hough-Transformation drauf und schauen, wie weit der Mittelpunkt abweicht."Mist", weil da nicht gescheit rüberkommt, wenn ein Sechseck voll mißgestaltet ist und perfekterweise seine 6 Nachbarn genau komplemetär mißgestaltet und die 7 Sechsecke als Außenkante voll regulär sind. Da kriege ich an Ankucker das Kotzen aber die Flächenmittelpunkte sind nur recht wenig displaced. Insbesondere wäre das verdrückte Sechseck perfekt bewertet.
Winkel und Längen? Klar, viel besser. Jeder Knoten muss zu seinen 3 Nachbarknoten 120Grad und die Normallänge haben. Abstandsquadrate vom "Richtigen" aufaddieren, das fühlt sich stark an. Aber das haste sicher schon probiert, und es ist in die Hose gegangen, sonst würdest Du nicht fragen.
Dann fällt mir nur noch ein (Rechenzeit spielt mal keine Rolle), eine sozusagen-Hough-Transformation für jeden Knotenpunkt zu machen und dabei die entfernteren (exponentiontiell?) schwächer einfließen zu lassen und dann zu schauen, wie gut der Knoten reinpaßt. Das würde aber die Sechseckigkeit nicht mehr so betonen und größere Regionen von wenn auch ein wenig schiefen Quadraten wären besser als supi-Sechsecke.
Winkel und Längen? Das kann man auch auf die Flächenmittelpunkte beziehen. Jeder MP muss zu seinen 6 Nachbar-MPs je 60Grad und die Nurmallänge haben.
Am besten scheint mir, ich schaue das displacement des Knotens von seinen drei Nachbarmittelpunkten an.
Ohje, 6 verschiedene Formeln. Vielleicht kriegr man eine zufriedenstellende Superformel, wenn man die 6 nach Gusto gewichtet.
Dann müßte noch rein, Entfernungsunterschiede des Knotens von seinen Nachbarmittelpunkten. Die scheint mir im Chaos-Bereich ganz schlimm zu sein.
Oha, warum wieder mit Mittelpunkten mitteln? Die Entfernungen des Knotens zu allen umliegenden Knoten anschauen (nach Entfernung gewichtet) und die müssen klare Cluster bilden. 3 in Normalentfernung, 6 in einem Winkelschritt, dann wieder 3, dann 6, und dann wirds mir zu kompliziert.
-
Ich wusste, dass die erste Antwort von dir sein würde und das sie gut sein würde
."Hough-Transformation". Das ist so ein Begriff, den ich hier im Forum schon mehrmals gelesen habe, aber nie wusste, was er bedeutete und auch nicht nachgeschlagen habe, weil es immer in Threads zu Bildverarbeitung war (was mich nicht sonderlich interessierte). Das ist ein nützliches Stichwort für mich. So ein Kombi-Studium Physik/Informatik wäre wirklich sehr nützlich für mich gewesen, einfach damit man solche Begriffe kennt. Letztlich könnte man so viel mehr mit Messdaten in den Naturwissenschaften machen, wenn sich die Naturwissenschaftler bloß besser mit Datenverarbeitung auskennen würden. Ich, der ich auf der Grenze zwischen beiden stehe, bekomme das immer wieder mit.
Ein paar der Gedanken, die du hattest, hatte ich auch schon, andere wiederum nicht. Sehr nützlich. Ich wäre zum Beispiel wohl nicht so schnell auf die Idee gekommen, die langen Geraden anzusehen, weil ich mit meinem Bildungshintergrund viel zu sehr gewohnt bin, in Mittelwerten und Abweichungen zu denken. Dafür hatte ich natürlich schon all die Ideen, die du auch zu diesem Thema hast.
Konkret umgesetzt habe ich hiervon noch keine Idee, es mag also sein, dass deine 3. Idee wirklich gut ist. Die hatte ich nämlich auch schon als guten Kandidaten im Kopf, aber noch lange nicht so gut, dass ich mir gesagt hätte "Das ist es!" und es spontan einprogrammiert hätte. Alle diese Ideen bedeuten doch recht viel Programmieraufwand und bedürfen durchaus halbwegs guter Planung bezüglich der Datenstrukturen und Algorithmen. Deswegen wollte ich nicht vorschnell handeln, bloß um hinterher die Arbeit eines ganzen Nachmittags (oder eventuell sogar mehr) wegwerfen zu müssen, weil die Grundidee nichts taugt.
P.S.: Jetzt wo ich lese, wie eine Hough-Transformation funktioniert: Ich hatte ähnliche Gedankengänge. Hab's nur nicht durchziehen können (zumindest nicht in den paar Stunden, die ich darüber nachgedacht habe). Gut zu wissen, dass ich nicht ganz dumm bin und auf solche Verfahren prinzipiell selber kommen könnte
. Aber noch besser ist es zu wissen, wie es wirklich richtig geht 
.
-
SeppJ schrieb:
Aber wie kann ich ausdrücken, wie "verzerrt" das Hexagongitter ist? Da müssen also irgendwie Längen und Winkel einfließen.
Spontaner Gedanke: Varianz der Diagonalen bzw. Differenz der Längen der längsten und kürzesten Diagonale
Durch was für eine Art Datenstruktur wird das Polygonnetz denn repräsentiert?
-
dot schrieb:
Durch was für eine Art Datenstruktur wird das Polygonnetz denn repräsentiert?
Wie in meiner vorherigen Antwort beschrieben, noch durch keine, da bei den zur Verfügung stehenden Optionen jede spezielle Wahl der Datenstruktur, die Wahl der Messungen, die man effizient darauf durchführen kann, beeinflussen würde. Daher habe ich noch nichts in dieser Richtung implementiert, bevor ich mich nicht für die Messmethode entschieden habe.
Derzeit ist es bloß eine Punktwolke. Nur für das gezeigte Bild wurden anhand einer Messreihe auch mal Kanten produziert.
-
Wenn es noch etwas kombinatorischeres sein darf: Schau dir den zugehörigen Graph mit der planeren Einbettung an. Die Facettengrößen dürften auch einen gewissen Aufschluss geben. Das ignoriert natürlich geometrische Verzerrungen, dürfte dafür aber reichlich robust und auch sehr effizient sein.
Letztlich hängt es aber natürlich davon ab was Du unter "verzerrt" verstehst.
-
Frage: Haben die Kanten eine besondere Bedeutung oder dienen sie nur der Visualisierung und letztendlich geht es um die Messpunkte?
Falls sie keine Bedeutung haben, koennte man ja auch ein anderes Netz konstruieren. Es gibt zum Beispiel jede Menge Literatur zu Triangulierungen. Ich bin mir sicher, dass in dem Zusammenhang auch viele Untersuchungsverfahren bezueglich der Regelmaessigkeit entstanden sind. Andererseits: Wenn die Kanten keine besondere Bedeutung haben, sollte man sich vielleicht ausschliesslich auf die Messpunkte konzentrieren.
Eine Hough-Transformation fuehrt man durch, um bestimmte geometrische Strukturen, wie zum Beispiel Geraden, in Bildern zu detektieren. Ich denke nicht, dass Du das brauchst. Du generierst die Geraden selbst, weisst also von Anfang an, was vorhanden ist.
Falls die Kanten eine Bedeutung haben, haben vermutlich auch die jeweils eingeschlossenen Bereiche eine Bedeutung. Vielleicht kann man ueber diese Bereiche ganz gute Aussagen machen: Man koennte zuerst einen Mittelpunkt bestimmen und sich dann zum Beispiel bei den Eckpunkten angucken, wie sie sich im Abstand zum Mittelpunkt unterscheiden und wie der Winkel am Mittelpunkt zwischen den Verbindungslinien zwischen 2 benachbarten Eckpunkten jeweils aussieht. Bei perfekten gleichseitigen Sechsecken waeren beide Groessen fuer alle Eckpunkte und alle benachbarten Paare von Eckpunkten identisch. Wenn man Abweichungen von dieser Form hat, dann sieht man da Unterschiede.
EDIT: Sehe gerade, dass volkards Ideen teilweise auch in die Richtung gingen, die ich hier zuletzt vorgeschlagen habe. Ich glaube, das ist ein guter Ansatzpunkt.
-
SeppJ schrieb:
Genauer gesagt, sind die Eckpunkte gemessen und die Kanten sind dann eingezeichnet als Verbindungen zwischen den Punkten bis zu einem festen Maximalabstand.
Dann sind die "wilden" Bereiche ja evtl überhaupt nicht soo wild, wie sie mit dieser Kantensetzung aussehen. Insbesondere kann man die so erzeugten Flächen kaum hernehmen zum Weiterrechnen. Kannste die selben Punkte nochmal zeigen aber ohne Kanten?
(Ich stelle mir dann mal vor, es sei ein per Lektronenmikroskop geschossenes Bildchen von Graphen und es ginge darum, abzuschätzen, wie gut der Herstellungsprozess war, also Krummheit eher irrelevant, viel wichtiger zu schauen, ob jeder Knoten drei Nachbarn hat. (Im Kantenbildchen hat einer sogar 6 Nachbarn und manche haben nur 2.))
-
Falls die Kanten, Flaechen eine Bedeutung haben, solltest Du Dir vielleicht auch den dualen Graphen angucken. In dem koennten die Informationen, die Du suchst, viel expliziter auftreten.
-
Ich hätte mir einfach mal alle Vielecke angeschaut und deren Eigenschaften aufgeschrieben:
- Anzahl Seiten
- Mittelpunkt
- Fläche
- Position der EckpunkteDann kann man global versuchen, aus den Mittelpunkten Geraden zu bilden (volkards displacement Idee).
Die lokale Unordnung findet man raus in dem man die Anzahl Seiten zählt und die Abweichung zum nächstbesten regulären Vieleck berechnet.(Ich nehme mal an, dass der hexagonale Teil global gesehen perfekte Struktur hat)
-
Die Kanten sind semi-echt. Die eigentlichen Daten enthalten die Kanten nicht, es ist wirklich nur eine Punktwolke und sieht so aus:
http://postimg.org/image/62av0620t/
Die Maximallänge, anhand derer die Kanten erzeugt wurden hat jedoch durchaus eine gewisse Bedeutung. Man kann die Kanten also durchaus rechtfertigen, selbst wenn sie erst im Nachhinein erzeugt wurden. Es wäre mir aber durchaus auch recht, nur auf den Punkten zu arbeiten.Da habe ich auch spontan eine Idee: Man könnte ein Hexagongitter an das Muster fitten und dann messen, wie weit der nächste gemessene Punkt vom Idealgitter entfernt ist. Die Idee ist noch nicht ganz ausgereift, weil sie mir gerade beim Schreiben kommt. Zu Klären wäre beispielsweise, wie der erste Schritt genau abläuft, insbesondere, wenn man viele Fehlstellen im Gesamtmuster hat.
