Mittlerer Abstand zweier Punkte auf einer Fläche oder im Raum

20.10.2013, 16:39

-ItsMe-

Auf diesen Beitrag antworten »

Mittlerer Abstand zweier Punkte auf einer Fläche oder im Raum

Ich würde gerne den mittleren Abstand zweier Punkte auf einem Rechteck und in einem Quader berechnen. Allgemein für alle geometrischen Objekte würde gelten: Den Mittelwert aller auftretenden Abstände berechnen. Dazu muss man die Abstände jedes Punkts im Objekt von jedem anderen Punkt im Objekt addieren und durch die Zahl der Abstände teilen.

P beschreibe ein geometrisches Objekt in einem Koordinatensystem mit den Koordinaten
$\begin{eqnarray*} x_1, x_2, x_3, ..., x_n \end{eqnarray*}$

Dann ist d_0 der Abstand zweier beliebiger Punkte im Objekt:

$\begin{eqnarray*} d_0 = |P(x_1', x_2', x_3', ..., x_n')-P(x_1, x_2, x_3, ..., x_n)| ; a_k \leq x_k, x_k' \leq b_k <br /> \end{eqnarray*}$

Wenn ich die Mittelwert-Summen für die Abstände aufstelle, dann kann ich die auch in Integrale umformen. Ich komme so auf folgendes Mehrfachintegral für die Berechnung des mittleren Abstands d:

$\begin{eqnarray*} d = \prod\limits_{k=1}^{n} \frac{1}{(b_k-a_k)^2} \cdot \int_{a_n}^{b_n} \, dx_n' \int_{a_n}^{b_n} \, dx_n \, ... \int_{a_1}^{b_1} \, dx_1' \int_{a_1}^{b_1} \! d_0 \, dx_1 \end{eqnarray*}$

In der Berechnung von d für ein Rechteck mit den Seiten a und b würde das Integral dann so aussehen:

$\begin{eqnarray*} d = \frac{1}{a^2 \, b^2} \cdot \int_{0}^{b} \, dy' \int_{0}^{b} \, dy \int_{0}^{a} \, dx' \int_{0}^{a} \! \sqrt{(x'-x)^2+(y'-y)^2} \, dx \end{eqnarray*}$

Und spätestens ab da komme ich nicht weiter. Das erste Integral kann ich vielleicht noch auflösen, aber die nächsten nicht mehr. Bei einem Quader wären es ja sogar 6 Integrale, von daher ist das noch unrealistischer zu berechnen. Wenn ich nur den eindimensionalen Fall betrachte, funktioniert diese Methode ganz gut. Bei einer Strecke mit der Länge a komme ich auf einen durchschnittlichen Abstand von a/3.

Meine Frage lautet nun also: Mache ich das vielleicht zu kompliziert? Geht das einfacher? Oder komme ich um das Mehrfachintegral nicht herum? Gibt es Programme (oder vllt. auch Menschen :p), die das berechnen könnten?

Ich bin Schüler btw., sprich, ich kann vielleicht nicht jeden Lösungsansatz verstehen, werd' mir aber jede Mühe geben.

20.10.2013, 16:46

HAL 9000

Auf diesen Beitrag antworten »

Was du dir überlegt hast, sieht alles sehr vernünftig aus, aber was die analytische Lösung betrifft, kann ich dir nicht viel Hoffnung machen.

Vielleicht solltest du auch andere Wege in Erwägung ziehen:

Monte-Carlo-Integration, geradezu prädestiniert für analytisch schwierige bzw. unmögliche Mehrfachintegrale.

20.10.2013, 20:13

-ItsMe-

Auf diesen Beitrag antworten »

Ich hab' mir den Artikel durchgelesen, kann aber schwer nachvollziehen, wie ich das auf meinen Fall ohne ein Hilfsprogramm anwenden soll ^^

Wenn ich das ganze approximativ lösen soll, könnte ich ja aber doch auch zufällig Punkte im Rechteck generieren lassen und dann den Mittelwert der Abstände bestimmen, oder? Ist dann wohl einfacher und vielleicht auch genauer.

20.10.2013, 21:22

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von -ItsMe-
Wenn ich das ganze approximativ lösen soll, könnte ich ja aber doch auch zufällig Punkte im Rechteck generieren lassen und dann den Mittelwert der Abstände bestimmen, oder?

Das ist doch gerade die Monte-Carlo-Integration. Augenzwinkern

Augenzwinkern

20.10.2013, 21:51

-ItsMe-

Auf diesen Beitrag antworten »

Ja, ergibt dann auch gleich viel mehr Sinn, wenn ich mir das ganze noch mal überlege ^^

Das einzige Problem ist, dass ich so keine allgemeine Formel aufstellen kann, was sehr schade ist :/
Ich kann mir aber nicht so ganz vorstellen, dass sich noch niemand mit der Frage nach dem Mittelwert von Punktabständen auf einem geometrischen Objekt beschäftigt hat. Und irgendwie kann ich auch nicht so ganz glauben, dass es keine allgemeine, bzw. analytische Lösung im Falle eines Rechtecks und eines Quaders gibt. Im eindimensionalen Fall war es jedenfalls so, dass die Lösung des ersten Integrals komplizierter war als die des zweiten. Und da sagt mir mein mathematisches Gespür schon, dass in so einem Falle der Berechnungsansatz zu allgemein gehalten ist. Ich müsste mir aber erst noch überlegen, wie ich den konkreter, bzw. an das Rechteck angepasst machen könnte.

20.10.2013, 22:00

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von -ItsMe-
Und irgendwie kann ich auch nicht so ganz glauben, dass es keine allgemeine, bzw. analytische Lösung im Falle eines Rechtecks und eines Quaders gibt.

Du kannst es natürlich versuchen - das bleibt dir unbenommen. Augenzwinkern

Augenzwinkern

Wenn es um den mittleren quadratischen Abstand geht, ist es übrigens sehr einfach analytisch lösbar - aber der mittlere direkte Abstand ist eben ungleich schwerer. Der Vergleich zu Dimension 1 taugt nur bedingt, da dort noch keine Wurzeln "stören".

Anzeige

22.10.2013, 23:10

-ItsMe-

Auf diesen Beitrag antworten »

Hab jetzt wieder Zeit gefunden und mich daher nochmal damit befasst. Für den quadratischen Abstand ergibt sich im Falle eines Rechtecks für d die einfache Formel:

$\begin{eqnarray*} d = \frac{a^2+b^2}{6} \end{eqnarray*}$

Für die mehr oder weniger nicht lösbaren Integrale beim Rechteck habe ich jetzt, wie du geraten hast, die Monte-Carlo-Methode angewendet und ein paar Datenpaarlisten erstellt. Aus denen hoffe ich dann eine allgemeine Formel ableiten zu können. Das Dumme ist halt, dass ich erst für eine Millionen zufällige Abstände eine Standardabweichung von ~ 0,0375% erhalte und jede Million Berechnungen etwa 4 Sekunden dauern. Sprich, um aus der Liste dann später richtige Annahmen treffen zu können, muss ich den PC wohl irgendwann für ne Nacht zum Rechnen stehen lassen.
Und danach wahrscheinlich nochmal, um die Daten durch Listenerstellen und Regression der Punkte auswerten zu lassen.
Aus den Listen, die ich bis jetzt habe, kann ich jedenfalls einen sehr gleichmäßigen Übergang herauslesen. Anbieten würde sich auf jeden Fall ein quadratischer Zusammenhang (einfache höhere Polynome sicher nicht) - Kann aber natürlich nicht sein, wenn schon der quadratische Abstand quadratisch mit a und b zusammenhängt.

Auf jeden Fall zeigt sich, dass ich mit a/3 im eindimensionalen Fall recht hatte - Wenn sich der Computer bei der MC-Methode nicht verrechnet hat :p Das gibt mir wenigstens Zuversicht gegenüber der oben genannten Formel für das Berechnen der Abstandsmittelwerte ^^

22.10.2013, 23:19

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von -ItsMe-
und jede Million Berechnungen etwa 4 Sekunden dauern.

Da ich einige Erfahrung mit derartigen Simulationen habe: Mit einigermaßen aktueller Hardware müsste das deutlich schneller gehen, vorausgesetzt du nutzt Software, die die Hardware effizient zu nutzen versteht - ich denke da etwa an C/C++. Und solche Simulationen sind auch gut parallelisierbar, d.h. auf mehrere Cores verteilbar, das gibt dann auf modernen Quadcores noch mehr Schub.

22.10.2013, 23:58

-ItsMe-

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Da ich einige Erfahrung mit derartigen Simulationen habe: Mit einigermaßen aktueller Hardware müsste das deutlich schneller gehen, vorausgesetzt du nutzt Software, die die Hardware effizient zu nutzen versteht.

Ja, das kann schon sein. Ich habe das Programm erstmal relativ hastig mit JavaScript in GeoGebra geschrieben, weil ich da natürlich auch gleich günstige Tabellenfunktion, Benutzereingabefunktionen und Graphendarstellung mit drin hab'. Mit C#/C++ habe ich auch schon mal gearbeitet, allerdings müsste ich mich wieder reinlesen :p

23.10.2013, 00:04

HAL 9000

Auf diesen Beitrag antworten »

Ich hab's gerade mal schnell programmiert (hatte schon ein "Gerüst" für derartige Simulationen) - Performance auf meinem betagten Core2Quad Q9550 (Jahrgang 2009, 4 Cores 2.8GHz):

ca 40 Mio Simulationen pro Sekunde bei Nutzung aller 4 Cores

Bei nur 1 Core immerhin noch etwa 15 Mio - scheint also ganz schön was zu bringen.

23.10.2013, 00:26

-ItsMe-

Auf diesen Beitrag antworten »

Okay - Also es steht dir nichts im Wege, ebenso die Formel aus den Simulationen rauszulesen versuchen - Du hast da ja anscheinend ein wenig mehr Erfahrung ^^

23.10.2013, 08:27

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von -ItsMe-
Also es steht dir nichts im Wege, ebenso die Formel aus den Simulationen rauszulesen versuchen

Hehe, ich bin oben schon nicht auf deine diesbezüglichen Spekulationen eingegangen und werde es gewiss nicht übernehmen. smile

smile

Wenn du es denn selbst angehen willst, dann kann sowieso höchstens eine leidlich gute approximative Anpassung das Ziel sein. Es ist kaum denkbar, auf diesem Weg eine exakte Formel zu ermitteln. Man sollte sich nicht durch die leicht berechenbare Formel $\begin{eqnarray*} \frac{a^2+b^2}{6} \end{eqnarray*}$ für den mittleren quadratischen Abstand blenden lassen und meinen, dann müsse es auch für den mittleren Abstand eine einfache geschlossene Darstellung geben.

23.10.2013, 14:26

Huggy

Auf diesen Beitrag antworten »

Für ein Rechteck konnte Mathematica das Vierfachintegral für den mittleren Abstand noch lösen, aber für einen Quader denkt es jetzt schon über eine Stunde nach.

23.10.2013, 14:35

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
Für ein Rechteck konnte Mathematica das Vierfachintegral für den mittleren Abstand noch lösen

Aber auch das ist wohl so lang, dass du es nicht gleich hier angeben konntest? smile

smile

23.10.2013, 14:47

Huggy

Auf diesen Beitrag antworten »

Das passt schon noch hin. Es sei $\begin{eqnarray*} \overline d(a,b) \end{eqnarray*}$ der mittlere Abstand in einem Rechteck mit den Seiten a und b. Dann gilt:

$\begin{eqnarray*} \overline d (a,b )=a\overline d (1, \frac {b}{a} \end{eqnarray*}$

23.10.2013, 15:00

Huggy

Auf diesen Beitrag antworten »

Das passt schon noch hin. Es sei $\begin{eqnarray*} \overline d(a,b) \end{eqnarray*}$ der mittlere Abstand in einem Rechteck mit den Seiten a und b. Dann gilt:

$\begin{eqnarray*} \overline d (a,b )=a \cdot\overline d (1, \frac {b}{a})=a \cdot \overline d(1,\beta) \end{eqnarray*}$

Mit Mathematica ausgerechnet habe ich

$\begin{eqnarray*} \frac {\beta^2}{a} \cdot \overline d(1, \beta) \end{eqnarray*}$

Dabei ist $\begin{eqnarray*} \beta \end{eqnarray*}$ in Mathematica mit $\begin{eqnarray*} b \end{eqnarray*}$ benannt.

[attach]31880[/attach]

23.10.2013, 21:31

-ItsMe-

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
[attach]31880[/attach]

Sicher, dass das Ergebnis stimmt? Das passt irgendwie nicht mit meinen Simulationen zusammen - Und die sind ganz sicher richtig.
Wenn I das Integral ist, dass Mathematica da berechnet hat, dann ist $\begin{eqnarray*} \overline d \end{eqnarray*}$ :

$\begin{eqnarray*} \overline d(a,b) = \frac{a}{\beta^2}\frac{1}{a^2b^2} \cdot I(a,b) = \frac{a}{b^4} \cdot I(a,b) \end{eqnarray*}$

Ist doch so - Oder habe ich etwas falsch verstanden?

24.10.2013, 08:27

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von -ItsMe-
Wenn I das Integral ist, dass Mathematica da berechnet hat, dann ist $\begin{eqnarray*} \overline d \end{eqnarray*}$ :

$\begin{eqnarray*} \overline d(a,b) = \frac{a}{\beta^2}\frac{1}{a^2b^2} \cdot I(a,b) = \frac{a}{b^4} \cdot I(a,b) \end{eqnarray*}$

Ist doch so - Oder habe ich etwas falsch verstanden?

Das hast du falsch verstanden. Es ist

$\begin{eqnarray*} \overline d(a,b)=\frac {a}{\beta^2} \cdot I(1,\beta)=\frac {a^3}{b^2}\cdot I(1,\beta) \end{eqnarray*}$

Der Plot zeigt $\begin{eqnarray*} \overline d(1, \beta) \end{eqnarray*}$ . Bei $\begin{eqnarray*} \beta = 0 \end{eqnarray*}$ ergibt sich 1/3, was mit der Rechnung für eine Strecke der Länge 1 übereinstimmt. Bei $\begin{eqnarray*} \beta =1 \end{eqnarray*}$ ergibt sich ca. 0.521. Das ist das Ergebnis für ein Quadrat der Seitenlänge 1. Passt das jetzt zu deinen Simulationen?

Allgemein: Wenn man $\begin{eqnarray*} \overline d(a,b) \end{eqnarray*}$ aus dem Plot ablesen will, wähle a als die größere Seite. Bestimme dann $\begin{eqnarray*} \beta =b/a \end{eqnarray*}$ . Lies das Ergebnis bei $\begin{eqnarray*} \beta \end{eqnarray*}$ aus dem Plot ab und multipliziere es mit a.

24.10.2013, 10:26

HAL 9000

Auf diesen Beitrag antworten »

Den Wert für $\begin{eqnarray*} \beta=1 \end{eqnarray*}$ kann ich bestätigen: $\begin{eqnarray*} 10^9 \end{eqnarray*}$ Simulationen ergeben 0.5214.

24.10.2013, 16:19

-ItsMe-

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
Das hast du falsch verstanden. Es ist

$\begin{eqnarray*} \overline d(a,b)=\frac {a}{\beta^2} \cdot I(1,\beta)=\frac {a^3}{b^2}\cdot I(1,\beta) \end{eqnarray*}$

Warum hat Mathematica dann deiner Grafik entsprechend nur das Mehrfachintegral der Puntkabstände bestimmt, ohne es mit dem Vorfaktor $\begin{eqnarray*} \frac{1}{a^2b^2} \end{eqnarray*}$ zu versehen? ^^

Zitat:

Der Plot zeigt $\begin{eqnarray*} \overline d(1, \beta) \end{eqnarray*}$ . Bei $\begin{eqnarray*} \beta = 0 \end{eqnarray*}$ ergibt sich 1/3, was mit der Rechnung für eine Strecke der Länge 1 übereinstimmt. Bei $\begin{eqnarray*} \beta =1 \end{eqnarray*}$ ergibt sich ca. 0.521. Das ist das Ergebnis für ein Quadrat der Seitenlänge 1. Passt das jetzt zu deinen Simulationen?

Kann es sein, dass in der Grafik der Plot falsch angezeigt wird? Du redest von 1/3 bei $\begin{eqnarray*} \beta = 0 \end{eqnarray*}$ , allerdings zeigt der Plot was anderes. Die berechnete Funktion für $\begin{eqnarray*} \beta \end{eqnarray*}$ entspricht nicht dem Plot in der Grafik, denn auch Geogebra und Wolframalpha zeigen das anders:

http://www7.pic-upload.de/24.10.13/taclylc1n5g.png

Zitat:

Allgemein: Wenn man $\begin{eqnarray*} \overline d(a,b) \end{eqnarray*}$ aus dem Plot ablesen will, wähle a als die größere Seite. Bestimme dann $\begin{eqnarray*} \beta =b/a \end{eqnarray*}$ . Lies das Ergebnis bei $\begin{eqnarray*} \beta \end{eqnarray*}$ aus dem Plot ab und multipliziere es mit a.

Joa, so hab' ich's mir auch gedacht (Grade ausprobiert - Das stimmt mit den Simulationen überein), allerdings war ich verwirrt, weil im Integral nirgendwo der Vorfaktor $\begin{eqnarray*} \frac{1}{a^2b^2} \end{eqnarray*}$ stand

verwirrt

24.10.2013, 16:26

-ItsMe-

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
aber für einen Quader denkt es jetzt schon über eine Stunde nach.

Hat Mathematica da dann Ergebnisse erzielt?

24.10.2013, 18:11

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von -ItsMe-
Kann es sein, dass in der Grafik der Plot falsch angezeigt wird? Du redest von 1/3 bei $\begin{eqnarray*} \beta = 0 \end{eqnarray*}$ , allerdings zeigt der Plot was anderes. Die berechnete Funktion für $\begin{eqnarray*} \beta \end{eqnarray*}$ entspricht nicht dem Plot in der Grafik, denn auch Geogebra und Wolframalpha zeigen das anders:

http://www7.pic-upload.de/24.10.13/taclylc1n5g.png

Der Plot ist schon richtig. Das Integral habe ich Mathematica ohne Vorfaktoren berechnen lassen. Der Plot zeigt dann das Integral geteilt durch $\begin{eqnarray*} \beta^2 \end{eqnarray*}$ , wie man aus dem Plotbefehl sieht. Und dieser Plot zeigt 1/3 bei $\begin{eqnarray*} \beta=0 \end{eqnarray*}$ . Beachte, dass die horizontale Achse bei 0,35 durch die vertikale Achse geht.

Die Rechnung für den Quader habe ich nach 2 Stunden abgebrochen. Da lag noch kein Ergebnis vor.

24.10.2013, 18:50

-ItsMe-

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
Der Plot ist schon richtig. Das Integral habe ich Mathematica ohne Vorfaktoren berechnen lassen. Der Plot zeigt dann das Integral geteilt durch $\begin{eqnarray*} \beta^2 \end{eqnarray*}$ , wie man aus dem Plotbefehl sieht. Und dieser Plot zeigt 1/3 bei $\begin{eqnarray*} \beta=0 \end{eqnarray*}$ . Beachte, dass die horizontale Achse bei 0,35 durch die vertikale Achse geht.

Die Rechnung für den Quader habe ich nach 2 Stunden abgebrochen. Da lag noch kein Ergebnis vor.

Danke für (beide) Richtigstellung(en) und für die Hilfe, auch @ HAL 9000 ^^

26.10.2013, 14:20

Huggy

Auf diesen Beitrag antworten »

Hier noch am Beispiel von dim-dimensionalen Würfeln der Seitenlänge 1 mit 1 Million Simulationen, wie eine Simulation mit Mathematica aussehen könnte:

[attach]31902[/attach]

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »