Настолько полезная, что вполне возможно, кто-то ее уже решил и выложил как функцию в какую-нибудь библиотеку.

Дано: пиксельная картинка произвольной формы на холсте с размерами Х*Y. Считаем, что координаты левого верхнего угла холста 0,0.
Задача: Найти максимальные стороны прямоугольника с заданным соотношением сторон k, полностью находящегося в картинке.
[длина горизонтальной стороны прямоугольника]/[длина вертикальной стороны прямоугольника]=k.
Функция должна возвращать массив из трех чисел:
1-2) r[0], r[1] — координаты верхнего левого угла прямоугольника на холсте.
3) r[2] — длина горизонтальной стороны прямоугольника.

Здравствуйте, qwp, Вы писали:


qwp>Настолько полезная, что вполне возможно, кто-то ее уже решил и выложил как функцию в какую-нибудь библиотеку.

qwp>Дано: пиксельная картинка произвольной формы на холсте с размерами Х*Y. Считаем, что координаты левого верхнего угла холста 0,0.
qwp>Задача: Найти максимальные стороны прямоугольника с заданным соотношением сторон k, полностью находящегося в картинке.
qwp>[длина горизонтальной стороны прямоугольника]/[длина вертикальной стороны прямоугольника]=k.
qwp>Функция должна возвращать массив из трех чисел:
qwp>1-2) r[0], r[1] — координаты верхнего левого угла прямоугольника на холсте.
qwp>3) r[2] — длина горизонтальной стороны прямоугольника.

Что понимается под прямоугольником?
Пиксели одинакового цвета? Какого-то конкретного цвета? Иное?

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, qwp, Вы писали:

Б>Что понимается под прямоугольником?
Б>Пиксели одинакового цвета? Какого-то конкретного цвета? Иное?

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

Здравствуйте, qwp, Вы писали:

qwp>Дано: пиксельная картинка произвольной формы на холсте с размерами Х*Y. Считаем, что координаты левого верхнего угла холста 0,0.
qwp>Задача: Найти максимальные стороны прямоугольника с заданным соотношением сторон k, полностью находящегося в картинке.
qwp>[длина горизонтальной стороны прямоугольника]/[длина вертикальной стороны прямоугольника]=k.

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

Есть решение за O(N^3), где N — ширина/длина холста. Надо лучше?

Здравствуйте, Буравчик, Вы писали:

Б>Т.е. задан холст, закрашенный белым цветом. На нем нарисована какая-то фигура черным цветом. Нужно найти максимальный прямоугольник, который можно вписать в черную фигуру. При этом отношение сторон прямоугольника равно k.
Б>Есть решение за O(N^3), где N — ширина/длина холста. Надо лучше?

Это без дополнительной памяти?

Если у нас есть XY дополнительной памяти, то должно быть быстрее.

Сперва — решение для квадрата.
Для каждой точки будем искать сторону квадрата, чей правый нижний угол — эта точка.

Для точек фона это значение, очевидно, 0.

Для точки с координатами P[x,y] найдём сторону квадрата p
рассмотрим точки Q[x-1,y] и R[x,y-1], обозначив стороны их квадратов как q, r
— если q <= r-1, то p = q+1

+---------+
|         |
| +-----+-+
| |     | |
| |     | |
+-+-----+-R
  |     | |
  +-----Q-P

— если r <= q-1, то, соответственно, p = r+1
— наконец, если q==r, то нужно проверить ещё одну точку — левый верхний угол S[x-q,y-q]: если он фоновый, то p = q, если фигура — то q+1

S +-------+
  |       |
+-+-----+ |
| |     | |
| |     | |
| +-----+-R
|       | |
+-------Q-P

Для прямоугольников не квадратной пропорции надо подумать.

Например, найти максимальные квадраты. Затем для каждой точки найти максимальный прямоугольник, исходя из максимальных квадратов.
Пусть пропорция, например, M = 7/2 (2 по высоте, 7 по ширине).
И максимальный квадрат в точке [x,y] равен p.
Тогда оценка снизу — это p*2/7, оценка сверху — p.
Мысленно продлим квадрат влево, получим там 3.5 квадрата высотой p. Нам придётся сделать максимум 4 проверки, чтобы уточнить высоту квадрата, бегущего по этой полоске.

Для больших значений M это может быть накладно. Тогда второй подход: сжать картинку, чтобы сделать пропорцию квадратной. И как-то обрабатывать серые пикселы...

Здравствуйте, samius, Вы писали:
S>Полагаю, речь идет о том, что бы отобразить некий объект (картинку) максимально "распахнутым" на экране/в окне, без искажения пропорций.
Именно так.

Здравствуйте, Буравчик, Вы писали:
Б>Т.е. задан холст, закрашенный белым цветом.
Нет, задача все-таки жизненная. Цвет холста может быть любым. Например, голубое небо.

Б> На нем нарисована какая-то фигура черным цветом.
В принципе, можно сделать отдельную функцию, которая будет понимать, к чему точка относится: к холсту или к картинке. И тогда белый/черный подойдет. Но такая функция должна работать не хуже человеческого глаза. Ведь человек, глядя на произвольную картинку, может понять с большой вероятностью, где картинка, а где холст.

Б>Есть решение за O(N^3), где N — ширина/длина холста. Надо лучше?

А почему в кубе?

Здравствуйте, qwp, Вы писали:

Б>>Т.е. задан холст, закрашенный белым цветом.
qwp>Нет, задача все-таки жизненная. Цвет холста может быть любым. Например, голубое небо.

Пусть летят K самолётов противника. Нет, K мало, пусть летят N

Здравствуйте, qwp, Вы писали:

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

Wdt, Hgt — размеры картинки
ClientWidth, ClientHeight — размеры окна
X0, Y0 — координаты вывода в окно

 if ClientWidth * Hgt >= ClientHeight * Wdt then begin  //окно широкое, поля по бокам
    Y0 := 0;
    X0 := (ClientWidth - Wdt * ClientHeight div Hgt) div 2;
  end
  else begin  //окно узкое, поля сверху и снизу
    X0 := 0;
    Y0 := (ClientHeight - ClientWidth * Hgt div Wdt) div 2;
  end;