Ist Punkt in Volumen (gelöst) < Lin. Algebra/Vektor < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 13:48 Fr 25.06.2010 | | Autor: | Mister_J |
| Aufgabe | | Gegeben sind acht Punkte im [mm] R^{3} (P_{i}, [/mm] i = 1 [mm] \cdots [/mm] 8), die die Eckpunkte eines Volumens V beschreiben. Ein weiterer Punkt [mm] P_0 [/mm] liegt ebenfalls im [mm] R^{3}. [/mm] |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo liebe Forenmitglieder,
ich stehe ein bisschen auf dem Schlauch und hoffe, dass ihr mir helfen könnt.
Wie kann ich bestimmen, ob ein Punkt P in einem Volumen V liegt? Geht das irgendwie über Abstandsberechnung?
Die Punkte, die die Eckpunkte des Volumen bestimmen, spannen "quasi" einen Quader auf, jedoch liegt der vierte Punkt einer Quaderseite nicht in der Ebene, die die drei anderen Punkte aufspannen. Des Weiteren kenne ich nicht die Reihenfolge der Punkte.
Hat jemand eine Idee und kann mir einen Tipp geben?
Vielen Dank,
Johannes
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:00 Fr 25.06.2010 | | Autor: | fred97 |
> Gegeben sind acht Punkte im [mm]R^{3} (P_{i},[/mm] i = 1 [mm]\cdots[/mm] 8),
> die die Eckpunkte eines Volumens V beschreiben. Ein
> weiterer Punkt [mm]P_0[/mm] liegt ebenfalls im [mm]R^{3}.[/mm]
> Ich habe diese Frage
Wo ist denn die Frage ?
> in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Hallo liebe Forenmitglieder,
>
> ich stehe ein bisschen auf dem Schlauch und hoffe, dass ihr
> mir helfen könnt.
Ich bin schon lange im Geschäft, aber damit:
" Gegeben sind acht Punkte im $ [mm] R^{3} (P_{i}, [/mm] $ i = 1 $ [mm] \cdots [/mm] $ 8), die die Eckpunkte eines Volumens V beschreiben."
kann ich nichts anfangen. Was verstehst Du unter "Volumen" ?
Ist damit die konvexe Hülle der 8 Punkte gemeint ?
FRED
> Wie kann ich bestimmen, ob ein Punkt P in einem Volumen V
> liegt? Geht das irgendwie über Abstandsberechnung?
> Die Punkte, die die Eckpunkte des Volumen bestimmen,
> spannen "quasi" einen Quader auf, jedoch liegt der vierte
> Punkt einer Quaderseite nicht in der Ebene, die die drei
> anderen Punkte aufspannen. Des Weiteren kenne ich nicht die
> Reihenfolge der Punkte.
> Hat jemand eine Idee und kann mir einen Tipp geben?
>
> Vielen Dank,
> Johannes
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:07 Fr 25.06.2010 | | Autor: | Mister_J |
Hallo Fred,
entschuldige bitte, dass ich mich ungenau ausgedrückt habe. Wie du richtig vermutet hast, ergibt sich das Volumen als konvexe Hülle über die acht Punkte.
Viele Grüße,
Johannes
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:19 Fr 25.06.2010 | | Autor: | fred97 |
> Hallo Fred,
>
> entschuldige bitte, dass ich mich ungenau ausgedrückt
> habe. Wie du richtig vermutet hast, ergibt sich das Volumen
> als konvexe Hülle über die acht Punkte.
so und nun willst Du wissen ob ein punkt p zur konvexen Hülle dieser 8 Punkte gehört ?
Diese 8 Punkte seine [mm] $p_1, [/mm] ..., [mm] p_8$
[/mm]
p gehört zur konvexen Hülle dieser 8 Punkte [mm] \gdw [/mm] es gibt [mm] t_1, [/mm] ..., [mm] t_8 \ge [/mm] 0 mit [mm] $t_1+ ...+t_8=1$ [/mm] und
[mm] $p=t_1*p_1+ ...+t_8*p_8$
[/mm]
FRED
>
> Viele Grüße,
> Johannes
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:25 Fr 25.06.2010 | | Autor: | Mister_J |
Hallo Fred,
nein, ich möchte wissen wie ich berechnen kann, ob ein Punkt [mm] P_{0} [/mm] innerhalb dieses Volumens liegt.
Viele Grüße,
Johannes
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:27 Fr 25.06.2010 | | Autor: | fred97 |
> Hallo Fred,
>
> nein, ich möchte wissen wie ich berechnen kann, ob ein
> Punkt [mm]P_{0}[/mm] innerhalb dieses Volumens liegt.
Meinst Du mit "innerhalb" die inneren Punkte des Volumens ?
FRED
>
> Viele Grüße,
> Johannes
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:33 Fr 25.06.2010 | | Autor: | Mister_J |
Hallo Fred,
ja, genau das.
Johannes
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:08 Fr 25.06.2010 | | Autor: | abakus |
> Hallo Fred,
>
> ja, genau das.
>
> Johannes
Hallo,
das Problem lässt sich sicherlich etwas reduzieren. Der gegebene Körper sollte unter Verwendung der gegebenen Eckpunkte in Teilkörper (Tetraeder) zerlegt werden können.
Dann muss untersucht werden, ob der Punkt in einem der Tetraeder liegt.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:24 Fr 25.06.2010 | | Autor: | Mister_J |
Hallo Abakus,
danke für den Lösungsvorschlag, ich werde dahingehend weitersuchen.
Viele Grüße,
Johannes
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:24 Fr 25.06.2010 | | Autor: | gfm |
> > Hallo Fred,
> >
> > entschuldige bitte, dass ich mich ungenau ausgedrückt
> > habe. Wie du richtig vermutet hast, ergibt sich das Volumen
> > als konvexe Hülle über die acht Punkte.
>
>
> so und nun willst Du wissen ob ein punkt p zur konvexen
> Hülle dieser 8 Punkte gehört ?
>
> Diese 8 Punkte seine [mm]p_1, ..., p_8[/mm]
>
> p gehört zur konvexen Hülle dieser 8 Punkte [mm]\gdw[/mm] es
> gibt [mm]t_1,[/mm] ..., [mm]t_8 \ge[/mm] 0 mit [mm]t_1+ ...+t_8=1[/mm] und
>
> [mm]p=t_1*p_1+ ...+t_8*p_8[/mm]
>
> FRED
> >
Vielleicht hab ich einen Denkfehler, aber das ist es doch schon, was Du sagst.
Daraus resultieren 4 lineare Gleichungen für acht Variablen. Wenn man sie in einander einsetzt, bleibt i.A. am Ende eine Gleichung
[mm] a_1u_1+a_2u_2+a_3u_3+a_4u_4=w
[/mm]
über, wobei die [mm] a_i\in[0,1] [/mm] unter der Nebenbedingung, dass Ihre Summe in [0,1] liegen muss, zu bestimmen sind und die anderen Werte gegeben sind.
Hilft das weiter?
LG
gfm
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:42 Fr 25.06.2010 | | Autor: | Mister_J |
Hallo gfm,
ich bin mir nicht sicher, dass ich dich richtig verstehe. Woraus resultieren 4 lineare Gleichungen und was genau bezeichnest du mit [mm] a_{i}, u_{i} [/mm] und w?
Viele Grüße,
Johannes
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:01 Fr 25.06.2010 | | Autor: | gfm |
> Hallo gfm,
>
> ich bin mir nicht sicher, dass ich dich richtig verstehe.
> Woraus resultieren 4 lineare Gleichungen und was genau
> bezeichnest du mit [mm]a_{i}, u_{i}[/mm] und w?
>
> Viele Grüße,
> Johannes
Beispiel im ebenen Fall
Seien [mm] (x_i,y_i) [/mm] i=1,2,3,4 vier Punkte in der Ebene und (x,y) der Testpunkt. Die konvexe Hülle ist [mm] \summe t_i (x_i,y_i) [/mm] mit [mm] \summe t_i=1 [/mm] und [mm] t_i\in[0,1]. [/mm] Damit (x,y) darin enthalten ist, muss also
[mm] \summe t_i=1
[/mm]
[mm] \summe t_ix_i=x
[/mm]
[mm] \summe t_iy_i=y
[/mm]
gelten.
I.A. folgt daraus eine Gleichung
[mm] a_1t_i+a_2t_k=w [/mm] für zwei [mm] i\not=k, [/mm] wobei [mm] 0\le t_i+t_k\le1 [/mm] sein muss.
Wenn [mm] a_1 [/mm] und [mm] a_2 [/mm] gleiches Vorzeichen haben, dann sind 0 und [mm] a_1+a_2 [/mm] die Extremwerte der linken Seite. w muss dazwischen liegen, wenn es eine Lösung geben soll. Wenn Sie ungleiches Vorzeichen haben, dann kann die linke Seite zwischen [mm] Min(a_1,a_2) [/mm] und [mm] Max(a_1,a_2) [/mm] liegen.
Was meint Ihr?
LG
gfm
|
|
|
| |
|
> Gegeben sind acht Punkte im [mm]R^{3} (P_{i},[/mm] i = 1 [mm]\cdots[/mm] 8),
> die die Eckpunkte eines Volumens V beschreiben. Ein
> weiterer Punkt [mm]P_0[/mm] liegt ebenfalls im [mm]R^{3}.[/mm]
> Die Punkte, die die Eckpunkte des Volumen bestimmen,
> spannen "quasi" einen Quader auf, jedoch liegt der vierte
> Punkt einer Quaderseite nicht in der Ebene, die die drei
> anderen Punkte aufspannen. Des Weiteren kenne ich nicht die
> Reihenfolge der Punkte.
Hallo Johannes,
ist denn über die Anordnung der Punkte im Raum gar
nichts genaueres bekannt ?
Du sprichst von einem "quasi" Quader ... was meinst
du damit ?
Auf welche Weise sind die Koordinaten der einzelnen
Punkte zustande gekommen ?
Wenn du alle Eckpunktskoordinaten hast, könntest du
doch auch mittels einer Zeichnung die Form des Körpers
ermitteln.
Falls nichts über die Anordnung bekannt sein sollte,
kannst du für alle die 70 Tetraeder, welche von je 4 der 8
Punkte aufgespannt werden, testen, ob [mm] P_0 [/mm] in dem
Tetraeder oder auf dessen Rand liegt. Lautet die Antwort
für mindestens eines dieser Tetraeder "Ja", so gehört
[mm] P_0 [/mm] zur konvexen Hülle der 8 Punkte, andernfalls nicht.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:38 Fr 25.06.2010 | | Autor: | Mister_J |
Hallo,
die Punkte ergeben sich durch Abtastung der Eckpunkte eines realen "Quaders" mittels eines Sensors, der die Daten an den Rechner überträgt. Durch kleinste Messfehler bzw. - ungenauigkeiten liegt der vierte Eckpunkt einer Seite nicht zwingend in einer Ebene mit den anderen drei Eckpunkte dergleichen Seite.
Die Reihenfolge der einzelnen Punkte könnte unter Umständen vorher festgelegt werden, wenn ansonsten die Rechenzeit zu lange würde.
Ich denke, ich werde den Ansatz mit den Tetraedern verfolgen.
Vielen Dank und viele Grüße,
Johannes
|
|
|
| |
|
> Hallo,
>
> die Punkte ergeben sich durch Abtastung der Eckpunkte eines
> realen "Quaders" mittels eines Sensors, der die Daten an
> den Rechner überträgt. Durch kleinste Messfehler bzw. -
> ungenauigkeiten liegt der vierte Eckpunkt einer Seite nicht
> zwingend in einer Ebene mit den anderen drei Eckpunkte
> dergleichen Seite.
> Die Reihenfolge der einzelnen Punkte könnte unter
> Umständen vorher festgelegt werden, wenn ansonsten die
> Rechenzeit zu lange würde.
> Ich denke, ich werde den Ansatz mit den Tetraedern
> verfolgen.
>
> Vielen Dank und viele Grüße,
> Johannes
Guten Abend Johannes
Aha, das verbessert die Situation doch irgendwie ganz
wesentlich. Wenn wir wissen, dass die 8 Punkte eigent-
lich die Ecken eines Quaders sein sollten, dann könnte
man doch versuchen, in einem ersten Schritt die allfäl-
ligen Messfehler auszugleichen, um einen exakten Quader
zu erhalten. Im zweiten Schritt prüft man dann, ob der
Punkt [mm] P_0 [/mm] diesem Quader angehört oder nicht.
Natürlich wäre es sinnvoll, die Eckpunkte des Quaders
nicht in zufälliger, sondern in systematischer Reihen-
folge zu vermessen und einzugeben.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:47 Fr 25.06.2010 | | Autor: | abakus |
> > Hallo,
> >
> > die Punkte ergeben sich durch Abtastung der Eckpunkte eines
> > realen "Quaders" mittels eines Sensors, der die Daten an
> > den Rechner überträgt. Durch kleinste Messfehler bzw. -
> > ungenauigkeiten liegt der vierte Eckpunkt einer Seite nicht
> > zwingend in einer Ebene mit den anderen drei Eckpunkte
> > dergleichen Seite.
> > Die Reihenfolge der einzelnen Punkte könnte unter
> > Umständen vorher festgelegt werden, wenn ansonsten die
> > Rechenzeit zu lange würde.
> > Ich denke, ich werde den Ansatz mit den Tetraedern
> > verfolgen.
> >
> > Vielen Dank und viele Grüße,
> > Johannes
>
>
>
> Guten Abend Johannes
>
> Aha, das verbessert die Situation doch irgendwie ganz
> wesentlich. Wenn wir wissen, dass die 8 Punkte eigent-
> lich die Ecken eines Quaders sein sollten, dann könnte
> man doch versuchen, in einem ersten Schritt die allfäl-
> ligen Messfehler auszugleichen, um einen exakten Quader
> zu erhalten. Im zweiten Schritt prüft man dann, ob der
> Punkt [mm]P_0[/mm] diesem Quader angehört oder nicht.
> Natürlich wäre es sinnvoll, die Eckpunkte des Quaders
> nicht in zufälliger, sondern in systematischer Reihen-
> folge zu vermessen und einzugeben.
>
>
> LG Al-Chw.
>
Zweite Variante:
Da es jetzt ein (beinahe-)Quader ist, müsste der Punkt zwischen den Ebenen "oben" und "unten", "vorn" und "hinten" sowie "links" und "rechts" liegen.
Bei einem "richtigen" Quader stellt man jeweils ein Paar paralleler Ebenen in der Form (z.B.)
[mm] ax+by+cz=d_{vorn}
[/mm]
und
[mm] ax+by+cz=d_{hinten}
[/mm]
auf und schaut, ob für den gegebeben Punkt sein Wert ax+by+cz zwischen [mm] d_{vorn} [/mm] und [mm] d_{hinten} [/mm] liegt.
Durch die Messfehler sind die Ebenen jedoch nicht so genau festgelegt.
Die Fläche P1 P2 P3 P4 kann deshalb nur unter Auslassung eines der 4 Punkte als Ebene durch 3 dieser Punkte beschrieben werden, und die Fläche P5 P6 P7 P8 wird einfach als Parallelebene zu P1 P2 P3 gesehen, die den Punkt P5 enthält.
Statt P5 könnte ebenso P6, P7 oder P8 genommen werden, und auch die erste Ebene kann statt P4 einen anderen Punkt "weglassen".
Es gibt somit allein für den Test "P zwischen oben und unten" 16 mögliche zu testende Kombinationen.
Kritisch wird es halt, wenn P in der Nähe der Begrenzungsfläche liegt und einige Tests sich deshalb widersprechen.
Gruß Abakus
|
|
|
| |
|
> Kritisch wird es halt, wenn P in der Nähe der
> Begrenzungsfläche liegt und einige Tests sich deshalb
> widersprechen.
Mit diesem Effekt muss man hier halt wegen möglicher
Messungenauigkeiten leben. Bei diesem Test gibt es
halt auch ein "Unentschieden" - wie beim Fußball !
Mit einer korrekt durchgeführten, aber halt aufwändigen
Ausgleichsrechnung kann man die Wahrscheinlichkeit
eines "Unentschieden" zwar verkleinern, aber nicht
ganz eliminieren.
LG Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Sa 26.06.2010 | | Autor: | Mister_J |
Hallo zusammen,
erst einmal Danke für die vielen Vorschläge.
Könnte man das Problem nicht so angehen, dass man, wie Abakus sagte, testet, ob der gegebene Punkt zwischen 2 Ebenen [mm] E_{unten} [/mm] und [mm] E_{oben} [/mm] liegt. Dafür müsste man aber doch nicht jede mögliche Kombination aus den vier oberen und unteren Punkten testen, da man jeweils die vier Punkte einer "Ebene" in 2 Ebenen aufteilt, die durch 3 Punkte gegeben sind. Also hätte man zum Beispiel 2 obere und 2 untere Ebenen, bei denen man testet, ob der Punkt dazwischen liegt.
Entsteht dann zum Beispiel ein Unentschieden, wie Al-Chwarizmi sagte, dadurch, dass die Kombination mit der ersten oberen Ebene [mm] E_{oben,1} [/mm] besagt, dass sich der Punkt innerhalb befindet, und die Kombination mit der zweiten oberen Ebene [mm] E_{oben,2}, [/mm] dass sich der Punkt außerhalb befindet, so könnte man testen, ob der Punkt innerhalb eines Tetraeders liegt, der durch die Punkte der Ebene [mm] E_{oben,1} [/mm] und jeweils einem Punkt der unteren Ebene aufgespannt wird. Dabei müssen diesmal natürlich alle 4 unteren Punkte mit einbezogen werden.
Ist dies der Fall, ist der Punkt innerhalb des "Quaders", ansonsten nicht. Auf jeden Fall könnte nach einem Unentschieden und der darauf folgenden genaueren Überprüfung sicher gesagt werden, wo sich der Punkt befindet.
Somit müsste man im unkritischen Fall, wenn also der Punkt zum Beispiel genau in der Mitte des Quaders liegt, nur für 4 verschiedene Kombinationen pro Ebenenausrichtung (oben-unten, recht-links, vorne-hinten) überprüft werden, ob der Punkt sich dazwischen befindet.
Im kritischen Fall wird nur bis zur Erreichung eines Unentschieden geprüft und danach genauer durch die Tetraeder.
Könnte man so vorgehen? Ich hoffe, ich habe mich nicht zu ungenau ausgedrückt.
Viele Grüße,
Johannes
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:35 Sa 26.06.2010 | | Autor: | Mister_J |
... andererseits könnte man, wenn die Reihenfolge der Punkte bekannt ist, gleich alle 8 Tetraeder testen, ob sich in einem der Punkt befindet.
Wäre dann wahrscheinlich noch das schnellste, oder?
Viele Grüße,
Johannes
|
|
|
| |
|
> ... andererseits könnte man, wenn die Reihenfolge der
> Punkte bekannt ist, gleich alle 8 Tetraeder testen, ob sich
> in einem der Punkt befindet.
>
> Wäre dann wahrscheinlich noch das schnellste, oder?
>
> Viele Grüße,
> Johannes
Hallo Johannes,
wenn du dich einfach auf die gegebenen Punkte (mit ihren
allfälligen Ungenauigkeiten) stützt und wenn diese in der
Standardreihenfolge ABCDEFGH gegeben sind (Grundrecht-
eck ABCD und darüber liegendes Rechteck EFGH), so kannst
du dich wohl sogar auf 5 Tetraeder beschränken, nämlich:
ACDH
AEFH
ABCF
CFGH
ACFH
(die ersten vier nehmen je ein Sechstel des Quadervolumens
ein - falls es wirklich ein Quader ist - und das letzte ein Drittel)
Auch bei diesem Verfahren nimmt man aber in Kauf, dass der
getestete Punkt allenfalls als "draußen" bewertet wird,
obwohl er innerhalb der konvexen Hülle der 8 Punkte liegt.
Falls die Messfehler aber klein sind, wird dies auch nur zu
unerheblichen "Fehlentscheidungen" führen.
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:36 So 27.06.2010 | | Autor: | Mister_J |
Hallo,
wie mir gestern noch eingefallen ist, wäre es doch am einfachsten zu überprüfen, ob der zu überprüfende Punkt jeweils über all den einzelnen 12 Ebenen (2 pro Seite) liegt (positiver Abstand), wenn der Normalenvektor in das Quader-Innere zeigt.
Danke Al-Chwarizmi für deine Ideenvorschläge.
Viele Grüße,
Johannes
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:10 So 27.06.2010 | | Autor: | abakus |
> Hallo,
>
> wie mir gestern noch eingefallen ist, wäre es doch am
> einfachsten zu überprüfen, ob der zu überprüfende Punkt
> jeweils über all den einzelnen 12 Ebenen (2 pro Seite)
Hallo,
wenn die 4 Punkte A,B,C und D nicht genau in einer Ebene liegen, darfst du nicht nur die Ebenen ABC und ACD betrachten. Wenn ausgerechnet die Linie AC durch Messfehler ins Quaderinnere hinein verschoben wird, könnte ein Punkt sowohl bezüglich ABC als auch bezüglich ACD "außerhalb" liegen, obwohl er bezüglich BCD und/oder ABD innerhalb liegt.
> liegt (positiver Abstand), wenn der Normalenvektor in das
> Quader-Innere zeigt.
> Danke Al-Chwarizmi für deine Ideenvorschläge.
>
> Viele Grüße,
> Johannes
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:00 So 27.06.2010 | | Autor: | Mister_J |
Danke Abakus,
da hast du natürlich Recht! Dadurch muss ich dann wohl weitere zwei Ebenen pro "Seite" überprüfen, wenn der Abstand wirklich negativ sein sollte.
Vielen Dank und viele Grüße,
Johannes
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:46 Mo 28.06.2010 | | Autor: | Mister_J |
Hallo nochmal,
wenn ich auf jeder Quader"seite" überprüfe, ob der vierte Punkt einen positiven Abstand zu der Ebene hat, die über die verbleibenden drei Punkten der gleichen "Seite" definiert wird, so ist diese Ebene eine der zwei konvexen Ebenen dieser Seite. Die zweite Fläche definiert sich dann über die noch verbleibende Fläche der "Seite".
Somit muss ich doch nur 2 Flächen pro "Seite" mit in die eigentlich Berechnung mit einfließen lassen.
Falls dies nicht stimmen sollte, bitte ich um einen Kommentar. (Natürlich darf auch jemand schreiben, dass das so funktioniert  )
Vielen Dank,
Johannes
|
|
|
|
