Snippet IsCoordInTriangle

Cookiemaster

Cookiemaster

New Member
Reaction score
36
What does it do?

It "constructs" a triangle with the given points (AX,AY),(BX,BY),(CX,CY) and checks if point (DX,DY) is in it, returning a boolean.

Using triangles, you could also check if a point is in a certain-shaped area.
shapes.png

Simply use "or" conditions together with the triangle check, to check if a point is in any of the triangles, which would mean the point is in the shape.



The functions.

First, for it to work properly, it needed a function that returns an angle between two points as a radiant value between 0 and 2Pi. (Unlike the -Pi~Pi Atan2(y,x) returns.)
For that; there is this function:
JASS:
//Returns the angle between points (AX,AY) and (BX,BY) as radiants between 0 and 2Pi.
function GetAngleBetweenCoords takes real AX, real AY, real BX, real BY returns real
    local real angle = Atan2(BY-AY,BX-AX)
    if angle < 0 then
        return angle + 2*bj_PI
    endif
    return angle
endfunction


With that, the triangle check is possible with simply this function:
JASS:
//Coords A, B and C are the corners of the triangle, coord D is the tested coord.
function IsCoordInTriangle takes real AX, real AY, real BX, real BY, real CX, real CY, real DX, real DY returns boolean
    local real AB = GetAngleBetweenCoords(AX,AY,BX,BY)
    local real BC = GetAngleBetweenCoords(BX,BY,CX,CY)
    local real CA = GetAngleBetweenCoords(CX,CY,AX,AY)
    local boolean clockwise = (((AB < BC and AB < CA) and BC > CA) or ((BC < AB and BC < CA) and AB > CA) or ((CA < AB and CA < BC) and AB > BC))
    local real AD = GetAngleBetweenCoords(AX,AY,DX,DY) + (3*bj_PI - AB)
    local real BD = GetAngleBetweenCoords(BX,BY,DX,DY) + (3*bj_PI - BC)
    local real CD = GetAngleBetweenCoords(CX,CY,DX,DY) + (3*bj_PI - CA)
    set AD = AD - ( I2R(R2I(AD/(2*bj_PI))) * (2*bj_PI) )
    set BD = BD - ( I2R(R2I(BD/(2*bj_PI))) * (2*bj_PI) )
    set CD = CD - ( I2R(R2I(CD/(2*bj_PI))) * (2*bj_PI) )
    return (AD>bj_PI and BD>bj_PI and CD>bj_PI and clockwise == false) or (AD<=bj_PI and BD<=bj_PI and CD<=bj_PI and clockwise == true)
endfunction



Because people in GUI are too lazy to learn jass;

I've made a function that takes points and calls IsCoordInTriangle.
It's basically the same, but uses locations (A,B,C,D) instead of coords (AX,AY,BX,BY,CX,CY,DX,DY):

JASS:
//Locations A, B and C are the corners of the triangle, location D is the tested point.
function IsLocationInTriangle takes location A, location B, location C, location D returns boolean
    local real AX = GetLocationX(A)
    local real AY = GetLocationY(A)
    local real BX = GetLocationX(B)
    local real BY = GetLocationY(B)
    local real CX = GetLocationX(C)
    local real CY = GetLocationY(C)
    local real DX = GetLocationX(D)
    local real DY = GetLocationY(D)
    return IsCoordInTriangle(AX,AY,BX,BY,CX,CY,DX,DY)
endfunction

This can be used in GUI in this way:

Trigger:
  • Actions
    • -------- LocationCorner is an array point variable. --------
    • Set LocationCorner[1] = (Random point in (Playable map area))
    • Set LocationCorner[2] = (Random point in (Playable map area))
    • Set LocationCorner[3] = (Random point in (Playable map area))
    • -------- LocationCheck is a point variable. --------
    • Set LocationCheck = (Center of (Playable map area))
    • -------- ReturnedBoolean is a boolean variable. --------
    • Custom script: set udg_ReturnedBoolean = IsLocationInTriangle(udg_LocationCorner[1],udg_LocationCorner[2],udg_LocationCorner[3],udg_LocationCheck)
    • -------- You could basically use any variable as substitute, but don't forget that variables made through the variable editor have udg_ as prefix. --------
    • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
      • If - Conditions
        • ReturnedBoolean Equal to True
      • Then - Actions
        • -------- The point LocationCheck is in the triangle formed by LocationCorner[1~3]. --------
      • Else - Actions
        • -------- The point LocationCheck is not in the triangle formed by LocationCorner[1~3]. --------
P.S. LEAKS@@!!@!



Implementing.

Create a new trigger, convert it to custom text (under edit), and replace all the text with the following: (If you don't want to use the IsLocationInTriangle function, then just remove it yourself.)
JASS:
function GetAngleBetweenCoords takes real AX, real AY, real BX, real BY returns real
    local real angle = Atan2(BY-AY,BX-AX)
    if angle < 0 then
        return angle + 2*bj_PI
    endif
    return angle
endfunction

function IsCoordInTriangle takes real AX, real AY, real BX, real BY, real CX, real CY, real DX, real DY returns boolean
    local real AB = GetAngleBetweenCoords(AX,AY,BX,BY)
    local real BC = GetAngleBetweenCoords(BX,BY,CX,CY)
    local real CA = GetAngleBetweenCoords(CX,CY,AX,AY)
    local boolean clockwise = (((AB < BC and AB < CA) and BC > CA) or ((BC < AB and BC < CA) and AB > CA) or ((CA < AB and CA < BC) and AB > BC))
    local real AD = GetAngleBetweenCoords(AX,AY,DX,DY) + (3*bj_PI - AB)
    local real BD = GetAngleBetweenCoords(BX,BY,DX,DY) + (3*bj_PI - BC)
    local real CD = GetAngleBetweenCoords(CX,CY,DX,DY) + (3*bj_PI - CA)
    set AD = AD - ( I2R(R2I(AD/(2*bj_PI))) * (2*bj_PI) )
    set BD = BD - ( I2R(R2I(BD/(2*bj_PI))) * (2*bj_PI) )
    set CD = CD - ( I2R(R2I(CD/(2*bj_PI))) * (2*bj_PI) )
    return (AD>bj_PI and BD>bj_PI and CD>bj_PI and clockwise == false) or (AD<=bj_PI and BD<=bj_PI and CD<=bj_PI and clockwise == true)
endfunction

function IsLocationInTriangle takes location A, location B, location C, location D returns boolean
    local real AX = GetLocationX(A)
    local real AY = GetLocationY(A)
    local real BX = GetLocationX(B)
    local real BY = GetLocationY(B)
    local real CX = GetLocationX(C)
    local real CY = GetLocationY(C)
    local real DX = GetLocationX(D)
    local real DY = GetLocationY(D)
    return IsCoordInTriangle(AX,AY,BX,BY,CX,CY,DX,DY)
endfunction

Additionally, this could be slightly faster by creating two variables to replace 2*Pi and 3*Pi in the first two functions. For that; refer to this version that uses vJass: (And thus requires something that can compile it, such as Newgen.)

JASS:

globals
    constant real II_PI = 2*bj_PI
    constant real III_PI = 3*bj_PI
endglobals

function GetAngleBetweenCoords takes real AX, real AY, real BX, real BY returns real
    local real angle = Atan2(BY-AY,BX-AX)
    if angle < 0 then
        return angle + II_PI
    endif
    return angle
endfunction

function IsCoordInTriangle takes real AX, real AY, real BX, real BY, real CX, real CY, real DX, real DY returns boolean
    local real AB = GetAngleBetweenCoords(AX,AY,BX,BY)
    local real BC = GetAngleBetweenCoords(BX,BY,CX,CY)
    local real CA = GetAngleBetweenCoords(CX,CY,AX,AY)
    local boolean clockwise = (((AB < BC and AB < CA) and BC > CA) or ((BC < AB and BC < CA) and AB > CA) or ((CA < AB and CA < BC) and AB > BC))
    local real AD = GetAngleBetweenCoords(AX,AY,DX,DY) + (III_PI - AB)
    local real BD = GetAngleBetweenCoords(BX,BY,DX,DY) + (III_PI - BC)
    local real CD = GetAngleBetweenCoords(CX,CY,DX,DY) + (III_PI - CA)
    set AD = AD - ( I2R(R2I(AD/(II_PI))) * (II_PI) )
    set BD = BD - ( I2R(R2I(BD/(II_PI))) * (II_PI) )
    set CD = CD - ( I2R(R2I(CD/(II_PI))) * (II_PI) )
    return (AD>bj_PI and BD>bj_PI and CD>bj_PI and clockwise == false) or (AD<=bj_PI and BD<=bj_PI and CD<=bj_PI and clockwise == true)
endfunction

function IsLocationInTriangle takes location A, location B, location C, location D returns boolean
    local real AX = GetLocationX(A)
    local real AY = GetLocationY(A)
    local real BX = GetLocationX(B)
    local real BY = GetLocationY(B)
    local real CX = GetLocationX(C)
    local real CY = GetLocationY(C)
    local real DX = GetLocationX(D)
    local real DY = GetLocationY(D)
    return IsCoordInTriangle(AX,AY,BX,BY,CX,CY,DX,DY)
endfunction


Inevitable Q&A:

Q: How does this work?
A: It checks the angles between the given points, compares them and with that, decides on which side of each line the point is. Then it can simply say if the point is in or outside of the triangle.

Q: Does it matter in which order you enter the points of the triangle?
A: No.

Q: Why isn't the location removed/destroyed/whatever in the location-version?
A: Maybe they might want to use the location somewhere in the trigger that does the check.

Q: YOUR GUI-TRIGGER LEAKS FOUR POINTS
A: OK

Q: How do I make round things (cones/circles/etc.) with this?
A: Not.

If the functions could in some way be slightly faster, please tell me so.
 
Jesus4Lyf

Jesus4Lyf

Good Idea™
Reaction score
397
>If the functions could in some way be slightly faster, please tell me so.
You can do this without any native calls.

Angles are slow... Use vectors.

Maybe this:

Lets say you have:

.............
......B......
...../..\....
....A--C...
..............

Sort your points by x, so they are in that order.
Gradient from A to point must be between gradient from A to C and gradient from A to B.
Gradient from point to C must be greater than gradient from B to C.

Did I miss something?

(If any points are on the same x coordinate, use a different set of calculations. Use "if" for this.)
 
kingkingyyk3

kingkingyyk3

Visitor (Welcome to the Jungle, Baby!)
Reaction score
216
JASS:
    set A = null
    set B = null
    set C = null
    set D = null


No need, since it is an argument and Warcraft will clean it automatically.
 
roXplosive

roXplosive

New Member
Reaction score
15
There is a simpler way to do this thingy . Did you ever think of approapching it as a system of inecuations and obtaining the truth value this way ?

I'll give you an example :

A) The equation of a line between points A(xa,ya) and B(xb,yb) is
(x-xa)/(xb-xa)=(y-ya)/(yb-ya)

that becomes : (x-xa)*(yb-ya)-(y-ya)*(xb-xa)=0

That can be rewritten into the generic equation of the line :
Ax+By+C=0 ; A,B,C real constants . If we divide by B (considering it's nenull) and rearranging we get the most used shape of the line func
y=mx+n ; m is the incline of the line and is also the tangent of the angle the line makes with the 0x axis
or f(x,y)=0 where f(x,y)=y-mx-n


This defines ALL the points that are on the given line
B) Say the line we are using is the last form of it and we have the point P(x , mx+n+k) where k>0 .

f(x,mx+n+k)= mx+n+k-mx-n = k > 0

We all agree that the points P(x,mx+n+k) are above the points D(x,mx+n) situated on the given line . So we can conclude that points for which the equation of the line returns a positive value are situated above the line . There is a posibility to have a line of the shape a*x+0*y=constant ; for this all points to the right if a>0 are verifying the condition that inserted the coordinates in the line's equation it results a positive value .

3. For random points A,B,C of the triangle it is difficult to imagine how to determine which inequations we are going to use to determine if a point is in the area of the triangle . It has to verify all 3 correct inequations . The problem is that we don't know how to choose 1 inequation from 2 possible .... but we know don't we that the centre of the inscribed in the triangle circle is situated on points that have coordinates equal to arithmetic media of the 3 points defining the triangle . And it's obvious that point is inside the triangle since all the inscribed circle is inside the triangle .

Using theese premises here is the code (i made it this way because I belive it's easyer to give parameters locations of units and changing it is easy :

JASS:

function Inside takes location A , location B , location C , location P returns boolean
local real xa=GetLocationX(A)
local real ya=GetLocationY(A)
local real xb=GetLocationX(B)
local real yb=GetLocationY(B)
local real xc=GetLocationX(C)
local real yc=GetLocationY(C)
local real xcenter=(xa+xb+xc)/3
local real ycenter=(ya+yb+yc)/3
local real xp=GetLocationX(P)
local real yp=GetLocationY(P)
local real inec1sign=RsignBJ((xcenter-xa)*(yb-ya)-(ycenter-ya)*(xb-xa))
local real inec2sign=RsignBJ((xcenter-xb)*(yc-yb)-(ycenter-yb)*(xc-xb))
local real inec3sign=RsignBJ((xcenter-xc)*(ya-yc)-(ycenter-yc)*(xa-xc))
return ((xp-xa)*(yb-ya)-(yp-ya)*(xb-xa))*inec1sign>=0 and ((xp-xb)*(yc-yb)-(yp-yb)*(xc-xb))*inec2sign>=0 and ((xp-xc)*(ya-yc)-(yp-yc)*(xa-xc))*inec3sign>=0
endfunction


@ OP for all the convex planar figures this reduces simply to checking if the point verifies cetrain sets of inequations . For concave figures I advise patience or use your brain and think of another method

Sense and simplicity (C) Philips LOL
 
Jesus4Lyf

Jesus4Lyf

Good Idea™
Reaction score
397
I wasn't sure whether or not to approve this, because the author seems to have lost interest and it is really very inefficient.

Then I remembered that in ~6-7 years of mapping, I've never needed this or seen it asked for.

Graveyarded.

But if people feel this should be approved, voice it please and we shall discuss it. :)
 
You must log in or register to reply here.
General chit-chat
Help Users
  • No one is chatting at the moment.

      The Helper Discord

      Staff online

      Members online

      Online now:
      638 (members: 1, guests: 637)

      Share this page

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top