mouse position to isometric tile including height

Question

Struggeling translating the position of the mouse to the location of the tiles in my grid. When it's all flat, the math looks like this:

this.position.x = Math.floor(((pos.y - 240) / 24) + ((pos.x - 320) / 48));
this.position.y = Math.floor(((pos.y - 240) / 24) - ((pos.x - 320) / 48));

where pos.x and pos.y are the position of the mouse, 240 and 320 are the offset, 24 and 48 the size of the tile. Position then contains the grid coordinate of the tile I'm hovering over. This works reasonably well on a flat surface.

Now I'm adding height, which the math does not take into account.

This grid is a 2D grid containing noise, that's being translated to height and tile type. Height is really just an adjustment to the 'Y' position of the tile, so it's possible for two tiles to be drawn in the same spot.

I don't know how to determine which tile I'm hovering over.

edit:

Made some headway... Before, I was depending on the mouseover event to calculate grid position. I just changed this to do the calculation in the draw loop itself, and check if the coordinates are within the limits of the tile currently being drawn. creates some overhead tho, not sure if I'm super happy with it but I'll confirm if it works.

edit 2018:

I have no answer, but since this ha[sd] an open bounty, help yourself to some code and a demo

The grid itself is, simplified;

let grid = [[10,15],[12,23]];

which leads to a drawing like:

for (var i = 0; i < grid.length; i++) {
    for (var j = 0; j < grid[0].length; j++) {
        let x = (j - i) * resourceWidth;
        let y = ((i + j) * resourceHeight) + (grid[i][j] * -resourceHeight); 
        // the "+" bit is the adjustment for height according to perlin noise values
    }
}

edit post-bounty:

See GIF. The accepted answer works. The delay is my fault, the screen doesn't update on mousemove (yet) and the frame rate is low-ish. It's clearly bringing back the right tile.

Source

Answer 1

Computer graphics is fun, right?

This is a special case of the more standard computational geometry "point location problem". You could also express it as a nearest neighbour search.

To make this look like a point location problem you just need to express your tiles as non-overlapping polygons in a 2D plane. If you want to keep your shapes in a 3D space (e.g. with a z buffer) this becomes the related "ray casting problem".

One source of good geometry algorithms is W. Randolf Franklin's website and turf.js contains an implementation of his PNPOLY algorithm.

For this special case we can be even faster than the general algorithms by treating our prior knowledge about the shape of the tiles as a coarse R-tree (a type of spatial index).