Comment by ianjsikes

Better yet, scale the image proportionally down to the largest of the two target sides, then run the algorithm once in the direction that needs to shrink.