I have a map that looks roughly like the following picture. The map is discretized into pixels and has size nxn where n is in [1000, 2000]. I want an efficient method, preferably O(1), to test whether two given points intersect with the map at any point. For example, the blue and red points will form a line segment that intersects with the map, while the blue and green points do not intersect. What would be a good algorithm to solve this problem?
If you're working on a pixel grid, and the points are exact pixel centers, then precomputing all answers for all possible input pairs and hashing the results lets you simply query the hashtable, which gives you an expected $O(1)$ runtime. Of course, the precomputation is a bit expensive. :(
The real point of this answer is not to suggest that as a serious approach, but rather to suggest that you might want to formulate the problem a little more precisely. I personally suspect that $O(1)$, without precomputation, is unlikely.
This is, by the way, the 2D visibility problem, much discussed by those who develop computer games, who want to know if the person at the red dot can shoot and kill the person at the blue dot, etc. If you did a web search on '2D visibility' and perhaps 'portal', you might find it instructive.