Sorting wallpapers by ratio with Euclid’s algorithm and PHP
Posted in Software Development on March 21st, 2011 by boy – 1 CommentI have a confession to make… I am a sucker for cool desktop wallpapers.
Right now on my MacBook Pro is a brilliant Fight Club background (made from the art of Adam from 52 Bad Dudes) and for my second monitor the funny Office Space / XP crossover wallpaper, popular on reddit right now.
I’m very much enjoying these wallpapers for now, but chances are that within the month I’ll get bored with them and find another to take their place.
I’ve had this addiction for several years now and as a good geek, instead of ever actually cleaning up, I’ve just migrated crap from hard disk to bigger hard disk. So in the process I’ve gathered quite a few wallpapers.
This used to work beautifully when I only had desktop machines, but when I switched to using laptops for work and (accidentally) ordered a widescreen monitor for home, my pretty 4:3 wallpapers didn’t look so hot anymore when they were scaled out to 16:9.
So I started collecting 16:9 wallpapers… and dropping them in the same folder as my old 4:3 wallpapers.
And now I have a mess of wallpapers that I have to sift through to find one that matches the ratio I want whenever I want to dig up an old wallpaper (like this cool “Why are you wearing that stupid man suit?” wallpaper from Donny Darko).
Now if I was a normal person I could:
- Live with it
- Find some small utility to sort it for me
- Sort everything by hand
But being a PHP programmer I had to write a simple script.
Problem
Given a single folder of images, sort them according to ratio where any ratio with less than X, a predetermined significant amount of, images get lumped together in a single ‘other’ category.
Solution
It’s pretty easy to get a list of images in a directory and with GD it’s pretty easy to get the image dimensions, however what I did not know was how to get the ratio. I tried to think how I would do this back in school with fractions, determining that 6/8th is the same as 3/4th but basically I’d just been thought to work on trial and error… something that I didn’t really feel like programming. There has to be an algorithm for this!
So after a little googling I’d determined I needed the ‘greatest common divisor’ and as usual there were snippets out there that did this for me, hell I could even use WolframAlpha to do it for me (although that didn’t seem to give me a usable answer… I was probably asking it wrong?).
Unfortunately the first PHP snippet I came across was so obfuscated (really people, a function name ghd? I won’t even grace it with the minute amount of PageRank I have) that I figured it would be more fun to write this myself, fortunately WikiHow has an awesome article on this algorithm called ‘Euclid’s algorithm‘ (and as usual Wikipedia has a boatload of information on it).
End result
<?php
define("MINIMUM_NUMBER_OF_IMAGES_FOR_VALID_RATIO", 10);
define("WEIRD_RATIO_FOLDERNAME", 'other');
/**
* @var array All files in the current directory
*/
$files = glob('*.*');
$imagesByRatio = array();
foreach ($files as $image) {
$imageData = getimagesize($image);
if ($imageData === false) {
echo "GD thinks $image is not a valid image." . PHP_EOL;
continue;
}
$imageWidth = $imageData[0];
$imageHeight = $imageData[1];
$divisor = getGreatestCommonDivisor($imageWidth, $imageHeight);
$ratioWidth = $imageWidth / $divisor;
$ratioHeight = $imageHeight / $divisor;
$ratioDescription = "$ratioWidth:$ratioHeight";
$imagesByRatio[$ratioDescription][] = $image;
echo "'$image' is a $ratioDescription image" . PHP_EOL;
}
foreach ($imagesByRatio as $ratio=>$images) {
// If there are enough images for this ratio, then it gets it's own folder
if (count($images) >= MINIMUM_NUMBER_OF_IMAGES_FOR_VALID_RATIO) {
// Replace colon by x for better compatibility with FAT filesystems
$dirName = str_replace(':','x', $ratio);
}
else {
// Else it gets to be in the 'weird-ratios folder'
$dirName = WEIRD_RATIO_FOLDERNAME;
}
// Create the directory if it doesn't exist already
if (!file_exists($dirName)) {
echo "Creating $dirName" . PHP_EOL;
mkdir($dirName);
}
// Copy over all the images with this ratio
foreach ($images as $image) {
echo "Copying '$image' to '$dirName/$image'" . PHP_EOL;
copy($image, "$dirName/$image");
}
}
/**
* Get the Greatest Common Divisor for 2 numbers
*
* @example getGreatestCommonDivisor(6,8) -> 2
* @link http://www.wikihow.com/Find-the-Greatest-Common-Divisor-of-Two-Integers
*
* @throws Exception
* @param int $a First number
* @param int $b Second number
* @return int Greatest common divisor
*/
function getGreatestCommonDivisor($a, $b)
{
assert('is_int($a) && is_int($b)');
$a = (int)abs($a);
$b = (int)abs($b);
if ($a === 0 OR $b === 0) {
throw new Exception("Cannot find greatest common divisor of 0");
}
if ($a > $b) {
$dividend = $a;
$divisor = $b;
}
else {
$dividend = $a;
$divisor = $b;
}
//$quotient = (int)($dividend / $divisor);
$remainder = $dividend % $divisor;
if ($remainder > 0) {
return getGreatestCommonDivisor($divisor, $remainder);
}
else {
return $divisor;
}
}
Conclusion
Math is fun!
Also, I have a lot of 5:4 and 8:5 wallpapers… weird ratio :-S.
.
