PureBoard

Verfasst: **14.07.2009 16:21**

Hi,
Ich hab hier so ein kleines Mathematisches Problem zu lösen.
Gegeben habe ich ein Dreieck, welches sich durch die
3 Punkte Ax/Ay Bx/By und Cx/Cy beschreiben lässt
(Das dreieck kann auch gekippt oder gedreht sein)
und es gibt einen Punkt Px/Py .

Wie krieg ich nun rechnerisch raus ob der
Punkt innerhalb des Dreiecks liegt ?
(Der Punkt wird später irgendwo sein können )

Bild

Ich hab bisher noch nix verwertbares
(Simple Funktion die man nachprogrammieren kann)
er-googeln können.

Verfasst: **14.07.2009 16:23**

Ich kann Dir damit dienen (prueft halt ob ein Punkt sich innerhalb eines Polygons befindet, muss nicht zwingend ein Dreieck sein):

Code: Alles auswählen

inline int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
    int i, j, c = 0;
    for(i = 0, j = nvert - 1; i < nvert; j = i++)
    {
        if (((verty[i] > testy) != (verty[j] > testy)) && (testx < (vertx[j] - vertx[i]) * (testy - verty[i])
                / (verty[j] - verty[i]) + vertx[i]))
            c = !c;
    }
    return c;
}

Ich bin mir aber ziemlich sicher, dass es mit Dreiecken noch viel einfacher geht... hab aber grad auch keine Idee. Ich glaube generell testet man von irgendwo ausserhalb, wo der Punkt auf keinen Fall liegen kann, eine Strecke zum Punkt, und prueft dann, wie oft man dabei die Linien des Dreiecks / Polygons ueberquert. Ist es eine ungerade Zahl, so befindet sich der Punkt im Polygon.

EDIT: Ach ja, die Funktion hab ich damals von dieser Seite gezogen: http://www.ecse.rpi.edu/Homepages/wrf/R ... npoly.html

EDIT 2: Eine simple Googlesuche nach "point in triangle" liefert auch sehr viele Ergebnisse

Verfasst: **14.07.2009 16:41**

Sowas hatte ich mir damals für die Raytracing-Engine auch selbst programmiert.

Ich glaube id hatte damals das Skalarprodukt <BA, CA> und <BA, PA> einfach nach dem
Vorzeichen verglichen. Aber ZeHas Funktion sieht wesentlich einfacher und performanter
aus, wenn sie stimmt (wovon ich einfach mal ausgehe).

///Edit:
Logisch, dass ZeHas Code viel einfacher ist.

Da geht es ja nur um 2D. Da kann man natürlich einiges vereinfachen.

Wenn ich den Code richtig verstehe, schaut er, ob bei benachbarten Linien der zu prüfende
Punkt immer auf der gleichen Seite bleibt. Allerdings muss dann der Polygonzug immer im
oder gegen den Uhrzeigersinn übergeben werden.

Verfasst: **14.07.2009 18:09**

PtInRegion ?

Verfasst: **14.07.2009 18:11**

konnte die Funktion gerade nicht testen, weil ich nicht an einem Rechner mit PB sitze, aber es sollte (hoffentlich) funktionieren

Code: Alles auswählen

Procedure.l _col_point_tri(tx1.l,ty1.l,tx2.l,ty2.l,tx3.l,ty3.l,Px.l,Py.l)
  
  Protected r.f
  Protected s.f
  Protected result.f
  
  Protected Ax.l = tx2 - tx1
  Protected Ay.l = ty2 - ty1
  Protected Bx.l = tx3 - tx1
  Protected By.l = ty3 - ty1
  
  If Ay = 0 or By = 0
    ProcedureReturn #False
  EndIf

  Px - tx1
  Py - ty1
  
  r = (By*Ax-Ay*Bx)
  
  If r 
    r      = (Px*By-Bx*Py)/r
    s      = (Py-Ay*r)/By
    result = r+s
    If result <= 1 And result => 0 And r <= 1 And r => 0 And s <= 1 And s => 0
      ProcedureReturn #True
    EndIf
  EndIf
  
  ProcedureReturn #False
  
EndProcedure

Habe ich mir mal für meine Kollisionsroutine überlegt.

Wie bei einem Polygon zu prüfen, wie oft die "Linien" geschnitten werden ist bei Dreiecken nicht so optimal. Wäre wesentlich rechenintensiver.

Edit:
Habe mal gegooglet, und was findet man? Selbe Idee, etwas anders umgesetzt:
http://www.blackpawn.com/texts/pointinpoly/default.html
ganz unten. Sogar zum interaktiv mit rumspielen.

Verfasst: **15.07.2009 09:47**

@Gnasen: Danke , die Procedure geht einwandfrei.

@Zeha: C-Code muss net unbedingt sein, sonst hätt ich hier nicht gepostet

@Andreas: Nein, keine Api, Plattformunabhängigkeit

Trotzdem recht herzlichen Dank an Alle das ihr euch mit darum
gekümmert habt.

Problem also erledigt!

Verfasst: **15.07.2009 12:49**

Hey, laut eigener Aussage hattest Du ein "mathematisches Problem" und wolltest eine "simple Funktion die man nachprogrammieren kann"

Verfasst: **15.07.2009 15:00**

ZeHa hat geschrieben:Hey, laut eigener Aussage hattest Du ein "mathematisches Problem" und wolltest eine "simple Funktion die man nachprogrammieren kann"

genau, simple soll sie sein, keine wasweisichwieüberladen C-Funktion

trotzdem danke nochmals.

PureBoard

Befindet sich ein Punkt im Dreieck ? Gelöst !

Befindet sich ein Punkt im Dreieck ? Gelöst !