With a help from Jery now we have a precise tile picking algo and a nice debug visualization of it, showing the bounding boxes underneath:
We split terrain into quadtree of bounding boxes. When we need to pick a tile below the cursor, we first check bounding boxes and discard those that don’t intersect with the picking ray (cast from cursor position). That way we effectively discard 95% of tiles and hittest only remaining few inside the hit bounding boxes. On the screenshot that is the smallest purple box around the cyan picked tile.