Algorithmus gesucht
-
Na, ich würde mal sagen, erstmal alle Punktabstände berechnen (wird einem wohl nicht erspart sein) und dann der Größe bzw. Abstand nach sortieren lassen. Nach der Sortierung hast ne Liste, die man nicht nur nach dem größten Abstand sondern auch kleinsten auswerten kann.
Aber ich bin kein Algorithmus-Profi...
-
@BarnieGeroellheimer
Genau so habe ich es ja bisher gemacht, aber nun geht es mir darum, die Rechenzeit zu reduzieren.
@Tippgeber
Habe grade etwas gegoogelt. Das Problem ist folgendes: Der Graham Scan als auch der Jarvis March Algorithmus funktionieren scheinbar nur für Punkte auf einer Ebene, also im zweidimensionalen.
-
cplusplus_anfaenger schrieb:
@BarnieGeroellheimer
Genau so habe ich es ja bisher gemacht, aber nun geht es mir darum, die Rechenzeit zu reduzieren.
@Tippgeber
Habe grade etwas gegoogelt. Das Problem ist folgendes: Der Graham Scan als auch der Jarvis March Algorithmus funktionieren scheinbar nur für Punkte auf einer Ebene, also im zweidimensionalen.
Ok, da hätte ich vorher mal besser nachgesehen ob die auch im höherdimensionalen funktionieren.
Ich habe gerade wenig Zeit sonst würde ich selber nachschauen, aber wenn du man nach Algorithmen für die konvexe Hülle suchst, solltest du auch Algorithmen für die Berechnung der Hülle im dreidimensionalen finden.
-
Für den 3-dim Fall gibt es viele verschiedene Algorithmen heisst es.
Welcher würde sich für meinen Fall am besten eignen ? n ist bei mir sehr groß und es sollte auch h<<n gelten, da sich die Punkte einigermaßen homogen innerhalb eines Kreises verteilen.
-
Eine Vereinfachung wäre es vermutlich den 3D-Raum in zahlreiche Würfel aufzuteilen, die sich jeweils halb überschneiden. Diesen weist du dann jeweils die Punkte zu die da drin sind (ein Punkt kann also in mehreren Würfeln sein). Dann brauchst du nur noch Punkte in einzelnen Würfeln vergleichen. Sollte nur einer drin sein, mit den benachbarten Würfeln testen.
Ein ganz wichtiger Punkt, unabhängig davon: Bei der Distanzberechnung auf keinen Fall die eigentliche Distanz berechnen, sondern die quadrierte oder in diesem Fall, ähm, kubierte(?) Version. Denn das Ziehen der Wurzeln ist ja bei simplen Vergleichen von Distanzen unnötig, das Verhältnis verändert sich ja nicht. Spart enorm viel Rechenzeit.
-
Ein ganz wichtiger Punkt, unabhängig davon: Bei der Distanzberechnung auf keinen Fall die eigentliche Distanz berechnen, sondern die quadrierte oder in diesem Fall, ähm, kubierte(?) Version. Denn das Ziehen der Wurzeln ist ja bei simplen Vergleichen von Distanzen unnötig, das Verhältnis verändert sich ja nicht. Spart enorm viel Rechenzeit.
Ja, das ist ein guter Tip.
(kubieren braucht man übrigens nicht bei der Distanzberechnung
)
-
cplusplus_anfaenger schrieb:
(kubieren braucht man übrigens nicht bei der Distanzberechnung
)Das ist der Nachteil wenn man bisher nur in der 2D-Simulation tätig war: Man hat von sowas keine Ahnung.
-
Bin nun auf den Chan Algorithmus gestoßen, wie wäre es damit, oder gibt es für meinen Fall (n sehr groß, h<<n) noch effizientere Algorithmen ?
-
Wäre natürlich schön, wenn es den Chan Algorithmus irgendwo als C++ source code gäbe .............
-
cplusplus_anfaenger schrieb:
Wäre natürlich schön, wenn es den Chan Algorithmus irgendwo als C++ source code gäbe .............
Jo, ich hab noch nicht einmal das Paper gefunden, scheint es nur in diesem Magazin zu geben.
So wie ich den englischen Wiki-Artikel verstehe basiert der Algorithmus auf Jarvis March, da stelle ich mir die Frage wie der im 3dimensionalen damit arbeiten will. Gibt dort ja einen Artikel verlinkt, aber nur auf eine Zitatseite und mehr als sich gegenseitig verlinkende Zitatseiten habe ich auch nicht finden können.
-
-
Da ich in 3 Minuten Feierabend habe ganz kurze Idee dir mir gerade einfällt:
Voraussetzung: Eine Funktion zum Prüfen ob ein Punkt in einem Raum definiert durch N Punkte ist.
Man nimmt den obersten Punkt und verbindet ihn mit den beiden anderen "obersten" Punkte (Z-Wert). Das ist das Ausgangsobjekt. Nun nimmt man nach und nach den nächsten "obersten" Punkt und prüft ob er drin ist. Vermutlich nur eine Erweiterung der Polygongeschichte (Strahl zum Punkt schneidet mit ungerade Anzahl Kanten, dann ist der Punkt im Polygon).
So, jetzt aber Feierabend.
-
Ok, also hier ist Chan's Paper und hier ist Chan's Paper über die konvexe Hülle im 2 und 3 dimensionalen in letzterem findest du auch für beide 2 Pseudocodes, aber es ist wirklich Pseudocode, das heißt du hast da schon noch gut was zu tun den in C++ umzusetzen
-
http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html
Unter "Implementation" gibt es auch einen Link zum Source Code. Ist zwar Java und chaotisch aber vielleicht hilft es.
-
Es gibt ja verschiedene Internetseiten, z.B. die Seite von numerical repecies (http://sdu.ictp.it/nr/index.html) oder Wykobi, auf denen C++ Scripts fuer bekannte mathematische Probleme angeboten werden. Teilweise auch kostenpflichtig. Gibt es da Angebote, die zu empfehlen sind ? Wäre natuerlich auch schon, wenn ich den Chan Algorithmus nicht selber schreiben müßte
-
Ich habe auf die schnelle folgendes gefunden: http://portal.acm.org/citation.cfm?id=610076.610085&coll=portal&dl=ACM
dort werden viele schnelle Methoden für 3d referenziert, beispielsweise http://portal.acm.org/citation.cfm?id=314693&dl=ACM&coll=portal
Außerdem gibt es einen Algorithmus, der zwar nicht theoretisch besser ist als O(n^2), aber in der Praxis wohl sehr gut funktioniert... und zu dem gibt's auch eine Implementierung: http://valis.cs.uiuc.edu/~sariel//papers/00/diameter/diam_prog.html
Mit der konvexen Hülle würde ich eher nicht arbeiten, die Algorithmen dafür sind meist recht heftig... und dann hast Du Dein Problem trotzdem noch nicht gelöst. Ich denke mit den Suchbegriffen "diameter point set" lässt sich noch einiges mehr an Material finden.
-
Mit der konvexen Hülle würde ich eher nicht arbeiten, die Algorithmen dafür sind meist recht heftig... und dann hast Du Dein Problem trotzdem noch nicht gelöst.
Ja, ich denke ich müßte danach noch den maximalen Abstand auf herkömmliche Art herausfinden, wobei ich nur noch Punkte auf der konvexen Hülle berücksichtige. Da diese Zahl dann aber doch recht klein ist (ich vermute mal weniger als 100 Punkte bei anfangs 300 Millionen bei gaussföriger Verteilung), müßte das dann relativ schnell gehen.
Wegen der angegebenen Implementierung bin ich etwas skeptisch, was die Geschwindigkeit betrifft, da meine Punkte in etwa zylindersymmetrisch verteilt sind und der Durchmesser (maximaler Abstand) um 3 Größenordnungen variieren kann.
-
cplusplus_anfaenger schrieb:
Wegen der angegebenen Implementierung bin ich etwas skeptisch, was die Geschwindigkeit betrifft, da meine Punkte in etwa zylindersymmetrisch verteilt sind und der Durchmesser (maximaler Abstand) um 3 Größenordnungen variieren kann.
Dein Einwand verstehe ich nicht. Aber ich würd's einfach mal schnell ausprobieren. Der Code ist sogar in C++ geschrieben und es gibt ein Beispiel, sieht nicht besonders schwer zu benutzen aus, das dürfte sich schnell mal machen lassen. Danach weißt Du ob Skepsis berechtigt ist.
-
Wegen der angegebenen Implementierung bin ich etwas skeptisch, was die Geschwindigkeit betrifft, da meine Punkte in etwa zylindersymmetrisch verteilt sind und der Durchmesser (maximaler Abstand) um 3 Größenordnungen variieren kann.
Dein Einwand verstehe ich nicht
Auf der Internetseite steht:
The code provided below can do the following things: ... Approximate the diameter of a point-set up to a prespecified approximation parameter.
D.h. ich muß also ein Parameter angeben, also ich denke mal eine Art maximal möglichen Durchmesser. Je größer dieser Wert ist, desto größer der Rechenaufwand.
Außerdem steht dort sinngemaess, dass im "worst case" die Rechenzeit quadratisch mit der Anzahl der Punkte ansteigt.
Die kugelsymmetrische Verteilung ist bei solchen Problemen in der Regel der "worst case", diese liegt zwar nicht vor, aber ich habe immerhin eine hohe Zylindersymmetrie vorliegen.Ok, aber ich werde es trotzdem mal ausprobieren, da es ja schon netterweise in der richtigen Programmiersprache vorliegt.