feststellen, ob ein Punkt auf der Fläche liegt

  • Hey @ all,

    ich habe eine 4eckige Plane in einem 3 dimensionalem Raum. Ich kenne nur die 4 Eckpunkte (A, B, C, D). Nun möchte ich herausfinden, ob irgendein Punkt P (x|y|z) auf der Fläche liegt. Der Winkel zwischen den 4 Ecken muss nicht zwangsläufig 90° sein. Wie findet man heraus, ob P auf der Fläche liegt oder nicht?

    mfg
    Developer30

    "Je mehr Käse, desto mehr Löcher; je mehr Löcher, desto weniger Käse. Ergo: Je mehr Käse, desto weniger Käse. 8| "
    "Programmers never die: they just GOSUB without RETURN"
    "I tried to change the world but I couldn't find the source code."

    Einmal editiert, zuletzt von Developer30 (16. Dezember 2011 um 22:22)

  • Da du die Vektorenrechnung im notwendigen Umfang in der Schule noch nicht gehört hast ist es etwas schwierig es so zu erklären das du es selbst mit ein paar Hinweisen herleiten kannst.
    Daher stattdessen wenigstens den Rechenweg fertig mit ein paar Kommentaren (Berechnet den Abstand des Punktes von der Ebene - wenn d=0 - Punkt ist auf Ebene):

    Spoiler anzeigen
    [autoit]

    ; 3 Punkte der Ebene
    Global $A[3] = [-1, 1, 1]
    Global $B[3] = [-2, 0, 2]
    Global $C[3] = [-3, 2, 1]

    [/autoit] [autoit][/autoit] [autoit]

    Global $P[3] = [1, 2, 3] ; Koordinaten des Punktes

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    $BminA = VektorDifferenz($B, $A)
    $CminA = VektorDifferenz($C, $A)

    [/autoit] [autoit][/autoit] [autoit]

    $n = Kreuzprodukt($BminA, $CminA) ; Normalenvektor
    $bn = Vektorbetrag($n) ; Betrag des Normalenvektors
    $n0 = VektorMulwithSkalar($n, 1 / $bn) ; normierter Normalenvektor
    $dn = Skalarprodukt($n, $A) ; Verschiebung der Ebene (egal welcher der 3 Punkte hier eingetragen wird)

    [/autoit] [autoit][/autoit] [autoit]

    ; Abstand des Punktes P von der Ebene
    $d = (Skalarprodukt($P, $n) - $dn) / $bn
    MsgBox(0,"Abstand", "Abstand: " & $d)

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    ; Berechnet das Kreuzprodukt 2er 3D-Vektoren:
    Func Kreuzprodukt(Const $A, Const $B)
    Local $Temp[3] = [$A[1] * $B[2] - $A[2] * $B[1], _
    $A[2] * $B[0] - $A[0] * $B[2], _
    $A[0] * $B[1] - $A[1] * $B[0]]
    Return $Temp
    EndFunc ;==>Kreuzprodukt

    [/autoit] [autoit][/autoit] [autoit]

    ; Berechnet die Differenz 2er Vektoren
    Func VektorDifferenz(Const $A, Const $B)
    Local $Temp[UBound($A)]
    For $i = 0 To UBound($A) - 1
    $Temp[$i] = $A[$i] - $B[$i]
    Next
    Return $Temp
    EndFunc ;==>VektorDifferenz

    [/autoit] [autoit][/autoit] [autoit]

    ; Berechnet den Betrag eines Vektors (anschaulich: Die Länge des Vektors)
    Func Vektorbetrag(Const $A)
    Local $qSum = 0
    For $i = 0 To UBound($A) - 1
    $qSum += $A[$i] * $A[$i]
    Next
    Return Sqrt($qSum)
    EndFunc ;==>Vektorbetrag

    [/autoit] [autoit][/autoit] [autoit]

    ; Berechnet die Multiplikation eines Vektors mit einem Skalar
    Func VektorMulwithSkalar($V, $S)
    Local $Temp[UBound($A)]
    For $i = 0 To UBound($A) - 1
    $Temp[$i] = $A[$i] * $S
    Next
    Return $Temp
    EndFunc ;==>VektorMulwithSkalar

    [/autoit] [autoit][/autoit] [autoit]

    ; Berechnet das Skalarprodukt 2er Vektoren
    Func Skalarprodukt(Const $A, Const $B)
    Local $Sum = 0
    For $i = 0 To UBound($A) - 1
    $Sum += $A[$i] * $B[$i]
    Next
    Return $Sum
    EndFunc ;==>Skalarprodukt

    [/autoit]

    Einmal editiert, zuletzt von AspirinJunkie (15. Dezember 2011 um 20:50)

  • Zunächst thx @ Ijens für die Bemühungen, die mir leider nicht viel gebracht haben.

    Zitat

    Da du die Vektorenrechnung im notwendigen Umfang in der Schule noch nicht gehört hast

    ja leider :/

    Danke für den Rechenweg. Wobei ich da etwas nicht ganz verstehe. Die Punkte A, B, und C bilden doch ein Dreieck.
    Wenn x die horizontale Achse ist und die z-Achse in die "Tiefe" nach hinten geht, wäre y also die Höhe. Ich kam noch garnicht dazu, dein gesamtes Script anzuschauen, weil es mich verblüfft hat, dass folgende Punkte d=0 ergeben:

    [autoit]

    Global $A[3] = [1, 1, 1]
    Global $B[3] = [10, 1, 1]
    Global $C[3] = [5, 5, 1]

    [/autoit][autoit][/autoit][autoit]

    Global $P[3] = [-50, 1, 1]

    [/autoit]

    z kann man bei meinen Punkten jetzt quasi ignorieren, weil wir uns überall in der gleichen "Tiefe" befinden. Ich verstehe nicht, warum mein Punkt $P auf dem Dreieck sein soll? -50 ist meilenweit von A (1|1|1) entfernt. Oder habe ich etwas falsch verstanden?

    Edit: Oh.. nunja, ich sehe gerade, dass du geschrieben hast "Berechnet den Abstand des Punktes von der Ebene - wenn d=0 - Punkt ist auf Ebene".. aber das sagt noch nicht 100% darüber aus, ob der punkt auf der Fläche liegt, oder?

    "Je mehr Käse, desto mehr Löcher; je mehr Löcher, desto weniger Käse. Ergo: Je mehr Käse, desto weniger Käse. 8| "
    "Programmers never die: they just GOSUB without RETURN"
    "I tried to change the world but I couldn't find the source code."

  • Alle Punkte in deinem Beispiel haben als Z-Wert den gleichen Wert "1".
    Demnach befinden sich alle Punkte in der X-Y-Ebene +1
    Daher ist das schon korrekt das der Punkt in der selben Ebene liegt.
    Wenn dich der Abstand nicht interessiert sondern nur ob der Punkt auf der Ebene liegt oder nicht kannst du das Skript auch folgendermaßen zusammenkürzen:

    Spoiler anzeigen
    [autoit]

    #include <Array.au3>
    ; 3 Punkte der Ebene
    Global $A[3] = [1, 1, 1]
    Global $B[3] = [10, 1, 1]
    Global $C[3] = [5, 5, 1]

    [/autoit] [autoit][/autoit] [autoit]

    Global $P[3] = [-50, 1, 1]

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    $BminA = VektorDifferenz($B, $A)
    $CminA = VektorDifferenz($C, $A)

    [/autoit] [autoit][/autoit] [autoit]

    $n = Kreuzprodukt($BminA, $CminA) ; Normalenvektor
    $dn = Skalarprodukt($n, $A) ; Verschiebung der Ebene (egal welcher der 3 Punkte hier eingetragen wird)

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    If Skalarprodukt($P, $n) <> $dn Then
    MsgBox(0,"", "Punkt liegt nicht in Ebene")
    Else
    MsgBox(0,"", "Punkt liegt in Ebene")
    EndIf

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    ; Berechnet das Kreuzprodukt 2er 3D-Vektoren:
    Func Kreuzprodukt(Const $A, Const $B)
    Local $Temp[3] = [$A[1] * $B[2] - $A[2] * $B[1], _
    $A[2] * $B[0] - $A[0] * $B[2], _
    $A[0] * $B[1] - $A[1] * $B[0]]
    Return $Temp
    EndFunc ;==>Kreuzprodukt

    [/autoit] [autoit][/autoit] [autoit]

    ; Berechnet die Differenz 2er Vektoren
    Func VektorDifferenz(Const $A, Const $B)
    Local $Temp[UBound($A)]
    For $i = 0 To UBound($A) - 1
    $Temp[$i] = $A[$i] - $B[$i]
    Next
    Return $Temp
    EndFunc ;==>VektorDifferenz

    [/autoit] [autoit][/autoit] [autoit]

    ; Berechnet den Betrag eines Vektors (anschaulich: Die Länge des Vektors)
    Func Vektorbetrag(Const $A)
    Local $qSum = 0
    For $i = 0 To UBound($A) - 1
    $qSum += $A[$i] * $A[$i]
    Next
    Return Sqrt($qSum)
    EndFunc ;==>Vektorbetrag

    [/autoit] [autoit][/autoit] [autoit]

    ; Berechnet die Multiplikation eines Vektors mit einem Skalar
    Func VektorMulwithSkalar($V, $S)
    Local $Temp[UBound($A)]
    For $i = 0 To UBound($A) - 1
    $Temp[$i] = $A[$i] * $S
    Next
    Return $Temp
    EndFunc ;==>VektorMulwithSkalar

    [/autoit] [autoit][/autoit] [autoit]

    ; Berechnet das Skalarprodukt 2er Vektoren
    Func Skalarprodukt(Const $A, Const $B)
    Local $Sum = 0
    For $i = 0 To UBound($A) - 1
    $Sum += $A[$i] * $B[$i]
    Next
    Return $Sum
    EndFunc ;==>Skalarprodukt

    [/autoit]

    Edit: Jetzt verstehe ich: Deine Frage war gar nicht ob die Punkte in der selben Ebene liegen sondern ob ein Punkt in einem bestimmten Polygon liegt. ;)
    Schau dir dazu mal diesen Thread an: >>Klickmich<<
    Bzw. wenn es bei einem Rechteck bleibt: >>MathEx UDF<<

    Einmal editiert, zuletzt von AspirinJunkie (15. Dezember 2011 um 21:58)

  • Edit: Jetzt verstehe ich: Deine Frage war gar nicht ob die Punkte in der selben Ebene liegen sondern ob ein Punkt in einem bestimmten Polygon liegt.


    genau das ;D.. sry für meine unpräzise Fragestellung...

    Schau dir dazu mal diesen Thread an: >>Klickmich<<


    in diesem Thread geht es um Polygone im 2D Umfeld.. die Komplikation bei meinem Problem liegt darin, dass ich wissen möchte, ob der Punkt auf der die Fläche eines Körpers (3D) liegt.. Wobei dieser aus ganz vielen kleinen Vierecken und Dreiecken besteht.

    "Je mehr Käse, desto mehr Löcher; je mehr Löcher, desto weniger Käse. Ergo: Je mehr Käse, desto weniger Käse. 8| "
    "Programmers never die: they just GOSUB without RETURN"
    "I tried to change the world but I couldn't find the source code."


  • (Berechnet den Abstand des Punktes von der Ebene - wenn d=0 - Punkt ist auf Ebene)


    Hab doch gewusst irgendwie gehts bestimmt einfacher^^ --> Hessesche Normalform ;)
    Danke :)

    Und wegen auf der Fläche liegen: Wenn der Punkt erstmal sicher auf der gleichen Ebene ist müsste man das einfach begrenzen können.
    Also zB. Z-Achse weglassen --> also von oben drauf schaun --> wenn der Punkt innerhalb des Vierecks ist, ist er auf der Fläche.
    Wie man das dann berechnet fällt mir aber jetzt auf die schnelle leider auch wieder nicht ein :(

    in diesem Thread geht es um Polygone im 2D Umfeld


    Aber das könnte man dann demnach verwenden ;) Einfach eine Achse weglassen und 2-Dimensional rechnen.


    Mfg Ijens

    2 Mal editiert, zuletzt von Ijens (16. Dezember 2011 um 08:46)

  • Und wegen auf der Fläche liegen: Wenn der Punkt erstmal sicher auf der gleichen Ebene ist müsste man das einfach begrenzen können.
    Also zB. Z-Achse weglassen --> also von oben drauf schaun --> wenn der Punkt innerhalb des Vierecks ist, ist er auf der Fläche.
    Wie man das dann berechnet fällt mir aber jetzt auf die schnelle leider auch wieder nicht ein


    die Punkte müssen aber nicht auf der gleichen Ebene sein. Es könnte sich auch um ein Dreieck handeln, dessen Punkte in 3 verschiedenen Ebenen sind (also z.B. für die z-Achse 3 verschiedene Werte).

    "Je mehr Käse, desto mehr Löcher; je mehr Löcher, desto weniger Käse. Ergo: Je mehr Käse, desto weniger Käse. 8| "
    "Programmers never die: they just GOSUB without RETURN"
    "I tried to change the world but I couldn't find the source code."

    Einmal editiert, zuletzt von Developer30 (16. Dezember 2011 um 15:33)


  • die Punkte müssen aber nicht auf der gleichen Ebene sein. Es könnte sich auch um ein Dreieck handeln, dessen Punkte in 3 verschiedenen Ebenen sind (also z.B. für die z-Achse 3 verschiedene Werte).

    Genau ja, und diese 3 Punkte (oder mehr) ergeben dann zusammen ne neue Ebene (sofern die Flächen nicht gewölbt oder irgendwas sind). Dann kannst du erstmal mit AspirinJunkie's Lösung gucken ob der Punkt auf dieser neuen Ebene liegt:
    --> wenn nein, also d= ungleich 0, kann der Punkt auch nicht auf der Fläche liegen und fällt also gleich schon weg.
    --> wenn ja, also d=0, gilt es noch zu prüfen ob er auch auf der Fläche liegt.
    Und dazu kannst du theoretisch einfach eine Achse weglassen (X,Y oder Z - egal welche, muss nur bei allen Punkten die gleiche sein). Somit hast du ein 2-Dimensionales Konstrukt und kannst es so machen wie in dem Thread :)

    Mfg

  • Ijens hat Recht (ich habe auch erst komplizierter gedacht).
    Du suchst sicherlich nach einer Möglichkeit die Ebene unverzerrt in ein 2D-System zu überführen.
    Das wäre eine Parallelprojektion mit anschließender Basistransformation.
    Das wäre aber verdammt aufwendig umzusetzen (am besten noch >>hier<< beschrieben).

    Für deine Fragestellung ob ein Punkt in einem Polygon liegt oder nicht brauchst du aber keine unverzerrte Projektion.
    Nimm alle Polygonpunkte und bilde z.B. die Parallelprojektion auf die Y-Z-Ebene (X-Koordinaten einfach weglassen).
    Dann hast du zu allen Punkten 2D-Koordinaten.
    Wenn der Punkt sich in der 3D-Ebene innerhalb des Polygons befindet so wird er es auch in dieser verzerrten Projektion tun.
    Daher reicht es einfach eine Koordinate wegzulassen und die entsprechende Prüfung durchzuführen.
    Um allerdings Spezialfälle wie eine genau senkrechte Lage der Ebene zur Projektionsebene mit zu beachten ist es angebracht die Prüfung in allen 3 Hauptebenen durchzuführen und wenn der Punkt in allen 3 Projektionen im Polygon liegt ist er es auch im 3-dimensionalen.

  • ahh 8o, jetzt seh ichs auch.. das könnte klappen.. ich melde mich wieder wenns ichs getestet hab.
    danke :)

    "Je mehr Käse, desto mehr Löcher; je mehr Löcher, desto weniger Käse. Ergo: Je mehr Käse, desto weniger Käse. 8| "
    "Programmers never die: they just GOSUB without RETURN"
    "I tried to change the world but I couldn't find the source code."

    2 Mal editiert, zuletzt von Developer30 (16. Dezember 2011 um 21:03)

  • Hi,
    Punkt in Fläche in 3D => kompliziert und extrem aufwendig^^. Bei Polygonen nur ohne weiteres berechenbar, wenn das Polygon selbst nur Punkte in einer Ebene hat.

    In 2D sehr simpel:
    Koordinaten des Polygons im Uhrzeigersinn "ablaufen". Zwischen 2 aufeinanderfolgenden "Ecken" besteht eine Gerade. Wenn Punkt immer rechts von allen Geraden ist, ist er innerhalb des Polygons, ansonsten ausserhalb.

    ciao
    Andy


    "Schlechtes Benehmen halten die Leute doch nur deswegen für eine Art Vorrecht, weil keiner ihnen aufs Maul haut." Klaus Kinski
    "Hint: Write comments after each line. So you can (better) see what your program does and what it not does. And we can see what you're thinking what your program does and we can point to the missunderstandings." A-Jay

    Wie man Fragen richtig stellt... Tutorial: Wie man Script-Fehler findet und beseitigt...X-Y-Problem

    Einmal editiert, zuletzt von Andy (17. Dezember 2011 um 07:04)

  • Ich hab die Idee von Ijens und AspirinJunkie mal mit einem Beispiel getestet. Es scheint zu funktionieren. :whistling:
    Danke :thumbup:

    "Je mehr Käse, desto mehr Löcher; je mehr Löcher, desto weniger Käse. Ergo: Je mehr Käse, desto weniger Käse. 8| "
    "Programmers never die: they just GOSUB without RETURN"
    "I tried to change the world but I couldn't find the source code."