# GM:S 1.4 [SOLVED] Point in quadrilateral?

Discussion in 'Programming' started by marasovec, Oct 12, 2019 at 8:33 PM.

1. ### marasovecMember

Joined:
Sep 15, 2016
Posts:
324
I have an isometric game where enemies use mp_grid. To save some time I'd like to check if the randomly selected target point is actually in the playable area

2. ### flyingsaucerinvasionMember

Joined:
Jun 20, 2016
Posts:
2,166
Can you tell us how you are drawing your game? In other words, if we knew how you get from the game's world space to what you see drawn on the view, we could tell you have to reverse the process.

EDIT:

But in general, if (x,y) is a point in the world, and (x1,y1) is an isometric projection of that point, and the projection can be described like this:

x1 = x*a + y*c
y1 = x*b + y*d

That is, moving 1 unit along the world's x axis, will move you the length and direction of the vector (a,b) in the isometric projection.
and moving 1 unit along the world's y axis will move you along a vector (c,d) on the isometric proejction.

then the inverse is

x = ( x1*d - y1*c)/(a*d - b*c)
y = (-y1*b + x1*a)/(a*d - b*c)

Last edited: Oct 13, 2019 at 6:28 PM
3. ### SnotWaffle StudiosMember

Joined:
Jun 21, 2016
Posts:
288
You can pass a line from your point in any direction and if it intersects with your quadrilateral an odd number of times, it's inside.

4. ### ParodyKnaveBobThe Laughing Rogue

Joined:
Jun 23, 2016
Posts:
537
Howdy, Marasovec,

One sure-fire shortcut way would be to run collision-in-triangle twice. (Or once if it's true on the first because then you don't need to check the second half of the parallelogram.)

I hope this helps. \$:^ J

marasovec likes this.
5. ### marasovecMember

Joined:
Sep 15, 2016
Posts:
324
Lmao that's genius
I've never thought about that as an area made of 2 triangles

6. ### flyingsaucerinvasionMember

Joined:
Jun 20, 2016
Posts:
2,166
I misunderstood your problem. I presumed you were using an isometric transformation to go from world to view space. I also presumed the random point you wanted to check was a point in view space.

However, my original answer can actually be used to provide a speedy solution to your actual problem. Even though it probably will be slower than using the built-in point-in-triangle functions, I'll write this out just because I'm embarrassed about misunderstanding the nature of your problem.

Let's say p0 is one of the points of the quadrilateral.
And p1, p2 are two other points at the end of the sides coming off of p0.
And that p3 is the point you want to check.
If (a,b) is p1-p0, and (c,d) is p2-p0. and (x0,y0) is p3-p0.
Then you can can check if the point is in that quadrilateral like this:

var _id = 1 /(a*d-b*c);
var x1 = ( x0*d - y0*c) * _id;
var y1 = (-x0*b + y0*a) * _id;
var in_quad = (x1 > 0) and (y1 > 0) and (x1 < 1) and (y1 < 1);

7. ### marasovecMember

Joined:
Sep 15, 2016
Posts:
324
Don't worry. I misunderstood a lot of problems here and felt like an idiot many times
I'll check your solution out too

Last edited: Oct 14, 2019 at 3:47 PM