PS if you couldnt do this querry easily then how on earth do you suppose maya can draw textures on objects?
When maya renders, it's operating in a forward direction. It already knows what polygon it's drawing etc. This question is trying to solve in the opposite direction.
It's not really fair to compare the two, although the solution as I described it is (IMO) still fairly simple.
Also, as a side note I was thinking about this...
And I was thinking about ways to speed it up if (for example) you wanted to code a plugin to do it in real time.
I came up with two ideas; both are designed to work in a condition of no overlap allowed, and both work by trying to find the 'right' polygon fast to short-circuit the search. Both ideas involve doing some prep work up front, but should speed up the process afterwards.
First idea is: pre-sort your polygon list based on UV map area. Largest polygons to the front of the queue, smaller to the back. This ensures that when you go to solve for any given UV, the polygons most statistically likely to contain it will get checked first.
Second idea is to set up a 2d array of polygon indices to represent the UV domain. Solve for each 'pixel' in the array ahead of time and store the counterpart polygon index in the array.
The array approach wouldn't be an end-all solution; it could still fail, but it could be coded to fail gracefully, and would still save a huge amount of calculation the vast majority of the time.
Say for example you need to look up (.101,.101). Now say the nearest array element is for (.1,.1). (.1,.1) and is right near the edge of polygon A, while (.101,.101) is unfortunately just over the edge and on polygon B. This would happen only a tiny fraction of the time, but it would need to be accounted for.
So you check the array, get poly A, check it and find that it doesn't contain your point. Not that big of a deal. You check the adjacent elements in the array and check their polys. 99% of the time that should produce a poly that contains your point.
If that still doesn't give you your poly, then it means your point is either not mapped or contained by a polygon so small that it slipped between array pixels. So at that stage you just have to do the full search as usual. No big deal.
The remaining 99.99% of the time, the array method would cut the search down to a single iteration; so overall it would be a very effective plan to implement if you needed to solve constantly in real time.
There are only really two downsides; one is the space required to hold the array, which could vary depending on how much accuracy you want. A high res array would produce solutions more often, while lower res would fail more often and require a full search.
The other is that the array is not dynamic, and wouldn't offer any help if your UV map was dynamically animating or if your topology changed over time. But this situation is pretty rare and probably not really a factor.