Calculating the cells contained inside a rectangle on an Isometric Grid

Consider that we are given an isometric grid (consider something like Diablo) of tiles. We have some measures for the grid, like grid height, grid width and tile height/width. Consider this image:

The center cell of the grid is 0,0 extending iso-north (+y), iso-south(-y), iso-east(+x), iso-west(-x).

Let's say we to draw a rectangle at an arbitrary location on the grid开发者_如何转开发. We do NOT have the isometric positions for the rectangle, but rather have the normal draw coordinates for the grid where the top left hand corner is 0,0 and south is y+, right is x+.

If we had the top, left, height, width of the rectangle in question - how could we calculate an array of iso-cells that crossed by the bottom edge of the rectangle.

Any language you choose to demonstrate this will suffice.

In some papers and books about isometric programming (Isometric programming with Direct X7, yes its old but gives an overview about the problems and techniques) they use mousemaps.

Also there is the technique to render the area of the map covered by the rectangle into an image, each tile gets a unique color (and it is just the color rendered). Afterwards they check which colors are in the image and so extract the list of tiles.

Since you are using a classic isometric tile width half height there could be a mathematical solution too. Unfortunatly an suggested algorithm would depend heavily on your map layout.

The code for a Java based TileSystem can be found here