Best way to find triangle that a given point occupies.

Question

Hey all, need some help with finding the best way to find the triangle that a given point occupies. The reason for this is that my terrain is made up of groups of four triangles that when combined form a square (this is necessary to achieve the visual style I want for the terrain). Here's a picture example of a single square:

alt text

Each of these four triangles can have their own values, so for example the left and top triangles can be water while the right and bottom triangles are land. Because of this I need to be able to tell what triangle a point is within. Once I know whether it's the left, top, right, or bottom triangle I can then pull that data.

My first thought was to find the distance between the point and the centers of all four triangles, and then compare them to find the triangle with the shortest distance. There's some preliminary code below if it helps at all. Note: I will be "manually" calculating the distance instead of using Vector2.Distance if I decide to go this route.

If anyone has other ideas please let me know!

         LeftTriPositionOffset = new Vector2 (0.25f, 0.5f);
         TopTriPositionOffset = new Vector2 (0.5f, 0.75f);
         RightTriPositionOffset = new Vector2 (0.75f, 0.5f);
         BottomTriPositionOffset = new Vector2 (0.5f, 0.25f);

         arrayPositionX = (int)(worldPosition.x / HSpacing);
         arrayPositionY = (int)(worldPosition.y / HSpacing);
 
         leftTriDistance = Vector2.Distance (worldPosition + LeftTriPositionOffset, worldPosition);
         topTriDistance = Vector2.Distance (worldPosition + TopTriPositionOffset, worldPosition);
         rightTriDistance = Vector2.Distance (worldPosition + RightTriPositionOffset, worldPosition);
         bottomTriDistance = Vector2.Distance (worldPosition + BottomTriPositionOffset, worldPosition);
 
 
         if (leftTriDistance <= topTriDistance && leftTriDistance <= rightTriDistance && leftTriDistance <= bottomTriDistance) {
             arrayPositionX += (int)(LeftTriArrayOffset.x);
             arrayPositionY += (int)(LeftTriArrayOffset.y);
         }
 
         else if (topTriDistance <= leftTriDistance && topTriDistance <= rightTriDistance && topTriDistance <= bottomTriDistance) {
             arrayPositionX += (int)(TopTriArrayOffset.x);
             arrayPositionY += (int)(TopTriArrayOffset.y);
         }
         
         else if (rightTriDistance <= leftTriDistance && rightTriDistance <= topTriDistance && rightTriDistance <= bottomTriDistance) {
             arrayPositionX += (int)(RightTriArrayOffset.x);
             arrayPositionY += (int)(RightTriArrayOffset.y);
         }
         
         else if (bottomTriDistance <= leftTriDistance && bottomTriDistance <= topTriDistance && bottomTriDistance <= rightTriDistance) {
             arrayPositionX += (int)(BottomTriArrayOffset.x);
             arrayPositionY += (int)(BottomTriArrayOffset.y);
         }
 
         else {
             Debug.LogError ("Cannot locate a Tri that is closest to position " + worldPosition + ".");
         }
 
 
         terrainTriArrayPosition = arrayPositionX * TerrainTriYSize + arrayPositionY;

Answer 1

There's two options for this that I can think of off the top of my head.

1 - A bunch of tests: Calculate the position in question relative to the center of the square. Then you do two sets of checks first check the X and Y to see if each is less than or greater than 0, telling you which of the four corners you would be in. But since you're dealing with triangles, you will then want to compare the magnitude of the x and y components, depending on which one is greater will tell you which triangle you are in (or if they are the same, you're on the edge and can make the call as to which one gets priority). (EG: if both x and Y relative to the center are positive, then you are in the bottom right, then if Abs(X) is greater than Abs(Y) then you are in the right, otherwise you're in the bottom.

2 - Use a dot product: Calculate the vector from the center of the square to the point in question, then normalize it. then you can use dot products to compare it to other vectors (using other unit vectors keeps this simpler) comparing the dot products against unit vectors for up down left and right (relative to the square) will then let you work out which segment the point is in. EG if you compare your vector with the unit vector for Left, a value greater than 0.5 means you're in the left triangle. between 0 and 0.5 could put you in the top or bottom and <0 could be in any other triangle. So do it against all 4 directions to work out which one is > 0.5 (Note if you get the result of exactly 0.5 for two of them then your point is on the boundary of those two triangles);

Hope this helps let me know if its still a bit confusing and I'll try to explain it a bit more.

Best way to find triangle that a given point occupies.

1 Reply

Your answer

Follow this Question

Related Questions