Beste Gerade durch Punktmenge mit Translation |
| 04.05.2011, 20:36 | Iridium | Auf diesen Beitrag antworten » | ||||||
| Beste Gerade durch Punktmenge mit Translation Hab mal wieder ein geometrisches Problem: Kennt jemand einen Algorithmus, um zu einer vorgegebenen Punktmenge in drei Dimensionen die beste Gerade zu finden, so daß jeder Punkt einmal passiert wird? Randbedingung (die das Problem erschwert, ansonsten habe ich nämlich schon einen Algorithmus gefunden): Die Punkte liegen innerhalb einer Elementarzelle eines Gitters und die Gerade schneidet den Ursprung und einen weiteren Gitterpunkt mit positiven Koordinaten (dies ist allerdings nur eine Einschränkung, die der Bequemlichkeit halber getroffen wird und nicht absolut zwingend ist). Die Punkte haben dann alle Koordinatenwerte größer als Null und kleiner als 1, es soll sich also um ein primitives Gitter handeln (nicht-primitive können vorher ja auf primitive zurückgeführt werden). Ansatz von mir: Bestimme alle möglichen Differenzvektoren zwischen zwei Punkten bzw. ihren Translationsäquivalenten und prüfe auf (annähernde) Parallelität. Allgemein würde man wohl, ähnlich wie im zweidimensionalen Fall, einen Differenzvektor bestimmen, der senkrecht auf der Geraden steht und dessen Betrag minimieren (d.h. genauer die Fehlerquadratsumme daraus). Gruß |
||||||||
| 05.05.2011, 07:50 | Hubert1965 | Auf diesen Beitrag antworten » | ||||||
Eine Gerade ist immer durch zwei verschiedene Punke vollständig bestimmt. Diese beiden Punkte sind, gemäß deinen Vorgaben:
Diese Gerade wird aber höchstwahrscheinlich nicht alle Punkte deiner Punktmenge passieren, sondern im wahrscheinlichsten Fall gar keinen. |
||||||||
| 05.05.2011, 17:02 | Iridium | Auf diesen Beitrag antworten » | ||||||
Ja, das ist an sich richtig, aber ich kenne nicht die Koordinaten des anderen Gitterpunktes, also nützt mir dies alleine nicht viel.
Auch das stimmt. Aber ich habe ganz bewusst nicht geschrieben, daß die Gerade alle Punkte "schneidet" oder "tangiert" oder so etwas. Es geht nur um die bestmögliche Annäherung an die Menge der Gitterpunkte, bei minimaler Länge der Gerade und der Bedingung, daß alle Punkte eben einmal "passiert" werden, d.h. nicht notwendigerweise auf der Geraden liegen müssen. Wenn sie dies trotzdem tun, umso besser. |
||||||||
| 05.05.2011, 19:10 | Hubert1965 | Auf diesen Beitrag antworten » | ||||||
Achso, du suchst eine Ausgleichsgerade. Regel Nummer 1 für alle Arten Ausgleichsgeraden zu berechnen: Die Ausgleichsgerade geht IMMER durch den Schwerpunkt aller Punkte. Die x-Koordinate des Schwerpunkts berechnest du, indem du die x-Koordinaten aller Punkte addierst, und diese Summe durch die Anzahl der Punkte teilst. Sinngemäß dasselbe gilt für alle anderen Koordinaten. Falls deine Punkte unterschleidlich "wichtig" sind, kannst du ihnen auch Gewichte zuordnen. Wie du das machst, bleibt ganz deiner Phantasie überlassen. Aber es verändert natürlich die Art, den Schwerpunkt zu berechnen: Du addierst jetzt nicht die x-Koordinaten, sondern bildest als ersten Schritt pro Punkt das Produkt aus der x-Koordinate und dem Gewicht des Punktes. Diese Produkte summierst du. Parallel dazu summierst du auch die Gewichte allein (ohne sie mit irgendetwas zu multiplizieren). Am Ende teilst du die Summe der Produkte durch die Summe der Gewichte. Damit erhältst du das gewichtete Mittel der x-Koordinaten, und das ist dann die x-Koordinate des gewichteten Schwerpunkts. Analog verfährst du für die anderen Koordinaten. (Die Summe der Gewichte musst du aber natürlich nur einmal berechnen und dir dann merken) Wenn du dann noch weißt, dass die Gerade genau durch den Koordiantenursprung gehen musst, hast du mit dem Schwerpunkt und dem Koordinatenursprung bereits alles beisammen um die Ausgleichsgerade zu bestimmen. |
||||||||
| 06.05.2011, 18:33 | Iridium | Auf diesen Beitrag antworten » | ||||||
Ja und Nein. Das was du sagst, stimmt schon. Aber das Problem ist diffiziler. Also...am Anfang gegeben sind: Der Ursprung (trivial), n Punkte (x,y,z) mit 0 < x,y,z < 1, sowie ein weiterer Gitterpunkt, von dem man aber die Koordinaten nicht kennt, sie müssen nur ganzzahlig (und der Bequemlichkeit halber) positiv sein. Die gesuchte Ausgleichsgerade soll jetzt UNTER BERÜCKSICHTIGUNG DER TRANSLATION bestimmt werden. D.h. es kann sein, daß der erste Punkt innerhalb der gegebenen Punktmenge zu suchen ist (x,y,z = 0,..., 0,..., 0,...), der nächste Punkt kann aber schon in einer benachbarten Zelle liegen (x,y,z = 1,..., 1,..., 0,...) usw. D.h. um den Schwerpunkt korrekt berechnen zu können, müsste man wissen, welche Punkte bzw. translationsäquivalente Punkte man zu einer Menge neu zusammenfassen muß. Wenn man das weiß, dann hat man aber auch schon das Problem gelöst. Es gibt Algorithmen für eine dreidimensionale Punktmenge. Aber ich habe keinen gefunden, für eine dreidimensionale Punktmenge, die sich dreidimensional periodisch wiederholt. Im Prinzip würde mir auch einfach reichen, ob man eine obere Grenze festlegen kann, wie weit um den Ursprung herum man suchen muß. Dann könnte man einfach zwischen allen Punkten innerhalb dieser Kugel die Differenzvektoren berechnen und darauf prüfen, ob diese parallel oder annähernd parallel zueinander sind (z.B. via Dachprodukt der geometrischen Algebra). Aber ich habe keine Vorstellung, ob es so eine Grenze gibt (abhängig von der Punktanzahl am Anfang), oder nicht, und wenn ja, wie man sie findet. Gruß |
||||||||
| 06.05.2011, 19:46 | Hubert1965 | Auf diesen Beitrag antworten » | ||||||
Das ergibt unendlich viele Punkte, die in alle Richtungen unendlich weit verstreut sind, und die ab einer bestimmten Skalengröße überall gleich dicht den Raum ausfüllen. In diesem Fall ist jede beliebige Gerade gleich gut oder schlecht wie jede beliebige andere. Oder suchst du nach einer Parallelenschar, bei der die Abstände der Punkte zur jeweils nächstgelegenen Geraden im Mittel minimal sind? |
||||||||
| Anzeige | ||||||||
|
|
||||||||
| 06.05.2011, 21:47 | Iridium | Auf diesen Beitrag antworten » | ||||||
Bei so großen Skalen, daß die Punkte den Eindruck erwecken, dicht im Raum zu liegen, mag das sein. Trotzdem liegen die Punkte ja selbst dann nur scheinbar dicht im Raum. Tatsächlich gibt es unendlich viel mehr Stellen, an denen kein Punkt liegt.
Kann sein, daß ich das suche. Klar, wenn es eine Gerade gibt, dann gibt es unendlich viele Geraden, die parallel dazu verlaufen, und da man den Ursprung des Gitters willkürlich wählen kann, erfüllen alle unter Umständen die Randbedingungen. Aber man gehe mal davon aus, daß man einen Gitterpunkt als Ursprung definiert, dann sollte es immer noch nur eine Gerade geben, die alle Bedingungen erfüllt. Im Grunde ist auch die Gerade gesucht, die sowohl dicht bei den Punkten liegt, als auch insgesamt eine minimale Länge aufweist, vom Ursprung zu dem zu bestimmenden Gitterpunkt, und dabei eben alle vorgegeben Punkte erfasst (im Sinne einer Annäherung oder eines Schnittes). Wahrscheinlich gibt es immer noch mehrere Möglichkeiten, dann wäre die Gerade zu bevorzugen, die möglichst viele Bedingungen gleichzeitig erfüllt. Evtl. würde man auch nur dann die Lösungsmenge auf ein Beispiel beschränken, wenn man die Genauigkeit vorgibt. Das sind alles sicher wichtige Fragen, aber ich wäre schon froh überhaupt einen Algorithmus zu finden, der irgendeine Lösung liefert. Von mehreren Lösungen lässt sich dann die "Beste" vielleicht von Hand auswählen. Gruß |
||||||||
| 07.05.2011, 07:56 | Hubert1965 | Auf diesen Beitrag antworten » | ||||||
Ähm. 
Gerade - minimale Länge??? Diese Dinger sind unendlich lang. Da kann man keine Länge minimieren. Jedesmal wenn ich dir hier etwas schreibe, antwortest du mit neuen, bisher unveröffentlichten Fakten über dein Projekt, die ich bisher natürlich (aus Unkenntnis) nicht berücksichtigen konnte. Ich habe den Eindruck, noch immer nicht verstanden zu haben, was du eigentlich wirklich willst. Heute ist Samstag. Nimm dir über das Wochenende vor, dein Problem in mathematischer Präzision, vollständig und trotzdem knapp zu formulieren. Die Sprache der Mathematik stellt dir tausende Begriffe mit exakten widerspruchsfreien Definitionen zur Verfügung. Verwende diese Begriffe! Schlage aber vorher deren genaue Bedeutung nach (z.B. in Wikipedia) und verwende die Begriffe nur in genau der definierten Bedeutung! Wenn du z.B. bei Wikipedia nachschaust, was eine Gerade ist, wirst du als allererstes diese beiden Sätze lesen: "Eine gerade Linie oder kurz Gerade ist ein Element der Geometrie. Darunter hat man sich anschaulich eine unendlich lange, unendlich dünne Linie vorzustellen." Damit ist schon mal klar, dass das kein Ding sein kann, das eine minimale Länge haben kann weil es sonst nicht unendlich lang wäre. Also solltest du den Begriff "Gerade" nicht für etwas verwenden, dass eine Länge hat, die minimiert werden kann. |
||||||||
| 07.05.2011, 08:55 | Iridium | Auf diesen Beitrag antworten » | ||||||
Ich bin der Meinung alle relevanten Fakten waren bereits im ersten Posting vorhanden und wurden bloß nicht ausreichend zur Kenntnis genommen! Der Rest war nur Erläuterung. Ich weiß auch, daß Geraden keine Längenbeschränkung haben. Aber ich habe mein Problem explizit als eines formuliert, und zwar von Anfang an, das auf Translationsperiodizität beruht. Wenn die gesuchte Gerade also einmal durch den Ursprung geht und ein zweites Mal durch einen zweiten Gitterpunkt, dann ist es für mich völlig ausreichend (und ich dachte für einen Mathematiker auch selbsterklärend), daß man nur diesen endlichen Bereich, genauer also ein Geradensegment, betrachten muß. Alles andere wiederholt sich doch. Insofern war das ungenau. Daß ich aber trotzdem sehr genau darüber nachdenke, wie ich formuliere, erkennt man vielleicht daran, daß ich von Anfang nicht davon gesprochen habe, daß die Gerade die Punkte "schneidet", sondern "passiert". Das ist zwar kein mathematischer Fachbegriff, trifft aber die Situation. Vielleicht sollten Mathematiker mal darüber nachdenken, daß sie mit ihren Definitionen und ihrer Strenge ungefähr 90% aller interessanten und praktisch relevanten Fälle übersehen. Im übrigen formulierst du auch nicht so viel genauer...das mit den dicht liegenden Punkten infolge einer Skalierung des Gitters ist z.B. ein Problem der visuellen Darstellung, mathematisch liegt da nichts "dicht". Was ich also nicht tun werde (obwohl ich Wikipedia, Wolfram MathWorld usw. kenne), ist, meine Frage so zu formulieren, wie Russell und Whitehead das getan haben. So schwierig ist die Problemstellung auch nicht, daß man sie hinter vielleicht präzisen aber völlig unverständlichen und wenig hilfreichen Definitionen verstecken müsste. Das Problem also noch mal in leicht veränderter Formulierung: Gegeben sind: n Punkte (x,y,z) in einer Elementarzelle eines dreidimensionalen Gitters (d.h. 0 < x,y,z < 1) Gesucht ist: Das Geradensegment minimaler Länge, das durch den Ursprung (0,0,0) und einen weiteren, noch zu bestimmenden, Gitterpunkt (u,v,w) definiert wird und das die vorgegebenen Punkte (0,... , 0,..., 0,...), bzw. deren Translationsäquivalente (m,... , n,..., l,...), im Sinne einer Ausgleichsgeraden, bestmöglicht annähert bzw. im Idealfall schneidet, und zwar für jeden Punkt genau einmal. Ich versuche außerdem mal eine Skizze für den zweidimensionalen Fall zu machen, dann ist das Problem denke ich, auch ohne strikte Definitionen, klar. Gruß |
||||||||
| 07.05.2011, 08:58 | Iridium | Auf diesen Beitrag antworten » | ||||||
Hier mal die Skizze für den zweidimensionalen Fall, mit der Besonderheit, daß alle Punkte auf einem Untergitter liegen (im Prinzip kann dieses Untergitter aber eine beliebig kleine Zelle haben, so daß eine quasi zufällig verteilte Punktmenge ebensogut auf diese Weise beschrieben werden kann). Jedenfalls werden alle Punkte des Untergitters nacheinander einmal geschnitten, bevor dann mit dem Punkt (1,-4) ein weiterer Gitterpunkt geschnitten wird (die Nomenklatur entstammt einem dreidimensionalen Beispiel mit z = 0, davon nicht verwirren lassen). Gruß |
||||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
