HomeUser Control Panel (unavailable in archive)ForumsTutorialsArt GalleryResourcesMaps

Point in a Triangle

01-31-2006, 12:03 PM#1
Jazradel
I wrote this code to check if a point is in a triangle, but it seems fairly inefficant to me. Anyone got any hints on how to improve it?
Code:
function IsPointOnSideOfLineAsPoint takes location loc, location locs, location loc1, location loc2 returns boolean
    local boolean check
    local real angle = AngleBetweenPoints(loc1, loc2)
    local real angle2 = AngleBetweenPoints(loc1, locs)
    local real angle3
    local real angle4 = AngleBetweenPoints(loc1, loc)
    local real angle5
    if angle2 < 0 then
        set angle2 = 360 + angle2
    endif
    if angle4 < 0 then
        set angle4= 360 + angle4
    endif
    set angle3 = angle2 - angle
    set angle5 = angle4 - angle
    if angle3 >= 0 and angle3 <= 180 then
        if angle5 >= 0 and angle5 <= 180 then
            set check = true
        else
            set check = false
        endif
    else
        if angle5 >= 0 and angle5 <= 180 then
            set check = false
        else
            set check = true
        endif
    endif
    return check
endfunction

function IsPointInTriangle takes location loc, location loc1, location loc2, location loc3 returns boolean
    local boolean check
    if IsPointOnSideOfLineAsPoint(loc, loc3, loc1, loc2) then
        if IsPointOnSideOfLineAsPoint(loc, loc1, loc2, loc3) then
            if IsPointOnSideOfLineAsPoint(loc, loc2, loc3, loc1) then
                set check = true
            else
                set check = false
            endif
        else
            set check = false
        endif
    else
        set check = false
    endif
    return check
endfunction
01-31-2006, 12:48 PM#2
Jacek
Check this:
http://www.idevgames.com/forum/archi...hp/t-9396.html
mostly Tasnu Arakun post.

or eventually get something from this (C++ too):

Code:
inline bool VertexInTriangle(vec3 vtxPoint,
                             vec3 vtx0,
                             vec3 vtx1,
                             vec3 vtx2)
{
    double dAngle;

    vec3 vec0 = Normalize( vtxPoint - vtx0 );
    vec3 vec1 = Normalize( vtxPoint - vtx1 );
    vec3 vec2 = Normalize( vtxPoint - vtx2 );

    dAngle =
        acos( DotProduct(vec0,vec1) ) + 
        acos( DotProduct(vec1,vec2) ) + 
        acos( DotProduct(vec2,vec0) ) ;


    if( fabs( dAngle - 2*pi ) < epsilon )
        return true;
else
return false;
}
sorry but I'm not into these things, just willing to help
01-31-2006, 01:36 PM#3
Vexorian
huh? http://www.wc3jass.com/viewtopic.php?t=237

that's the fastest way I could do.

Probably that c sample is faster but it requires you to make a bunch of vector functions, the extra calls would probably make it slower (an extra call in JASS is seriously slow)
01-31-2006, 03:02 PM#4
Jacek
Maybe, I just threw few links as reference.
01-31-2006, 08:58 PM#5
Jazradel
Well I'm only 15 so I have absolutely no idea how to do Dot Products. I tried for 3 days and all I got was a headache.

I has seen your code before Vex, and I couldn't get it to do exactly what I wanted. Your angle check just gave me a good idea to improve my code though.
01-31-2006, 09:07 PM#6
Anitarf
Vex, Daelin seems to have a better idea, although I haven't been able to yet figure out how it works... but it sure seems simple.

link
01-31-2006, 09:12 PM#7
Jazradel
Ohh wow. That owned me. Thanks Anitarf, that is a fantastic link.
01-31-2006, 10:21 PM#8
Vexorian
I dunno if Daelin's is better performance wise though cause it uses like 8 multiplications , and mine uses 2 Atan2 + soem comparissions, problem is again JASS' slowness, so I don't really know
02-01-2006, 04:45 AM#9
Jacek
I wanted to post Daelin's link too, I have it in my clipboard :D