Оптимальный размер битмапы.

Привет.
Необходимо создать битмапу, известно число пиксель. Как посчитать оптимальный её размер, наиболее близкий к квадрату, но чтобы пустых пиксель было наименьшее число ?
Никак не могу посчитать.. Помню давно подобная задача решалась както дифференцированием..
Например для 17 пиксель можно сделать так:
+++++
+++++
+++++
++ooo 4x5
Можно так:
+++++++
+++++++
+++oooo 7x3
Оптимальный вариант такой:
++++++
++++++
+++++o 6x3
Для большик картинок это важно, так как используется лишнее пустое место.
Я считал квадратные корни, но это не оптимально. Если дампить массив данных в 32-х разрядную битмапу считал так:
Pixels = (DumpSize + 3) & Not(3)) / 4
Width = Int(Pixels ^ 0.5)
Heigth = Int(Pixels/Width)
Для ширины и высоты поправка на 1 если не целые. Для дампа ntdll http://img14.imageshack.us/my.php?image=00330000.png теряется полтора килобайта.

 

Методом перебора. За то время, пока ты будешь рожать оптимальный лохорифм, компьютер успеет решить задачу, выпить кофе и сходить поспать.

 

Должна быть формула.

 

Clerk

определитесь с приоритетом оптимизации, то ли к квадрату, то ли к наименьшему числу пикселей.
если к квадрату, то

 

t00x
Форма близкая к квадрату, точнее прямоугольник. При наименьшем числе пискель получается чтото близкое к линии.

Это если (Int(Pixels ^ .5)) ^ 2 != Pixels, иначе например для 100 пиксель получится 10 лишних.

 

Clerk

посчитать
Width = Int(Pixels ^ 0.5) и
Width1 = Int(Pixels ^ 0.5) + 1, потом
W2 = Width ^ 2 и
W2_1= Width1 ^ 2, сравнить с Pixels, какое подходит (равно или больше),
потом (если не точный квадрат) прибавлять по 1 к Width(1) и считать Height (все значения Width(1) и Height сохранять),
и выбрать наилучшие -- min (Pixels - Width(1)*Height) --> 0.

 

Это уже цикл.
Допустим 32 пикселя, если корень вычеслить то стороны одинаковы:
+ + + + + +
+ + + + + +
+ + + + + +
+ + + + + +
+ + + + + +
+ +
Оптимально так:
+ + + + + + + +
+ + + + + + + +
+ + + + + + + +
+ + + + + + + +
Ширина/Длина = 2, пойдёт.
Но как я это посчитал ??

 

x имеем. остаток r до ближайшего квадрата (s^2), r=|s^2 - x|, r < s распихиваем в столб/строку.
[arg] - целое число от arg.
s1=[x^0.5]
s2=[x^0.5+1]
s=s1 или s2 в зависимости от следующего:
r = min(|s1^2-x|,|s1^2-x|). выбираем тот что ближе. s - сторона опт квадрата. r - остаток, дописываем в стоку либо распихиваем по пикселу в столбец. Если s=s1 то r - значащий остаток, если s=s2, то r - незначащий остаток. т.е в 1м случае идёт прибавление к квадрату, во 2м дополнение до квадрата. Во 2м случае имеем квадрат. в 1 прямоугольник.
То же что и t00x сказал.

 

Clerk
Пусть число пикселей = N, максимальное соотношение сторон (W/H), которое можно себе позволить = R.
Ищем делитель числа N (если оно составное), наиболее близкий к его корню. Получим разложение N=A*B, где A<=sqrt(N).
Если B/A < R, то используем битмап размера AxB. Можно попробовать вычислить A и B также для N+1, N+2, ... и так далее до ближайшего квадрата, и выбрать A и B, при которых теряется меньше всего пикселей. Вот, вкратце, переборный алгоритм. А формулу придумать вряд-ли получится.

 

Кстати, если мы получили разложение N=A*B, то пиксели не теряются вообще. Если получили N+K=A*B, то теряются K пикселей. Так что перебор нужно останавливать, как только получили A и B, удовлетворяющие условию B/A < R.

 

Не то чтото. Помню когда учился была задача на нахожнение оптимального размера коробки, сейчас хотел посмотреть, залез в матчасть.. но не понятно как уравнение составить, которое далее дифференцируется(анализ на экстремумы вроде).

 

Clerk
Про коробку это другое.

 

Clerk
Вот до чего доводит преждевременный уход из вуза.

Ваша задача должна решаться в целых числах. А это сильно меняет дело. В данном случае это просто задача разложения на множители. К тому же, как правильно сказал t00x, необходимо выбрать приоритет условий. Т.е. постановка задачи неоднозначная. Скажем для 321 пикселя какое разложение лучше: 18x18 (3 лишних) или 107x3 (зато нацело)?

P.S. Гоню. Залез случайно в старые темы и чего-то взбрело в голову ответить. Извиняюсь за подъём.

 

l_inc
Лучше 18x18 (3 лишних).

 

Clerk
Не... это, конечно, очень хорошо, что Вы сумели выбрать, но для решения задачи неплохо бы сформулировать более-менее формальный критерий, по которому это можно определить для любых двух различных решений. Но в любом случае одной формулой задача, конечно, не решается.
P.S. Так тема ещё актуальна?

 

l_inc
Да, тема актуальна. К сожалению я не могу сформулировать чётко задачу, еслибы мог то и решил бы.

 

Clerk
Может попробовать искать минимальный периметр?

 

Clerk
Могу предложить способ, изложенный ниже. Он быстр, находит то, что требуется по задаче; в приоритете - приближенность к квадрату (ограничение: между значениями сторон оптимального прямоугольника должен быть квадрат целочисленного числа, иначе - см. примеры 4,5). То что написано выше (начиная со второго предложения) - ничем не обосновано, просто наблюдения. В силу малого количества экспериментов, выводы могут быть статистически незначимы

Код (Text):

1. sq1 = roundup(sqrt(x));
2. sq2 = roundown(sqrt(sq1^2-x)); // <-- исправлено
3. w = sq1+sq2, h = sq1-sq2;

примеры:

Код (Text):

1. 1) 100000:    339*295 = 100005  ( 5 пустых)
2. 2) 200000:    474*422 = 200028  (28 пустых)
3. 3) 225929:    501*451 = 225951  (22 пустых), оптимальный -   517*437 (0 пустых)
4. 4) 401280:    660*608 = 401280  ( 0 пустых), оптимальный -   640*627 (0 пустых)
5. 5) 422550:    686*616 = 422576  (26 пустых), оптимальный -   675*626 (0 пустых)
6. 6) 1489324: 1259*1183 = 1489397 (73 пустых), оптимальный - 1388*1073 (0 пустых)

Если нужно, могу дать пояснения, может кто их разовьет, и получится более стоящий вариант.

P.S.
Особенно с учетом

 

С чего это вдруг???
Строка выравнивается до четырех байт, а пикселей в ней - сколько угодно.