Algorithmus gesucht
-
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.