Das deutsche Python-Forum

Hi,

Ich programmier mir gerade eine n-Dimensionale virtuelle Realität.
Hier berechne ich zum Beispiel den Schwerpunkt von Polytopen (n-Dimensionale polygone).
Hierzu teile ich das Polytop in Simplexe auf. und berechne dann von jedem simplex den Schwerpunkt
C = \frac{1}{n+1}\sum_{i=0}^n v_i.
Dann berechne ich auch das Volumen von den Simplexen mit mit der Formel 1/n! * det(m) wobei m die punkte sind und n die anzahl der dimensionen ist.
Die schwerpunkte bekommt man ja mit
Cx = 1/(summe_der_gewichte) * (gewicht1*schwerpunkt1[x] + gewicht2*schwerpunkt2[x] [...] )
Cy = 1/(summe_der_gewichte) * (gewicht1*schwerpunkt1[y] + gewicht2*schwerpunkt2[y] [...] )
Weil das Polytop überall die gleiche dichte hat kann ich anstatt des gewichtes auch das volumen vom simplex nehmen.
Der algorithmus funktioniert soweit, nur dauert es für ein 8-eck fast eine halbe sekunde den schwerpunkt zu berechnen.
Habt ihr eine idee wie ich die performance verbessern kann?

Edit: Oder gibt es eine Möglichkeit zu überprüfen wo das programm am längsten hängt/wofür es am längsten braucht? Ein Debugger tuts da ja nicht so richtig oder?

Wenns nur um Polygone geht: schau mal auf http://de.wikipedia.org/wiki/Schwerpunkt

Dort ist auch Information verlinkt http://local.wasp.uwa.edu.au/~pbourke/g ... /polyarea/
Und dort ist auch Python-Code verlinkt.

Für Polygone ist es ja wesentlich einfacher. Mein Problem ist das es auch schnell mit Polytopen funtkionieren soll.
Im 3-D Raum funktioniert ja schon die Formel A = \frac{1}{2}\sum_{i=0}^{N-1} (x_i\ y_{i+1} - x_{i+1}\ y_i) nicht.
Dann habe ich gesehen dass man den Schwerpunkt und das Volumen von Simplexen relativ leicht ausrechnen kann. Um dann den Gesamt Schwerpunkt von einem Polytop auszurechnen muss ich die Schwerpunkte und volumen mit einander kombinieren.
Irgendetwas hierbei ist offensichtlich zeitaufwändig.
Gibt es vielleicht einen besseren algorythmus für Polytope. Kann man den ansatz für polygone vielleicht auf polytope übertragen?

Ich werde nachher mal gucken wo mein programm am längsten hängt und dann mehr darüber sagen.

Hm, ich hab' so was mal für den Schwerpunkt von ~1e5 Atomen gemacht (schnödes Beispiel im karthesischen Koordinatensystem, aber Deinem Problem nicht unähnlich). Das ging recht fix (habe nie gemessen, aber << 0.5 s). Wichtig war,
a) die Schleife so einzuteilen, das Rechnungen nicht unnötig mehrfach durchgeführt werden.
b) numpy arrays der Daten zu haben (viel schneller als Python-Listen)
c) und - ich hatte eine abgeleitete Datenstruktur - die Iteration eben über Iteratoren zu machen, so daß nicht wiederholt im Hintergrund die Elemente übergeben werden müssen

Hast Du ggf. ein Minimalbeispiel für Deine Funktion? Oder zumindest ein kommentiertes kurzes Snippet?

Gruß,
Christian

PS timeit is ein on-board modul zur Messung der Ausführungszeit. Die Python-Seite enhält darüber viele Performance Tips und Profiling-Links.