Алгоритм золотой середины?

#математика #алгоритм

Реализация программы для кропа изображений привела меня в тупик. Не могу выявить
закономерность при создании такого алгоритма: 
Даны  х,у . Найти такие минимальные dx и dy, чтобы (x - dx)/(y - dy) = 3/2
Т.е. в результате два новых числа будут относиться как 3:2.(Впрочем соотношение может
быть любым).
Пример:

1500 и 1100  - на выходе 1500 и 1000 (dx=0, dy=100)
1500 и 1300 - на выходе 1200 и 800 (dx=300,dy=500)

Интутитивно я какбы догадываюсь, но описать алгоритмом не могу. Кто знает, подскажите
хотя бы ход мыслей!    

Ответы

Ответ 1

самый простой вариант:
public class TestCrop
{
    private static final double DIMENSION_REL = 1.5;

    public int x;
    public int y;

    public TestCrop ( int x, int y )
    {
        setX ( x );
        setY ( y );
    }

    public static void main ( String [] args )
    {
        test ( new TestCrop ( 1500, 1100 ) );
        test ( new TestCrop ( 1500, 1300 ) );
        test ( new TestCrop ( 1600, 1100 ) );
        test ( new TestCrop ( 1600, 1300 ) );
        test ( new TestCrop ( 1700, 1100 ) );
        test ( new TestCrop ( 1700, 1300 ) );
    }

    private static void test ( TestCrop point )
    {
        System.out.println ( "in   = " + point );
        TestCrop result = calc ( point );
        System.out.println ( "out  = " + result );
        System.out.println ();
    }

    private static TestCrop calc ( TestCrop p )
    {
        double rel = (double) p.getX () / p.getY ();
        if ( rel > DIMENSION_REL ) {
            return new TestCrop ( (int) ( p.getY () * DIMENSION_REL ), p.getY () );
        }

        return new TestCrop ( p.getX (), (int) ( p.getX () / DIMENSION_REL ) );
    }

    // методы get/set

    @Override
    public String toString ()
    {
        return String.format ( "{%d, %d}", getX (), getY () );
    }
}

на выходе:
in   = {1500, 1100}
out  = {1500, 1000}

in   = {1500, 1300}
out  = {1500, 1000}

in   = {1600, 1100}
out  = {1600, 1066}

in   = {1600, 1300}
out  = {1600, 1066}

in   = {1700, 1100}
out  = {1650, 1100}

in   = {1700, 1300}
out  = {1700, 1133}

более сложный:
Задача найди размеры изображения которые будут максимально близки к исходным, это
значит что у них должны быть минимальные {dx, dy}, что так же означает что dx*dy должно
стремится к x*y. Если обозначить результаты которые возвращает простая реализация как
{rx, ry}, то более точным решением будет рекурсия с подсчетом dx*dy где значения находятся
в диапазонах: [rx; x] для dx и [ry; y] для dy. Для каждой проверенной пары {dx, dy}
надо вызвать проверку для {dx-1, dy} и {dx, dy-1}
p.s. поиск будет идти по спаданию значений т.к. нас интересует макс. значения размеров
p.s.s не думаю, что в данной ситуации есть смысл настолько увиличивать сложность
алгоритма


Ответ 2

Возьмем вместо 3/2 дробь a/b. Уравнение, приведенное в вопросе, можно привести к
виду ady - bdx = ay - bx = const. Это известное диофантово уравнение.
Если найдено частное решение dx = u, dy = v, общее решение будет иметь вид dx = u
+ bn, dx = v - an для любого целого n.

Соответственно, есть решение, у которого dx - наименьшее положительное из всех. Также
есть решение с наименьшим положительным dy. 
Например, для x = 1600, y = 1200, a = 3, b = 2 получаем  3dx - 2dy = 700. Достаточно
взять dy четным числом, dx = 2k получим, что dy = 3k - 350. Наименьшее dx будет 0,
тогда dy = -350. Наименьшее положительное dy будет dy = 1 (при k = 117), тогда dx = 234. 
Если допустить и отрицательные dx, dy, можно найти и меньшие по модулю значения.
Например, при k = 70 имеем dx = 140, dy = -140.
В математике есть алгоритм решения такого рода уравнений, алгоритм Евклида. Но, думаю,
проще организовать прямой перебор, если числа не очень большие.