Check, ob Punkt in Dreieck oder Viereck

[Froggerprogger]

Folgender Code testet, ob ein Punkt P in dem durch die Punkte A,B,C gegebenen planaren Dreieck liegt, bzw. in dem durch die Punkte A,B,C,D (und deren Reihenfolge) gegebenen Viereck. Beim Viereck muss die Reihenfolge der Nennung beachtet werden: Es muss 'aussenherum' beschritten werden, nicht über eine Diagonale.
Liegen Punkte auf einer Geraden, oder stimmen gar überein, wird dies von beiden Funktionen korrekt gehandhabt!

Code: Alles auswählen

; functions to check whether a point lies in a triangle/quadrangle or not
;
; Remark:
; A quadrangle is specified by it's 4 points and the order of them!
; The function doesn't calculate the complex hull of A,B,C,D, so make sure
; to give A,B,C,D in an order where you 'walk around' the quadrangle, and not
; on one of its diagonals.
;
; by Froggerprogger 16.11.2005

Procedure.l InTriangle(Ax.f, Ay.f, Bx.f, By.f, Cx.f, Cy.f, Px.f, Py.f) ; returns #TRUE if P lies inside the triangle ABC, #FALSE if not. ABC might be a 'corrupt' triangle (e.g. a line or a point).
  Protected validTriangle.l
  Protected p.f, q.f, denom.f
  
  ; check if ABC is a true triangle == not lying on one line
  denom = (Ax - Bx)*(Ay - Cy) - (Ax - Cx)*(Ay - By)  
  If denom <> 0.0
    validTriangle = #True
  Else
    validTriangle = #False
  Endif

  If validTriangle
    ;p = - ((Ax - Cx)*(Ay - Py) - (Ax - Px)*(Ay - Cy)) / ((Ax - Bx) (Ay - Cy) - (Ax - Cx) (Ay - By))
    ;q =   ((Ax - Bx)*(Ay - Py) - (Ax - Px)*(Ay - By)) / ((Ax - Bx) (Ay - Cy) - (Ax - Cx) (Ay - By))
    p     = -((Ax - Cx)*(Ay - Py) - (Ax - Px)*(Ay - Cy)) / denom
    q     =  ((Ax - Bx)*(Ay - Py) - (Ax - Px)*(Ay - By)) / denom

    If p >= 0.0 And q <= 1.0 And Abs(p)+Abs(q) <= 1.0
      ProcedureReturn #True
    Else
      ProcedureReturn #False
    Endif
  Else
     ; here check the special cases (A=B=C or ABC on one line)
     
     ; find the leftmost and rightmost points
     LeftX  = Ax : LeftY  = Ay
     RightX = Ax : RightY = Ay
     If Bx < LeftX
       LeftX = Bx : LeftY = By
     Endif
     If Cx < LeftX
       LeftX = Cx : LeftY = Cy
     Endif
     If Bx > RightX
       RightX = Bx : RightY = By
     Endif
     If Cx > RightX
       RightX = Cx : RightY = Cy
     Endif
     
     If LeftX = RightX And LeftY = RightY
        ; A=B=C
        If Px <> LeftX Or Py <> LeftY
          ProcedureReturn #False
        Else
          ProcedureReturn #True
        Endif
     Else
       ; ABC on one line 
       If Px < LeftX Or Px > RightX
         ProcedureReturn #False
       Else
         ; check if vectorproduct((P-Left), (Right-Left)) = 0
         If (Px - LeftX) * (RightY - LeftY) = (Py - LeftY) * (RightX - LeftX)
           ProcedureReturn #True
         Else
           ProcedureReturn #False
         Endif
       Endif  
     Endif
  EndIf 
EndProcedure

Procedure.l InQuadrangle(Ax.f, Ay.f, Bx.f, By.f, Cx.f, Cy.f, Dx.f, Dy.f, Px.f, Py.f) ; returns #TRUE if P lies inside the quadrangle ABCD (given in this order!), #FALSE if not. ABCD must be given in a non-line-crossing order, but might be a triangle/line/point.
  If InTriangle(Ax, Ay, Bx, By, Cx, Cy, Px, Py)
    ProcedureReturn #True
  Else
    If InTriangle(Cx, Cy, Dx, Dy, Ax, Ay, Px, Py)
      ProcedureReturn #True
    Else
      ProcedureReturn #False
    Endif
  Endif
EndProcedure

; some test-examples
debug InTriangle(0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0)
debug InTriangle(0.0, 0.0, 1.0, 0.0, 0.0, 1.0, -1.0, 0.0)
debug InTriangle(5.0, 5.0, 6.0, 5.0, 5.0, 6.0, 5.5, 5.5)
debug InTriangle(10.0, 10.0, 10.0, 10.0, 20.0, 10.0, 15.0, 10.0)
debug InTriangle(1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 2.5, 2.5)
debug InTriangle(1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 2.5, 2.6)
debug InTriangle(-1.0, -1.0, -2.0, -2.0, 3.0, 3.0, 2.5, 2.5)
debug InQuadrangle(-5.0, -5.0, 5.0, -5.0, 5.0, 5.0, -5.0, 5.0, -2.0, -2.0)
debug InQuadrangle(-5.0, -5.0, 5.0, -5.0, 5.0, 5.0, -5.0, 5.0, 2.0, 12.0)
debug InQuadrangle(-5.0, -5.0, 5.0, -5.0, 5.0, 5.0, -5.0, 5.0, 122.0, 12.0)