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 The Helper:
    I am great and it is fantastic to see you my friend!
     +1
  • The Helper The Helper:
    Here is a great appetizer recipe Texas style! https://www.thehelper.net/threads/recipe-chicken-stuffed-poblano-peppers.194086/
  • The Helper The Helper:
    If you are new to the site please check out the Recipe and Food Forum https://www.thehelper.net/forums/recipes-and-food.220/
  • Monovertex Monovertex:
    How come you're so into recipes lately? Never saw this much interest in this topic in the old days of TH.net
  • Monovertex Monovertex:
    Hmm, how do I change my signature?
  • tom_mai78101 tom_mai78101:
    Signatures can be edit in your account profile. As for the old stuffs, I'm thinking it's because Blizzard is now under Microsoft, and because of Microsoft Xbox going the way it is, it's dreadful.
  • The Helper The Helper:
    I am not big on the recipes I am just promoting them - I use the site as a practice place promoting stuff
     +2
  • Monovertex Monovertex:
    @tom_mai78101 I must be blind. If I go on my profile I don't see any area to edit the signature; If I go to account details (settings) I don't see any signature area either.
  • The Helper The Helper:
    You can get there if you click the bell icon (alerts) and choose preferences from the bottom, signature will be in the menu on the left there https://www.thehelper.net/account/preferences
  • The Helper The Helper:
    I think I need to split the Sci/Tech news forum into 2 one for Science and one for Tech but I am hating all the moving of posts I would have to do
  • The Helper The Helper:
    New dessert for Summer - https://www.thehelper.net/threads/recipe-lemon-blueberry-layer-cheesecake.194113/
  • The Helper The Helper:
    What is up Old Mountain Shadow?
  • The Helper The Helper:
    Happy Thursday!
     +1
  • Varine Varine:
    Crazy how much 3d printing has come in the last few years. Sad that it's not as easily modifiable though
  • Varine Varine:
    I bought an Ender 3 during the pandemic and tinkered with it all the time. Just bought a Sovol, not as easy. I'm trying to make it use a different nozzle because I have a fuck ton of Volcanos, and they use what is basically a modified volcano that is just a smidge longer, and almost every part on this thing needs to be redone to make it work
  • Varine Varine:
    Luckily I have a 3d printer for that, I guess. But it's ridiculous. The regular volcanos are 21mm, these Sovol versions are about 23.5mm
  • Varine Varine:
    So, 2.5mm longer. But the thing that measures the bed is about 1.5mm above the nozzle, so if I swap it with a volcano then I'm 1mm behind it. So cool, new bracket to swap that, but THEN the fan shroud to direct air at the part is ALSO going to be .5mm to low, and so I need to redo that, but by doing that it is a little bit off where it should be blowing and it's throwing it at the heating block instead of the part, and fuck man
  • Varine Varine:
    I didn't realize they designed this entire thing to NOT be modded. I would have just got a fucking Bambu if I knew that, the whole point was I could fuck with this. And no one else makes shit for Sovol so I have to go through them, and they have... interesting pricing models. So I have a new extruder altogether that I'm taking apart and going to just design a whole new one to use my nozzles. Dumb design.
  • Varine Varine:
    Can't just buy a new heatblock, you need to get a whole hotend - so block, heater cartridge, thermistor, heatbreak, and nozzle. And they put this fucking paste in there so I can't take the thermistor or cartridge out with any ease, that's 30 dollars. Or you can get the whole extrudor with the direct driver AND that heatblock for like 50, but you still can't get any of it to come apart
  • Varine Varine:
    Partsbuilt has individual parts I found but they're expensive. I think I can get bits swapped around and make this work with generic shit though
  • Ghan Ghan:
    Heard Houston got hit pretty bad by storms last night. Hope all is well with TH.
  • The Helper The Helper:
    Power back on finally - all is good here no damage
     +2
  • V-SNES V-SNES:
    Happy Friday!
     +1
  • The Helper The Helper:
    New recipe is another summer dessert Berry and Peach Cheesecake - https://www.thehelper.net/threads/recipe-berry-and-peach-cheesecake.194169/
  • The Helper The Helper:
    New recipe is Cheeseburger Pie! https://www.thehelper.net/threads/recipe-cheeseburger-pie.194191/

      The Helper Discord

      Members online

      No members online now.
      Online now:
      161 (members: 2, guests: 159)

      Share this page

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top