Доброго времени суток форумчане!
Прошу помощи в след. нестандартной задаче "по графике"

Требуется найти  максимальный по площади прямоугольник (и его  координаты верхнего левого и правого нижнего угла) со сторонами параллельными осям координат и размещающийся в другом наибольшем прямоугольнике, который не пересекает(возможно имеет общие точки) заданный отрезок A-B. 

Наибольший прямоугольник(внутри которого рисуется линия и требуется найти другой прямоугольник ) задается переменными W,H, где W,H – ширина и высота в пикселах (начало координат – левый верхней угол окна), AX,AY, BX,BY – координаты вершин A и B отрезка.


Я даже не знаю с какой стороны подойти к задаче,   думаю, что нужно плясать от координат отрезка, но КАК осуществлять сам поиск(это основная загвоздка) координат углов прямоугольника причём таких чтобы этот прямоугольник был самым большим который только можно нарисовать в этой области я понять не могу     

  

Это сообщение отредактировал(а) Нэраварин - 14.12.2012, 08:22

Задача элементарно решается аналитически.

а по подробнее можно?

Поподробнее что? курс геометрии 8-го класса?

Эмм перечитайте пожалуйста мой первый пост повнимательнее...

если стороны обоих прямоугольников параллельны осям координат, то как вы нарисовали, так и будет -- один из углов искомого прямоугольника совпадает с углом большого прямоугольника, а противоположный угол или лежит на отрезке или на противоположной стороне большого прямоугольника, и тогда сторона меньшего прямоугольника проходит через конец отрезка

так оно и есть 



так как это вывести алгоритмически? может это и элементарные операции но что то я никак не догоняю до них после нескольких бессоных ночей....обрисуйте пожалуйста именно алгоритм нахождения координат угла искомого наибольшего по площади прямоугольника   



что вы имели в виду под "проходит"? если имеет общие точки то это допустимо если же пересекает хоть и слегка то это не допустимо!

Перечитал. Внимательно. Моё мнение не изменилось. Если не считать того, что необходимо рассмотреть три варианта (см. аттач).
Варианты 2 и 3 в расчёте тривиальны.
Что же до варианта 1... Координаты точек A,B,D - известны и фиксированы.
Задавая различные положения точки С, например, изменяя абсциссу Xc от Xa до Xb, и рассчитывая ординату как функцию абсциссы, получаем функцию зависимости площади прямоугольника задаваемого точками C и D от одной переменной Xc. Функция - квадратичная. Аналитически найти её максимум (а что это будет максимум - очевидно) - элементарно (формула должна просто от зубов отскакивать). И если этот максимум лежит в диапазоне от Xa до Xb, то это он и есть, а если за пределами - то максимумом в области определения будет ближайшая из границ диапазона. Остаётся посчитать значение функции (площади) в этой точке, сравнить с площадями по вариантам 2 и 3, и выбрать абсолютный максимум.


Присоединённый файл ( Кол-во скачиваний: 34 )
 1.gif 4,73 Kb

В таком случае алгоритм обречён на большое количество проверок....если я всё правильно понял.
и скажите рисунок в формате гиф это случайность? или там всё таки должна быть анимация...

Четыре IF - это что, большое количество? 


Нет. В этом формате рисунок получился наиболее компактным (без потери качества).

ИМХО решается самой тривиальной производной:
Координаты искомого угла прямоугольника X,Y. Координаты дального угла соответствуют ширине и высоте поля W,H. Тогда площадь прямоугольника будет произведением разностей и искаться будет максимум:
(W-X)*(H-Y)=max
Понятное дело, минусы-плюсы в этой формуле будут зависеть от заданной системы координат, но это уже точно младшешкольная геометрия - не будем распыляться.
Имеем также формулу наклонной прямой:
y=ax+b
Подставляем прямую:
(W-x)*(H-ax-b)=max
Ну а дальше ищем точку, в которой производная равна нулю  

Большое спасибо всем за помощь, но что то я не разберусь как быть в таком случае?


Да и вариант предложенный уважаемым Akina с перебором абсолютных максимумов не кажется мне удачным, возможно ли какое-либо другое, более лаконичное решение?

Он ничем не отличается от исходного и от моего вар. 1.

А куда ты денешься от проверки всех трёх вариантов...