I suddenly had a brilliant idea: given a 16:9 screen/window aspect ratio, could I make the map 4:3, and then fill the two sides with UI elements?
I had to do this for aesthetic reasons, but it reduced the pressure on actual performance optimization and also took into account the black borders on the left and right sides of the widescreen display.