You can also treat it as just normal squares, and use an additional mask image. First, find the tile as normal, then use the mask image to determine if you need to offset you position.
This technique will also work with other tile shapes.
See this for more detail (described near the bottom).
This is pretty much what I ended up going with. It works beatifically, the code is understandable, and it takes just as long to run the code if I have 10x10 or 10,000x10,000 tiles.