# which quarter of a triangle the point is in

I've got a world made out of squares. The square are devided in four triangles like this: The corners have their heights stored in a 2D array and the center height is the average of the corners. To calculate the players Y-coordinate I have to know in which triangle he is standing on. How can you calculate in which quarter the player is by the X and Y coordinates?

EDIT:

My algorithm:

bool h1 = false, h2 = false;

if(posZ < posX - posZ) //something weird going on here
{
h1 = true;
}
if(posX < posZ - posX) // and here
{
h2 = true;
}
if(h1 && h2)
{
triangle = 0;
}
if(h1 && !h2)
{
triangle = 1;
}
if(!h1 && !h2)
{
triangle = 2;
}
if(!h1 && h2)
{
triangle = 3;
}


This algorithm tries to find in which triangle you are. There is something wrong in that math.

• Don't you mean "To calculate the players Z-coordinate" because you have the Y already. – Simeon Pilgrim Jun 30 '14 at 11:15
• Yes kind of. I think Y is like height wich i'm trying to find here. But yes you can also call it Z – Hullu2000 Jun 30 '14 at 11:17
• Well use 'height' or 'z' but not Y twice for different things. – Simeon Pilgrim Jun 30 '14 at 11:19
• The ground coordinates are X and Z (North/South an East/West). Y is hight (Up/Down). – Hullu2000 Jun 30 '14 at 11:21
• If squares are defined in the square projection of X Y the you can do simple checks for greater than the middle in the X and Y to know which side of the square your on then you can compare the X to Y value to know which side of the corner to center line you are on. – Simeon Pilgrim Jun 30 '14 at 11:22

## 2 Answers

We can find out which corner the player is in by checking whether their position is above or below the two diagonals through the square.

Let's assume for a moment that the center of your square was at the coordinate position (0,0), and let's start with the diagonal that goes from the lower left to the upper right. When would a point be exactly on this line? Obviously when its x and y coordinates are the same.

Therefore, if x < y, the point is above the diagonal, and if y < x, it is below the diagonal.

(Important: these tests assume the x-axis to point right and the y-axis to point up, like in maths, not like in standard 2D graphics.)

With a similar reasoning we can check the other diagonal, the one from the upper left to the lower right. A point is on that line if -x == y.

Therefore if -x < y, the point is above the diagonal, and if y < -x, it is below the diagonal.

But what if the diagonal's center point is not at (0, 0)? Well, then we just translate the player's position so that we can fall back to the above case. In order to move the square so that its center ends up at (0, 0) we have to translate it by the reverse vector from that point to its center. And we will have to move the player's position by the same amount, of course.

Together, we get the following algorithm.

tx = px - cx              // translate the player's position
ty = py - cy              // by negative vector to square's center

if tx < ty then           // above diagonal #1
if -tx < ty then      // + above diagonal #2
// top corner
else                  // + below diagonal #2
// left corner
fi
else                      // below diagonal #1
if -tx < ty then      // + above diagonal #2
// right corner
else                  // + below diagonal #2
// bottom corner
fi
fi


Note, however, that you should make sure that the player's position is inside the square in the first place. That's something the above algorithm doesn't check.

As an exercise, what does the algorithm do when the player's position is exactly on one of the two diagonals? :-)

Do you know for sure that the player's position is actually inside the square? If so, the following might work for you.

If you translate the player position (p_x, p_y) so that the center of the square (c_x, c_y) would end up in your coordinate system's origin, and then rotate it by 45 degrees around the origin, you can simply check the four corner by less-than/greater-than zero tests:

  testX  |  testY  | Corner
============================
< 0   |   < 0   |   #1
< 0   |   > 0   |   #2
> 0   |   < 0   |   #3
> 0   |   > 0   |   #4


You have to handle the = case, too, of course, which ever way you like.

Here is how you get from the player's position p to the test coordinates which you can use in the above table:

• Way overkill. You don't need a length-preserving rotation, so using (a=x+y, b=x-y) transform works well enough. Matrix transforms are useful in the general case, but they're rarely efficient in specific cases. – MSalters Jun 30 '14 at 12:44
• @MSalters Thank you, very good observation! By the way, I didn't mean to suggest matrices as the way to implement this, it's just to demonstrate the steps. – Thomas Jun 30 '14 at 13:32