Detect point in triangle (2D)

[Petr]

Hi. I needed to write a function for arrows in the game Puzzle and from that came the need to write or get a function for detecting a point in a triangle. I found a beautiful solution in C++. So I am attaching the original source code in C++ but of course also my version in QB64 which is based on it. The source code also includes a link to the original source. I think it might be useful for someone someday (and I also know that I will save it on my computer so that I can find it, so I will never find it again).

I tried some combinations of points and it seems to work correctly. If you encounter a problem, write it here. I am not entirely sure of the meaning of the last line in C++: return d == 0 || (d < 0) == (s + t <= 0); and it is possible that I did not understand it correctly. I am not good with C++.

Code: (Select All)

'Since have only touched the C++ language remotely and am not fully confident in the correct translation, am leaving the original here for review by those who know C++ better than me.

'Source: https://stackoverflow.com/questions/2049...d-triangle



'public static bool PointInTriangle(Point p, Point p0, Point p1, Point p2)

'{

'    var s = (p0.X - p2.X) * (p.Y - p2.Y) - (p0.Y - p2.Y) * (p.X - p2.X);

'    var t = (p1.X - p0.X) * (p.Y - p0.Y) - (p1.Y - p0.Y) * (p.X - p0.X);



'    if ((s < 0) != (t < 0) && s != 0 && t != 0)

'        return false;



'    var d = (p2.X - p1.X) * (p.Y - p1.Y) - (p2.Y - p1.Y) * (p.X - p1.X);

'    return d == 0 || (d < 0) == (s + t <= 0);

'}

Screen _NewImage(1024, 768, 256)



Type XY

    As Integer x, y

End Type







Do

    While _MouseInput

    Wend

    mx = _MouseX

    my = _MouseY



    Dim Shared As XY p, p0, p1, p2

    p.x = mx

    p.y = my

    p0.x = 350

    p0.y = 140

    p1.x = 350

    p1.y = 340

    p2.x = 750 '800

    p2.y = 240



    Cls

    Line (p1.x, p1.y)-(p0.x, p0.y)

    Line (p0.x, p0.y)-(p2.x, p2.y)

    Line (p1.x, p1.y)-(p2.x, p2.y)

    Locate 1

    Print PiT(p, p0, p1, p2)

    _Display

    _Limit 20



Loop



Function PiT (p As XY, p0 As XY, p1 As XY, p2 As XY)

    s = (p0.x - p2.x) * (p.y - p2.y) - (p0.y - p2.y) * (p.x - p2.x)

    t = (p1.x - p0.x) * (p.y - p0.y) - (p1.y - p0.y) * (p.x - p0.x)

    d = (p2.x - p1.x) * (p.y - p1.y) - (p2.y - p1.y) * (p.x - p1.x)

    If Sgn(d) = Sgn(t) And Sgn(t) = Sgn(s) And Sgn(t) <> 0 Then PiT = 1

    ' d, s, t - if are all three positive / all three negative ---> point is in triangle

End Function

[bplus]

Wow I was just looking at MasterGy's PointInTriangle here:
https://qb64phoenix.com/forum/showthread.php?tid=2134
last night.

Looks like a common task needed from comments to his and now yours.

[Petr]

Hi BPlus, I didn't know that. I could have saved myself some time Yeah, MasterGy is very good. Thanks for the link.