I don't know if there's a general algorithm, but your saying that Excel should also do the same resampling, made me think "So GD::Graph should as well". Only, it's far easier to see how GD::Graph does things. So, maybe you'd like to take a look at the sub "val_to_pixel", in the source of GD::Graph::XYlines...
HTH..