GM:S 1.4 [SOLVED] Point in quadrilateral?

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

  1. marasovec

    marasovec Member

    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
    [​IMG]
     
  2. flyingsaucerinvasion

    flyingsaucerinvasion Member

    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 Studios

    SnotWaffle Studios Member

    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. ParodyKnaveBob

    ParodyKnaveBob The 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. marasovec

    marasovec Member

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

    flyingsaucerinvasion Member

    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.
    upload_2019-10-13_10-12-58.png
    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. marasovec

    marasovec Member

    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

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice