1
\$\begingroup\$

I'm using Unity's Grid system, and I'm drawing triangles on the grid. Each triangle is recorded as a Vector2Int origin point and a List of three Vector2Ints recording its relative vertices, for instance:

origin = new Vector2Int(0, 0);

relativeVertexPositions = new List<Vector2Int>() {
    new Vector2Int(-3, 0),
    new Vector2Int(3, 0),
    new Vector2Int(0, -3),
};

It's a bit weird that the origin is on the bottom of the triangle but it's for an in-game reason - a character is meant to stand there. I can redefine the origin point to elsewhere in the triangle if needs be.

The above code would generate a triangle as follows:

enter image description here

I'm completely stuck on how to find out whether a given Vector2Int (i.e. an integer x,y position - this is presumably an engine-agnostic problem) is fully inside the triangle. These four squares are marked in blue on my sketch.

Individual instances of triangles vary in the distance that their vertices are located away from the origin (1..n), but they all have this shape and the structure ((-m,0),(m,0),(0,-m)) where m is an integer. They can also be rotated in 90-degree increments around the origin point - I do this by translating the vertices around the origin, but the relative relationship of the vertices to the origin never changes.

\$\endgroup\$
6
  • \$\begingroup\$ Is the only purpose of creating this triangle to find the grid cells you're looking for? \$\endgroup\$
    – Romen
    Sep 13, 2022 at 19:06
  • \$\begingroup\$ How variable are your triangles, as your last sentence suggests only certain triangles (are they always isosceles with a flat base? Are they the same shape? Do they have a minimum size?) There is a general solution for completely arbitrary triangles that I can post later, but it might be overkill for your case. \$\endgroup\$
    – MadMan
    Sep 13, 2022 at 19:58
  • \$\begingroup\$ @Romen, no, the triangles are displayed onscreen and used in-game. \$\endgroup\$ Sep 13, 2022 at 20:16
  • 1
    \$\begingroup\$ @lowercasename so they are all ((-m,0),(m,0),(0,-m)) where m is an integer (or rotation thereof)? It may be worth editing your question to include that as you will be more likely to get a (much simpler) answer that fits your use case. \$\endgroup\$
    – MadMan
    Sep 13, 2022 at 20:24
  • 1
    \$\begingroup\$ You're completely right, and I've updated the answer - hopefully it's clearer now! \$\endgroup\$ Sep 13, 2022 at 20:54

1 Answer 1

2
\$\begingroup\$

You seem to be using the centre point of your square as the reference, so I will follow that convention (I'm not familiar with Unity's conventions about this).

You just need to check three inequalities, one for each of the sides of the triangle. Assuming i,j is the centre of your square (I'm using i and j because I want to leave x and y free to show my working):

  • For the base, you need to check that j+1/2<=0, simplifies to 2*j<=-1, or j<=-1 given that we are working with integers.

  • For the left side, look at the top left corner of the square, you are checking it against the line x+y=-m, so check (i-1/2)+(j-1/2)>=-m, simplifies to i+j>=-m+1

  • Similarly for the right side, look at the top right corner of the square, you are checking it against the line x-y=m, so check (i+1/2)-(j-1/2)<=m, simplifies to i-j<=m-1.

If it passes all three checks, it is fully inside, otherwise it is not fully inside.

For the rotated case, you can just rotate to this coordinate system and do the checks, or have 3 other cases similar to this one.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .