Finding closest larger resolution with nearest asp

Question

I have an array:

$resolutions = array(
    '480x640',
    '480x800',
    '640x480',
    '640x960',
    '800x1280',
    '2048x1536'
);

I want to retrieve closest larger value with the nearest aspect ratio (same orientation).

So, in case of $needle = '768x1280' - 800x1280.
And, in case of $needle = '320x240' - 640x480. While the closest here is 480x640 it shouldn't be matched, because its aspect ratio differs too much. So on, and so forth.

Purpose:

I have a set of images with resolutions as specified in $resolutions. Those images are going to be used for smartphone wallpapers.

With JavaScript, I am sending over a request with screen.width and screen.height to determine $needle.

On the server side, I am going to fetch the closest larger value of the given resolution, scale it down to fit the whole screen while preserving aspect ratio, and if something overlaps the dimensions, crop it to perfectly fit the screen.

Problem:

While everything is pretty simple with scaling and cropping, I cannot think of a way to find out the closest larger value, to load the reference image.

Hints:

In case it helps, $resolutions and $needle can be in a different format, ie.: array('width' => x, 'height' => y).

Tries:

I tried to experiment with levenshtein distance: http://codepad.viper-7.com/e8JGOw
Apparently, it worked only for 768x1280 and resulted 800x1280. For 320x240 it resulted in 480x640 but that does not fit this time.

Answer 1

Would it be easier if you had a single number to compare against?

It's a ratio, so just do, for example: 640 / 480 = 1.33*

Then you at least have something nice and simple to compare against the dimensions you are sending and presumably come up with a tolerance?

A simple example, which assume that the ratio array is ordered from lowest to highest. If this was a problem then we would create a search that ordered by the area (x by y).

function getNearestRatio($myx, $myy)
{

    $ratios = array(
        array('x'=>480, 'y'=>640),
        array('x'=>480, 'y'=>800),
        array('x'=>640, 'y'=>480),
        array('x'=>640, 'y'=>960),
        array('x'=>800, 'y'=>1280),
        array('x'=>2048, 'y'=>1536)
    );
    $tolerance = 0.1;
    foreach ($ratios as $ratio) {
         $aspect = $ratio['x'] / $ratio['y'];
        $myaspect = $myx / $myy;

        if ( ! ($aspect - $tolerance < $myaspect && $myaspect < $aspect + $tolerance )) {
            continue;
        }

        if ($ratio['x'] < $myx || $ratio['y'] < $myy) {
            continue;
        }
        break;
    }

    return $ratio;
}

I've built in a tolerance, so that it will match 'nearby' aspect ratios, as you allude to in your question.

This function should pass both test cases you have given.

Answer 2

Well, this turned out larger than I anticipated, but I think this meets the criteria. It works by breaking the available resolutions down to their ratio. Then sorting by the delta between the target ratio and the available ratios ascending, then by size (pixels) descending. Returning the top match - which should be the closest, smallest match.

class ResolutionMatcher
{
    private $resolutions;

    public function __construct(array $resolutions)
    {
        foreach ($resolutions as $resolution) {
            $this->resolutions[$resolution] = $this->examineResolution($resolution);
        }
    }

    public function findClosest($target)
    {
        $targetDetails = $this->examineResolution($target);
        $deltas = array();
        foreach ($this->resolutions as $resolution => $details) {
            if ($details['long'] < $targetDetails['long'] || $details['short'] < $targetDetails['short']) continue;
            $deltas[$resolution] = array(
                'resolution' => $resolution,
                'delta' => abs($details['ratio'] - $targetDetails['ratio']),
            );
        }
        $resolutions = $this->resolutions;
        uasort($deltas, function ($a, $b) use ($resolutions) {
            $deltaA = $a['delta'];
            $deltaB = $b['delta'];
            if ($deltaA === $deltaB) {
                $pixelsA = $resolutions[$a['resolution']]['pixels'];
                $pixelsB = $resolutions[$b['resolution']]['pixels'];
                if ($pixelsA === $pixelsB) {
                    return 0;
                }
                return $pixelsA > $pixelsB ? 1 : -1;
            }
            return $deltaA > $deltaB ? 1 : -1;
        });
        $resolutions = array_keys($deltas);
        return array_pop($resolutions);
    }

    private function examineResolution($resolution)
    {
        list($width, $height) = explode('x', $resolution);
        $long = ($width > $height) ? $width : $height;
        $short = ($width < $height) ? $width : $height;
        $ratio = $long / $short;
        $pixels = $long * $short;
        return array(
            'resolutions' => $resolution,
            'pixels' => $pixels,
            'long' => $long,
            'short' => $short,
            'ratio' => $ratio,
        );
    }
}

Usage:

$resolutions = array(
    '480x640',
    '480x800',
    '640x480',
    '640x960',
    '800x1280',
    '2048x1536'
);

$target = $_GET['target'];

$matcher = new ResolutionMatcher($resolutions);
$closest = $matcher->findClosest($target);

Answer 3

First of all, I would store the haystack using width first, height second:

$resolutions = array(
    array('w' => 640, 'h' => 480),
    array('w' => 800, 'h' => 480),
    array('w' => 960, 'h' => 640),
    array('w' => 1280, 'h' => 800),
    array('w' => 2048, 'h' => 1536),
);

Then, calculate dimension differences between needle and each item, followed by the area size:

array_walk($resolutions, function(&$item) use ($needle) {
    $item['aspect'] = abs($item['w'] - $needle['w']) / abs($item['h'] - $needle['h']);
    $item['area'] = $item['w'] * item['h'];
});

usort($resolutions, function($a, $b) {
  if ($a['aspect'] != $b['aspect']) {
    return ($a['aspect'] < $b['aspect']) ? -1 : 1;
  }
 return 0;
});

Then you filter the list based on which resolutions are bigger; the first match is the one closest to the needle aspect ratio:

$needle_area = $needle['w'] * $needle['h'];
foreach ($resolutions as $item) {
    if ($needle_area < $item['area']) {
        return $item;
    }
}
return null;

Answer 4

Try this

echo getClosestRes('500x960');
echo '<br /> try too large to match: '.getClosestRes('50000x960');

function getClosestRes($res){
    $screens = array(
        'landscape'=>array(
            '640x480',
            '1200x800'
        ),
        'portrait'=>array(
            '480x640',
            '480x800',
            '640x960',
            '800x1280',
            '1536x2048'
        )
    );

    list($x,$y)=explode('x',$res);
    $use=($x>$y?'landscape':'portrait');

    // if exact match exists return original
    if (array_search($res, $screens[$use])) return $res; 

    foreach ($screens[$use] as $screen){
        $s=explode('x',$screen);
        if ($s[0]>=$x && $s[1]>=$y) return $screen;
    }
    // just return largest if it gets this far.
    return $screen; // last one set to $screen is largest
}

Answer 5

You can first extract the arrays like:

$resolutions = array(
    '480x640',
    '480x800',
    '640x480',
    '640x960',
    '800x1280',
    '2048x1536'
);

foreach ($resolutions as $resolution):
    $width[]=(int)$resolution;
    $height[]=(int)substr(strrchr($resolution, 'x'), 1);
    echo $width,' x ',$height,'<br>';
endforeach;

Then you can match the given needle with the array with in_array and array_search like:

$key = array_search('480', $items);
echo $key;  

When you have the key just increment it for the closest greater value. I'll let you do that by yourself.

Answer 6

Made a quick class. Should competently find the minimum resolution for any two numbers that you specify. I have preloaded it with the resolutions you specified but the $_resolutions array could be set to whichever standards you like, and can also be changed on-the-fly.

class Resolution {

    /**
     * Standard resolutions
     *
     * Ordered by smallest to largest width, followed by height.
     *
     * @var array
     */
    private $_resolutions = array(
        array('480', '640'),
        array('480', '800'),
        array('640', '480'),
        array('640', '960'),
        array('800', '1280'),
        array('2048', '1536')
    );

    /**
     * Width
     *
     * @var int
     */
    private $_width;

    /**
     * Height
     *
     * @var int
     */
    private $_height;

    /**
     * Constructor
     *
     * @param  int $width
     * @param  int $height
     * @return void
     */
    public function __construct($width, $height) {
        $this->setSize($width, $height);
    }

    /**
     * Find the minimum matched standard resolution
     *
     * @param  bool $revertToLargest (OPTIONAL) If no large enough resolution is found, use the largest available.
     * @param  bool $matchAspectRatio (OPTIONAL) Attempt to get the closest resolution with the same aspect ratio. If no resolutions have the same aspect ratio, it will simply use the minimum available size.
     * @return array The matched resolution width/height as an array.  If no large enough resolution is found, FALSE is returned, unless $revertToLargest is set.
     */
    public function getMinimumMatch($revertToLargest = false, $matchAspectRatio = true) {
        if ($matchAspectRatio) {
            $aspect = $this->_width/$this->_height;
            foreach ($this->_resolutions as $res) {
                if ($res[0]/$res[1] == $aspect) {
                    if ($this->_width > $res[0] || $this->_height >     $res[1]) {
                        return ($revertToLargest ? $res : false);
                    }
                    return $res;
                }
            }
        }
        foreach ($this->_resolutions as $i => $res) {
            if ($this->_width <= $res[0]) {
                $total = count($this->_resolutions);
                for ($j = $i; $j < $total; $j++) {
                    if ($this->_height <= $this->_resolutions[$j][1]) {
                        return $this->_resolutions[$j];
                    }
                }
            }
        }
        return ($revertToLargest ? end($this->_resolutions) : false);
    }

    /**
     * Get the resolution
     *
     * @return array The resolution width/height as an array
     */
    public function getSize() {
        return array($this->_width, $this->_height);
    }

    /**
     * Set the resolution
     *
     * @param  int $width
     * @param  int $height
     * @return array The new resolution width/height as an array
     */
    public function setSize($width, $height) {
        $this->_width = abs(intval($width));
        $this->_height = abs(intval($height));
        return $this->getSize();
    }

    /**
     * Get the standard resolutions
     *
     * @return array
     */
    public function getStandardResolutions() {
        return $this->_resolutions;
    }

    /**
     * Set the standard resolution values
     *
     * @param  array An array of resolution width/heights as sub-arrays
     * @return array
     */
    public function setStandardResolutions(array $resolutions) {
        $this->_resolutions = $resolutions;
        return $this->_resolutions;
    }

}

Example Usage

$screen = new Resolution(320, 240);
$screen->getMinimumMatch();
// Returns 640 x 480 (aspect ratio matched)

$screen = new Resolution(1280, 960);
$screen->getMinimumMatch();
// Returns 640 x 480 (aspect ratio matched)

$screen = new Resolution(400, 960);
$screen->getMinimumMatch();
// Returns 640 x 960 (aspect ratio not matched, so uses closest fit)

$screen = new Resolution(5000, 5000);
$screen->getMinimumMatch();
// Returns FALSE (aspect ratio not matched and resolution too large)

$screen = new Resolution(5000, 5000);
$screen->getMinimumMatch(true);
// Returns 2048 x 1536 (aspect ratio not matched and resolution too large, so uses largest available)