QB64 Phoenix Edition
Detect point in triangle (2D) - Printable Version

+- QB64 Phoenix Edition (https://qb64phoenix.com/forum)
+-- Forum: QB64 Rising (https://qb64phoenix.com/forum/forumdisplay.php?fid=1)
+--- Forum: Prolific Programmers (https://qb64phoenix.com/forum/forumdisplay.php?fid=26)
+---- Forum: Petr (https://qb64phoenix.com/forum/forumdisplay.php?fid=52)
+---- Thread: Detect point in triangle (2D) (/showthread.php?tid=3221)



Detect point in triangle (2D) - Petr - 11-20-2024

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/2049582/how-to-determine-if-a-point-is-in-a-2d-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



RE: Detect point in triangle (2D) - bplus - 11-20-2024

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.


RE: Detect point in triangle (2D) - Petr - 11-20-2024

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