[vJASS] Is Point In Triangle

[Reventhous]

I've read this Barycentric coordinate system - Wikipedia and I found the way to determine if a point in a triangle. Here is it

library IsPointInTriangle
    function IsPointInTriangle takes real x, real y, real x1, real y1, real x2, real y2, real x3, real y3 returns boolean
        //denominator
        local real d = ((y2 - y3)*(x1 - x3) + (x3 - x2)*(y1 - y3))
        //express new p coordinates as a linear combination of a, b, c
        local real a = ((y2 - y3)*(x - x3) + (x3 - x2)*(y - y3)) / d
        local real b = ((y3 - y1)*(x - x3) + (x1 - x3)*(y - y3)) / d
        local real c = 1 - a - b
       
        return 0 <= a and a <= 1 and 0 <= b and b <= 1 and 0 <= c and c <= 1
    endfunction
endlibrary

Please tell me if I did something wroing because I'm about to create a new system (I think) and it uses this snippet.

 

[Pyrogasm]

Looks correct to me.

 

[Elprede]

library IsPointInTriangle
//check to see if a point P is in triangle ABC
   function IsPointInTriangle takes real ax, real ay, real bx, real by, real cx, real cy, real px, real py returns boolean
       local real cross0 = (py-ay)*(bx-ax)-(px-ax)*(by-ay)
       local real cross1 = (py-cy)*(ax-cx)-(px-cx)*(ay-cy)
       return (cross0*cross1 >= 0) and (((py-by)*(cx-bx)-(px-bx)*(cy-by))*cross1 >= 0)
   endfunction
endlibrary

 

[Aniki]

From this SO answer:

function IsPointInTriangle takes real px, real py, real ax, real ay, real bx, real by, real cx, real cy returns boolean
    local boolean b1 = (px - bx) * (ay - by) - (ax - bx) * (py - by) < 0.0
    local boolean b2 = (px - cx) * (by - cy) - (bx - cx) * (py - cy) < 0.0
    local boolean b3 = (px - ax) * (cy - ay) - (cx - ax) * (py - ay) < 0.0
    return b1 == b2 and b2 == b3
endfunction

 

[IcemanBo]

Moved thread to Triggers & Scripts.

 

[Dr Super Good]

Please tell me if I did something wroing because I'm about to create a new system (I think) and it uses this snippet.

Worth testing it rather than trying to get others to look for mistakes that may or may not be there.

Come up with a few examples and check if the results are what is expected.

 

[Wietlol]

I have 2 functions

    //excludes boundaries
    public static boolean isPointInTriangle1(
            float px, float py,
            float ax, float ay,
            float bx, float by,
            float cx, float cy)
    {
        boolean b1 = (px - bx) * (ay - by) - (ax - bx) * (py - by) < 0.0f;
        boolean b2 = (px - cx) * (by - cy) - (bx - cx) * (py - cy) < 0.0f;
        boolean b3 = (px - ax) * (cy - ay) - (cx - ax) * (py - ay) < 0.0f;
    
        return ((b1 == b2) && (b2 == b3));
    }
 
    //includes boundaries
    public static boolean isPointInTriangle2(
            float px, float py,
            float ax, float ay,
            float bx, float by,
            float cx, float cy)
    {
        float a = ((by - cy)*(px - cx) + (cx - bx)*(py - cy)) / ((by - cy)*(ax - cx) + (cx - bx)*(ay - cy));
        float b = ((cy - ay)*(px - cx) + (ax - cx)*(py - cy)) / ((by - cy)*(ax - cx) + (cx - bx)*(ay - cy));
        float c = 1 - a - b;
    
        return 0 <= a && a <= 1 &&
               0 <= b && b <= 1 &&
               0 <= c /*&& c <= 1*/;
    }

The first one excludes the lines while the second one includes the lines.
Aka, if you have a triangle (0, 0) (1,0) (0,1), then the point (0,0) would return false in the first and true in the second.
There shouldnt be much difference in performance... at least in Java.

The JASS code equivalent:

//excludes boundaries
function isPointInTriangle1 takes real px, real py, real ax, real ay, real bx, real by, real cx, real cy returns boolean
    local boolean b1 = (px - bx) * (ay - by) - (ax - bx) * (py - by) < 0.0
    local boolean b2 = (px - cx) * (by - cy) - (bx - cx) * (py - cy) < 0.0
    local boolean b3 = (px - ax) * (cy - ay) - (cx - ax) * (py - ay) < 0.0
 
    return ((b1 == b2) and (b2 == b3))
endfunction

//includes boundaries
function isPointInTriangle2 takes real px, real py, real ax, real ay, real bx, real by, real cx, real cy returns boolean
    local real pxMcx = px - cx
    local real pyMcy = py - cy
    local real t = (by - cy)*(ax - cx) + (cx - bx)*(ay - cy)
    local real a = ((by - cy)*(pxMcx) + (cx - bx)*(pyMcy)) / t
    local real b = ((cy - ay)*(pxMcx) + (ax - cx)*(pyMcy)) / t
    local real c = 1 - a - b
 
    return (0 <= a and a <= 1 and 0 <= b and b <= 1 and 0 <= c /*and c <= 1*/)
endfunction

EDIT:
Silly mistake by me, in the second one, you dont have to check if c is smaller than or equal to 1.
Assuming that a and b both are larger than or equal to 0, c can never be larger than 1.
EDIT:
Another slight optimization by cutting of the last parts of the formulas (which are the same) in the second function.