@Dr_D Chat GPT Point In 2D Triangle !

[D.J.Peters]

Today humans are more clever than AI

I'm sure you are familiar with the cross product in 3D.

Here is the formula as a reminder:

x = a.y*b.z - a.z*b.y
y = a.z*b.x - a.x*b.z
z = a.x*b.y - a.y*b.x

in 2D you have only the coords X,Y now take a look at last row of the 3D cross product.

z = a.x*b.y - a.y*b.x

In 2D z is the direction from monitor to you.
If the result of the last row of the cross product (from the triangle edges and the x,y point) is <=0 then x,y are outside the triangle edges.
With this knowledge in mind you can use it in function PontInTriangle2D() also.

It used 3 times: z = ax*by - ay*bx : if z<=0 then return false

Code: Select all

function PointInTriangle2D(byval px as single, byval py as single, _
                           byref x0 as single, byref y0 as single, _
                           byref x1 as single, byref y1 as single, _
                           byref x2 as single, byref y2 as single) as boolean
  dim as single ax=any,ay=any,bx=any,by=any
  ax=x1-x0:ay=y1-y0:bx=px-x0:by=py-y0 : if ax*by - ay*bx < 0 then return false
  ax=x2-x1:ay=y2-y1:bx=px-x1:by=py-y1 : if ax*by - ay*bx < 0 then return false     
  ax=x0-x2:ay=y0-y2:bx=px-x2:by=py-y2 : if ax*by - ay*bx < 0 then return false
  return true
end function

Compare it with the long complex version that use baric center coords.

Code: Select all

function PointInTriangle(x as single, y as single, _
                         x1 as single, y1 as single, _
                         x2 as single, y2 as single, _
                         x3 as single, y3 as single) as integer
    dim v0 as single = x3 - x1
    dim v1 as single = x2 - x1
    dim v2 as single = single(x) - x1
    dim u0 as single = y3 - y1
    dim u1 as single = y2 - y1
    dim u2 as single = single(y) - y1
    dim dot00 as single = v0 * v0 + u0 * u0
    dim dot01 as single = v0 * v1 + u0 * u1
    dim dot02 as single = v0 * v2 + u0 * u2
    dim dot11 as single = v1 * v1 + u1 * u1
    dim dot12 as single = v1 * v2 + u1 * u2
    dim invDenom as single = 1.0 / (dot00 * dot11 - dot01 * dot01)
    dim u as single = (dot11 * dot02 - dot01 * dot12) * invDenom
    dim v as single = (dot00 * dot12 - dot01 * dot02) * invDenom
    if (u >= 0) and (v >= 0) and (u + v <= 1) then
        PointInTriangle = 1
    else
        PointInTriangle = 0
    end if
end function

Test it out if you like.

Joshy

Code: Select all

' 3D cross product
' x = a.y*b.z - a.z*b.y
' y = a.z*b.x - a.x*b.z
' z = a.x*b.y - a.y*b.x

' clockwise order
' v0-----------v1  e0 = v1-v0
'  \ *        /    e1 = v2-v1
'   \  *     /     e2 = v0-v2
'    \   *p /      p0 = p-v0
'     \    /       p1 = p-v1
'      \  /        p2 = p-v2
'       \/
'       v2  
function PointInTriangle2D(byval px as single, byval py as single, _
                           byref x0 as single, byref y0 as single, _
                           byref x1 as single, byref y1 as single, _
                           byref x2 as single, byref y2 as single) as boolean
  dim as single ax=any,ay=any,bx=any,by=any
  ax=x1-x0:ay=y1-y0:bx=px-x0:by=py-y0 : if ax*by - ay*bx < 0 then return false
  ax=x2-x1:ay=y2-y1:bx=px-x1:by=py-y1 : if ax*by - ay*bx < 0 then return false     
  ax=x0-x2:ay=y0-y2:bx=px-x2:by=py-y2 : if ax*by - ay*bx < 0 then return false
  return true
end function

dim as long mx,my,colour
dim as boolean IsInside 
ScreenRes 640,480,8,2
ScreenSet 1, 0
windowtitle "move the mouse :-)"
while inkey()=""
  cls
  if getmouse(mx,my)=0 then
    IsInside = PointInTriangle2D(mx,my,100,100,400,200,500,400)  
  endif
  colour=iif(IsInside,2,4)
  pset (100,100),colour
  line -(400,200),colour
  line -(500,400),colour
  line -(100,100),colour   
  flip
  sleep 16
wend

[D.J.Peters]

One note:
The direction Z from the cross product points out or in the monitor plane depending of the triangle winding order.

clockwise versus counter clock !

if z < 0 then point_is_outside_of_triangle
or
if z > 0 then point_is_outside_of_triangle

Joshy

[dodicat]

Independent of order, it might take a split second longer to generalize PointInTriangle2D z component method, I just use 2d isleft
#define isleft(L1x,L1y,L2x,L2y,px,py) iif(Sgn((L1x-L2x)*(py-L2y)-(px-L2x)*(L1y-L2y))<0,1,0)
Then compile -pp flag to incorporate isleft

Code: Select all

Function PointInTriangle2D(Byval px As Single, Byval py As Single, Byref x0 As Single, Byref y0 As Single, Byref x1 As Single, Byref y1 As Single, Byref x2 As Single, Byref y2 As Single) As boolean
    Dim As Single ax=Any,ay=Any,bx=Any,by=Any
    ax=x1-x0:ay=y1-y0:bx=px-x0:by=py-y0 : If ax*by - ay*bx < 0 Then Return false
    ax=x2-x1:ay=y2-y1:bx=px-x1:by=py-y1 : If ax*by - ay*bx < 0 Then Return false
    ax=x0-x2:ay=y0-y2:bx=px-x2:by=py-y2 : If ax*by - ay*bx < 0 Then Return false
    Return true
End Function

Function intriangle(px As Single,py As Single,x1 As Single,y1 As Single, x2 As Single,y2 As Single, x3 As Single,y3 As Single) As Long
    If Iif(Sgn((x1-x2)*(py-y2)-(px-x2)*(y1-y2))<0,1,0) <> Iif(Sgn((x2-x3)*(py-y3)-(px-x3)*(y2-y3))<0,1,0) Then Return 0
    If Iif(Sgn((x2-x3)*(py-y3)-(px-x3)*(y2-y3))<0,1,0) <> Iif(Sgn((x3-x1)*(py-y1)-(px-x1)*(y3-y1))<0,1,0) Then Return 0
    Return 1
End Function

Screen 20
For n As Long=1 To 100
    Locate 2,2
    Color 4
    Print "dodicat"
    Locate 3,2
    Color 3
    Print "d.j.peters"
    Color 15
    Dim As Single x1=Rnd*1024,x2=Rnd*1024,x3=Rnd*1024
    Dim As Single y1=Rnd*768,y2=Rnd*768,y3=Rnd*768
    Line(x1,y1)-(x2,y2)
    Line(x2,y2)-(x3,y3)
    Line(x3,y3)-(x1,y1)
    
    Dim As Double t1=Timer
    For x As Single=0 To 1024
        For y As Single = 0 To 768
            If intriangle(x,y,x1,y1,x2,y2,x3,y3) Then Pset(x,y),4
        Next
    Next
    Print Timer-t1,"dodicat,press a key"
    Sleep
    t1=Timer
    
    For x As Single=0 To 1024
        For y As Single = 0 To 768
            If pointintriangle2d(x,y,x1,y1,x2,y2,x3,y3) Then Pset(x,y),3
        Next
    Next
    Print Timer-t1,"d.j.peters, press a key"
    Print
    Sleep
    Cls
Next n
Sleep