In a triangulated isometric grid, what triangle is a given point in?

Question

I have a triangulated isometric grid, like this:

In my code, triangles are grouped by columns.

As I hover the mouse, I want to calculate what triangle the mouse coordinates are in. Is there a simple algorithm to do that?

Answer 1

What you want to do is turn this into a grid as much as possible because grids are far easier to work with.

The first thing you do is work out what column it's in. You say you store that so it should be easier by doing a simple integer division on the x coordinate by the column width offset by the box start. Easy.

After that you want to work out what triangle it's in (obviously). How you partially turn this into a grid is you pretend that you have a stack of right angle triangles instead of a stack of isometric triangles.

The triangles have a length along the y axis (the side of the column). Divide that number in two and work out how many steps down you are. Based on the number of steps down and if the column is even or odd will tell you if you're looking at:

+--------+
|-_      |
|  -_    |
|    -_  |
|      -_|
+--------+

or the reverse. At this point you only need to determine which side of the line it's on to determine which right triangle it's in, which also tells you which isometric triangle it's in.

You have a couple of options for this.

1. You could use something like Bresenham's line algorithm to rasterize the hypotenuse and when you hit the column you're in work out if you're above or below that line;
2. Because you only have two possible grids here (one being the reverse of the other so it's really only one). You could store a array of row values, saying that for column 3, the hypotenuse is at offset 2, whereas for 6 it's at 4 and so on.

You could even use (1) to generate (2) as a fast lookup.

The only other thing to consider is what happens if the mouse cursor is on an edge?

Answer 2

This is similar to what cletus said, but a different way to look at it I suppose.

I am assuming the triangle side is 1.

Suppose you have the grid as below:

       y'
      /
     /__/__/__/__/__/__/
    /__/__/__/__/__/__/
   /__/__/__/__/__/__/____ x'
(0,0)

If you consider the grid in a co-ordinate system in which the x & y axes are at an angle of 60 degrees, a point whose co-ordinate in the angled system (x',y') will correspond to the coordinate in the orthogonal system (with same origin an general direction of axes) to (x,y).

In your problem, you are given (x,y), we need to find (x',y') and then figure out the triangle.

If i is the unit vector along x and j the orthogonal along y, then we have that

x'* i + y'( i/2 + sqrt(3) * j /2) = xi + yj.

(Basically the unit vector along the 'angled' y axis is i/2 + sqrt(3)/2 * j. The unit vector along the x axis is the same as the normal x-axis, i.e. i).

Thus

x' + y'/2 = x
y' * sqrt(3)/2 = y

Solving gives:

y' = 2*y/sqrt(3)
x' = x - y/sqrt(3)

Assume for now that x' and y' are positive.

Now if c = [x'], the integer part of x'

and r = [y'], the integer part of y'

then in the (angular) grid, the point lies in the cth column and the rth row. (Counting right and up and start counting at 0).

Thus we have narrowed down your point to a parallelogram

       ____
      /\ * /   
     /___\/
   (c,r)

Now in order to find out which triangle it is in you can consider the fractional parts of x' and y'.

{x} = x' - [x'] = x' - c.
{y} = y' - [y'] = y' - r.

Now,

if {x} + {y} > 1, then the point lies in the triangle marked with *. if {x} + {y} < 1, then the point lies in the other triangle. if {x} + {y} = 1, then the point lies on the line common to the two triangles.

Hope that helps too.