Finding out where point X lies

[Nichilus]

Hi guys, I'm having a little problem finding out if point X lies in region or not.

Look at this graph:

I have 4 points - A, B, C and D, I know their x and y position on the graph. Connecting those 4 points creates a region.
If it helps, those 4 points are not static, but they are always placed so they create a rectangle (i.e. the angles ABD; BDC; DCA and CAB are 90°; ranges |AB| = |CD| and |AC| = |BD|).

Now I also have point X, I know its x and y position as well.
The thing I have problems with currently is finding out if X lies in the "region" created by points A, B, C and D.

Can someone help me with this?

----------------

 

[deathismyfriend]

I believe tht new made a snippet in the jass section for this. It should do exactly what u need

 

[Nichilus]

Is it possible to find out in GUI? I'm not really a Jass person
Anyway I'll take a look at it - maybe its math will help me after all.

Edit: uh, could you point me out in which thread it is? I'm not visiting jass section and I've no idea in which thread it may be

 

[deathismyfriend]

It is in the jass section. Not sure were. Basically all u do to use it is copy and paste it in ur map then use a custom script. Ill see if I can find it but I'm on my phone.

 

[Imp Midna]

The easiest Method i could come up with:

With
d = half of the width of the square
P = Point in the middle of the edge (px|py)
U = Vector to the other end (ax|ay)
---------------------------------------
X = The Point you are checking (x|y)
V = Perpendicular (ay|-ax)

- To get the Point of Intersection of U and V:
P+r*U = X+s*V
-->
r = -((ax*px+ay*py - ax*x-ay*y)/(ax^2+ay^2))
Then use r to get the Point of Intersection using P+r*U
edit: garfield is right. if r is not inside of [0,1], its wrong allready. Totally forgot about that case.
- Calculate the distance between X and the Point of Intersection:
Temp = PointOfIntersection - X
Distance = |PointOfIntersection| (Sqrt(x^2+y^2), guess you know this one)
- If Distance > d -> outside
else d -> inside

example (trying to guess the positions in your picture):
d = 1
P = {px,py} = {-3.8,-3}
U = {ax,ay} = {6,5}
---------------------
X = {x,y} = {-3.8,1.5}
V = {ay,-ax} = {5,-6}

r = -((ax*px+ay*py - ax*x-ay*y)/(ax^2+ay^2))
= -((6*-3.8 + 5*(-3) - 6*(-3.8) - 5*1.5) / (6^2+5^2))
= 0.368852
poi = P+r*U = (px,py)+0.368852*{ax,ay} = {-3.8,-3}+0.368852*{6,5}
= {-1.58689 , -1.15574}
Temp = poi - x = {-1.58689 , -1.15574} - {-3.8 , 1.5}
= {2.21311, -2.65574}
Distance = Sqrt( (2.21311)^2 + (-2.65574)^2 ) = 3.45699

3.45699 > 1 -> not inside

x,y = 0 would yield 0.128036 < 1 -> inside

Might wanna do some examples, should work.
Also, you might get around the Squareroot if you save d^2 rather than d. d will then of corse not be the exact width, but it will still work for comparisions.

 

[Garfield1337]

I've found the function by Nestharus

library IsPointInRectangle
    //determins if point P is in rectangle ABCD
    function IsPointInRectangle takes real ax, real ay, real bx, real by, real cx, real cy, real dx, real dy, 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)
        local real cross4 = (py-dy)*(ax-dx)-(px-dx)*(ay-dy)
       
        return ((cross0*cross1 >= 0) and (((py-by)*(cx-bx)-(px-bx)*(cy-by))*cross1 >= 0)) or ((cross0*cross4 >= 0) and (((py-by)*(dx-bx)-(px-bx)*(dy-by))*cross4 >= 0))
    endfunction
endlibrary

You can also find other coordinate snippets in this post
http://www.hiveworkshop.com/forums/1838224-post336.html

To use the function, use a custom script and write this: set udg_Boolean = IsPointInRectangle(udg_x1, udg_y1, udg_x2, udg_y2, udg_x3, udg_y3, udg_x4, udg_y4, udg_px, udg_py)
where Boolean is a boolean variable (you can rename it); x1, y1; x2, y2; x3, y3; x4, y4 are rectangle vertex coordinates and px and py are point coordinates.
You have to add "udg_" preffix when using variables from variable editor in JASS.
Now you can use the boolean variable in an if/then/else statement.

@Imp Midna,
What if the X was right next to P, but outside of rectangle? You would've got wrong result.

 

[Nichilus]

Thanks guys

 

[deathismyfriend]

Thanks for finding it lol I couldn't find it on my phone lol.

 

[Imp Midna]

@Imp Midna,
What if the X was right next to P, but outside of rectangle? You would've got wrong result.

Ua, your right. Forgot to check if r is in [0,1]. Sorry about that one

 

[Nestharus]

That IsPointInRectangle function, if I'm not mistaken, is a little bit buggy.

 

[Nichilus]

Hmm doesn't work
I copied the line garfield posted and changed it, but it didn't work, I simplified to look like the one he posted, it still doesn't work.
Here's the line:

• Custom script: set udg_IsIn = IsPointInRectangle(udg_x1, udg_y1, udg_x2, udg_y2, udg_x3, udg_y3, udg_x4, udg_y4, udg_px, udg_py)

when I save the map, an error "1645: Expected a name" appears, disabling that trigger.

Does anyone know what I did wrong?
IsIn is boolean (tried to simplify the name as much as I could), all x and y and px and py are reals
I'm saving x and y of a point using

• Set x1 = (X of Temp_Point[1])

and for y the Y of point function

 

[Imp Midna]

I must confess that my math skills are rather limited (to the bit math we learn in school), but judging by the variable names used in the snipet, it seems to be using a cross-line-algorithm. I'm too stupid to understand them, but I'm pretty sure they need to have the points of the geometrical figure in a special order (usually counter-clockwise) in order to be able to find the correct borders and work. If you saved your points like they look like in the picture you gave us, it probably wont work as A-C-D-B is not the order the algorithm expects.

 

[Nichilus]

Still doesn't work. I took your advice and changed calculation of points.

If you look at this pic (same as in first post), I first changed calculation for points A and B to swap them, then I had A-B-C-D in counter-clockwise direction, but it still gave me the same error.
I also changed those calculations so I got A-B-C-D in clockwise direction, but that didn't work as well.

I'm not sure if it's of any help, but whenever I get the error, the error window points at the udg_px udg_py part of

• Custom script: set udg_IsIn = IsPointInRectangle(udg_x1, udg_y1, udg_x2, udg_y2, udg_x3, udg_y3, udg_x4, udg_y4, udg_px, udg_py)

(though that is also the end of the script, so I'm unsure if the window doesn't simply point at the end of the line)

 

[Garfield1337]

The custom script looks ok. Make sure you named the variables properly.
Don't give them udg_ preffix in variable editor, just name them x1, y1, x2, y2... (only in the code should you use udg_)

 

[Nichilus]

yes I know that. At first I used real array called x and y, so I had x[1]-x[4] and y[1]-y[4] and px and py real variables for the point in question. Since that didn't work, I created instead 4 different variables - x1; x2; x3 and x4, same for y; as well as changed name of boolean to "IsIn", to see if that makes difference; but it didn't.

I'll post the whole trigger here, maybe the problem lies somewhere else in that trigger or I'm still doing the same error without realizing it.

Click

• Trigger
  • Events
  • Conditions
  • Actions
    • -------- -------------------------------------------------------------------------------- --------
    • -------- ---------- SET UP --------
    • Set Temp_Group = (Units within 1000.00 of (Center of Center <gen>) matching ((((Matching unit) belongs to an ally of (Owner of Boss)) Equal to False) and (((Matching unit) is alive) Equal to True)))
    • Set Temp_Point[1] = (Position of AnBeam_Units[1])
    • Set Temp_Point[2] = (Position of AnBeam_Units[2])
    • For each (Integer LoopIntegerA) from 1 to 2, do (Actions)
      • Loop - Actions
        • Set Temp_Point[(2 + LoopIntegerA)] = (Temp_Point[1] offset by 20.00 towards ((Angle from Temp_Point[1] to Temp_Point[2]) + (90.00 + (180.00 x (Real(LoopIntegerA))))) degrees)
        • Set Temp_Point[(4 + LoopIntegerA)] = (Temp_Point[2] offset by 20.00 towards ((Angle from Temp_Point[2] to Temp_Point[1]) + (90.00 - (180.00 x (Real(LoopIntegerA))))) degrees)
    • Set x1 = (X of Temp_Point[3])
    • Set x2 = (X of Temp_Point[4])
    • Set x3 = (X of Temp_Point[5])
    • Set x4 = (X of Temp_Point[6])
    • Set y1 = (Y of Temp_Point[3])
    • Set y2 = (Y of Temp_Point[4])
    • Set y3 = (Y of Temp_Point[5])
    • Set y4 = (Y of Temp_Point[6])
    • Custom script: call RemoveLocation(udg_Temp_Point[1])
    • Custom script: set udg_Temp_Point[1] = null
    • For each (Integer LoopIntegerA) from 2 to 6, do (Actions)
      • Loop - Actions
        • Set Temp_Point[1] = Temp_Point[LoopIntegerA]
        • Custom script: call RemoveLocation(udg_Temp_Point[1])
        • Custom script: set udg_Temp_Point[1] = null
    • -------- -------------------------------------------------------------------------------- --------
    • -------- -------------------------------------------------------------------------------- --------
    • -------- -------------------------------------------------------------------------------- --------
    • Unit Group - Pick every unit in Temp_Group and do (Actions)
      • Loop - Actions
        • Set Temp_Point[1] = (Position of (Picked unit))
        • Set px = (X of Temp_Point[1])
        • Set py = (Y of Temp_Point[1])
        • Custom script: set udg_IsIn = IsPointInRectangle(udg_x1, udg_y1, udg_x2, udg_y2, udg_x3, udg_y3, udg_x4, udg_y4, udg_px, udg_py)
        • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
          • If - Conditions
            • IsIn Equal to True
          • Then - Actions
            • Set IsIn = False
            • Unit - Kill (Picked unit)
          • Else - Actions
        • Custom script: call RemoveLocation(udg_Temp_Point[1])
        • Custom script: set udg_Temp_Point[1] = null
    • Custom script: call DestroyGroup(udg_Temp_Group)
    • Custom script: set udg_Temp_Group = null

 

[gorillabull]

use this instead i think it exists as a gui function

function RectContainsCoords takes rect r, real x, real y returns boolean
    return (GetRectMinX(r) <= x) and (x <= GetRectMaxX(r)) and (GetRectMinY(r) <= y) and (y <= GetRectMaxY(r))
endfunction

edit
yes you can use it in gui too
[trigger=asdf]
asdf
Events
Conditions
((Playable map area) contains (Center of (Playable map area))) Equal to True
Actions
[/trigger]

this will return true if the point lies on the region so use it in a condition

 

[deathismyfriend]

problem is that that makes a square or rectangular rect. It doesnt make a rect at an angle like the rect in the graph.

 

[gorillabull]

haha yea missed that well then nes' algorithm is fine but you have to know how to copy it to the map just try copying the function without the library in the map script and see if it works

 

[deathismyfriend]

nes said his system was a little buggy tho. So not sure what the best thing is for this then.

 

[rulerofiron99]

Ugh.

Here's a neat little system:
http://www.wc3c.net/showthread.php?t=96543

 

[deathismyfriend]

Wow thats pretty neat lol and it does any shape u want.

 

[Nichilus]

Seems like it will work (though it's in jass, which I wanted to avoid :< )
Still, I guess I can't have everything the way I want, so I appreciate it.

Thank you all for help.