Willkommen bei Ask1.org

Hier diskutieren mehr als 10.000 User die verschiedensten Themen!
Register Now

Hilfe gesucht: Punkt im Tetraeder

Dieses Thema im Forum "Technik, Forschung und Entwicklung" wurde erstellt von Giacomo_S, 20. Dezember 2004.

  1. Giacomo_S

    Giacomo_S Ehrenmitglied

    Beiträge:
    2.795
    Registriert seit:
    13. August 2003
    Ort:
    München
    sorry Leute, aber vielleicht kann mir jemand da weiterhelfen, ich benötige einen Alghoritmus für ein Programm, an dem ich gerade schreibe.

    Nehmen wir an, es gibt einen Tetraeder, der in einem 3-dimensionalen Koordinatensystem durch vier (beliebige) Punkte aufgespannt wird.
    Die vier Punkte P1 bis P4 sind durch ihre Koordinaten x,y, und z definiert.

    Desweiteren gibt es einen (beliebigen) Punkt PX, auch durch seine drei Koordinaten x,y, und z definiert, für den entschieden werden soll, ob er innerhalb oder außerhalb des von den drei Punkten P1,P2,P3 und P4 gebildeten Tetraeders liegt.

    Wie müßte ein solches Entscheidungskriterium aussehen ?

    Danke,
    Giacomo.
     
  2. Suleiman

    Suleiman Geselle

    Beiträge:
    52
    Registriert seit:
    13. Juni 2002
    Konkretes habe ich nichts vorzuweisen, aber immerhin einen Ansatz :):

    Schritt 1: Die Ebenen, die durch die Seitenflächen bestimmt werden, festlegen. Vier Stück.
    Schritt 2: Ebene 1 liege "unten" am Tetraeder. Jetzt für den Punkt prüfen, ob er unter oder über der Ebene liegt. Liegt er drunter, ist der Algorithmus beendet - er liegt nicht im Tetraeder. Liegt er drüber, gehts weiter mit Schritt 3.
    Schritt 3,4,5: Analog wie Schritt 2, nur mit den Ebenen 2, 3, und 4.
     
  3. cadaei

    cadaei Meister

    Beiträge:
    251
    Registriert seit:
    30. November 2002
    Ort:
    Germany
    Alle Möglichkeiten durchgehen, um mit 3 von den 4 Punkten eine Ebene zu erstellen, und prüfen, ob PX auf der gleichen Seite des 4. Punktes liegt oder nicht. Liegt er nicht auf der gleichen --> außerhalb. Erst wenn er von allen Ebenen auf der Seite des 4. Punktes liegt --> innerhalb.
     
  4. sillyLilly

    sillyLilly Ehrenmitglied

    Beiträge:
    4.168
    Registriert seit:
    14. September 2002
    Ort:
    my home is my castle
    :O_O:


    Naja ... ich muss ja nicht alles verstehen 8)
     
  5. Misterbluedevil

    Misterbluedevil Neuling

    Beiträge:
    3
    Registriert seit:
    9. August 2002
    Damit sich ein Punkt Px in dem Tetraeder (P1,P2,P3,P4) befindet muss folgendes erfüllt sein:
    p1=Vektor zu P1
    usw.

    |p4-(Lotfußpunkt von px auf Ebene(durch die Punkte P1,P2,P3))|>|p4-px|
    |p3-(Lotfußpunkt von px auf Ebene(durch die Punkte P1,P2,P4))|>|p3-px|
    |p2-(Lotfußpunkt von px auf Ebene(durch die Punkte P1,P4,P3))|>|p2-px|
    |p1-(Lotfußpunkt von px auf Ebene(durch die Punkte P4,P2,P3))|>|p1-px|

    Die Fähigkeit zur Berechnung des Lotfußpunktes setze ich vorraus.

    Gruß Misterbluedevil
     
  6. Giacomo_S

    Giacomo_S Ehrenmitglied

    Beiträge:
    2.795
    Registriert seit:
    13. August 2003
    Ort:
    München
    Erst mal vielen Dank an alle.
    Dieser Ansatz scheint mir der vielversprechendste zu sein.
    Ich nehme an, der Lotfußpunkt, ist der Punkt, in dem sich die Höhe, die von einem Punkt ausgehend auf der gegenüberligenden Fläche senkrecht steht, schneidet.
    Aber bis Du Dir sicher, oder ist das eine vermutete Lösung ?

    Ich gebe folgendes zu bedenken: Befindet sich z.B. PX in unmittelbarer Nähe z.B. von Punkt P3 (aber innerhalb des Tetraeders) oder gar auf P3, dann ist doch |P1-PX| (=der Abstand von PX nach P1) in jedem Fall > |Lotfußpunkt 4,2,3| (=eine der 4 Höhen des Tetraeders) !
    Oder liege ich da falsch ?
     
  7. Giacomo_S

    Giacomo_S Ehrenmitglied

    Beiträge:
    2.795
    Registriert seit:
    13. August 2003
    Ort:
    München
    Auch nicht schlecht. Aber was ist in einem dreidimensionalen System mit beliebig austauschbaren Dimensionen "unten" und was ist "oben" ?

    Allerdings hat mich das auf eine Idee gebracht (noch nicht ausgereift).
    Kann da nicht irgendetwas gehen, mit

    Summe der Abstände Punkt PX-Tetraedermittelpunkt <= irgendetwas ?
     
  8. Giacomo_S

    Giacomo_S Ehrenmitglied

    Beiträge:
    2.795
    Registriert seit:
    13. August 2003
    Ort:
    München
    Eben.
    Jede / r hat auch seine / ihre Themen.
     
  9. cadaei

    cadaei Meister

    Beiträge:
    251
    Registriert seit:
    30. November 2002
    Ort:
    Germany
    ist korrekt.

    Die Lösung funktioniert, ich war nur zu faul, meine mathematischer auszudrücken, sie benutzt das gleiche Prinzip. Man könnte noch, wenn du definierst, dass sich ein Punkt auf einer Tetraederseite auch innerhalb befindet, aus den > jeweils ein ≥ machen. Wenn alle Bedingungen zutreffen, ist der Punkt im Tetraeder.

    Der Lotfußpunkt ist immer von PX nicht von P1(!), also ist in diesem Fall |P1-PX| ≤ LPX auf P2,P3,P4
    (in der Formel ist es andersrum, deshalb ≤ statt ≥)

    Das funktioniert leider nicht, denn dann gehst du von einer Kugel aus, also stimmt es nicht immer.