How do I determine if a given grid coordinate is fully within a triangle?

Question

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:

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.

Answer 1

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.