Задача такая:
есть: на координатной плоскости n-угольник произвольный, заданный ломаной прямой без самопересечений.
надо: вписать в него (те определить координаты 4х (2х) вершин) прямоугольник, у которого задано отношение длин сторон и направление (направляющий вектор) одной из сторон. Желательно, чтобы этот прямоугольник был максимального размера.

Несколько взаимоисключающие условия, не находишь? По определению - вписать == это построить так, чтобы вершины прямоугольника лежали на границе многоугольника. Если задано направление одной из осей, такой прямоугольник вообще единственный - или вообще не существует. А есть еще и ограничение на соотношение сторон. 
Может, "вписать" у тебя что-то другое означает?

 Согласен был не прав.

Скажем так: 
надо: найти прямоугольник максимального размера (те определить координаты 4х (2х) вершин), у которого задано отношение длин сторон и направление (направляющий вектор) одной из сторон, лежащий внутри n-угольника. 

а n-угольник выпуклый ?

Добавлено через 11 минут и 49 секунд
опс.. просмотрел



Это сообщение отредактировал(а) 4d5a - 1.11.2008, 07:17

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

Добавлено через 9 минут и 56 секунд
перебирать все возможные  точки на отрезке уже не получится, т.к. их бесконечное количество
так что придётся представить размер прямоугольника в аналитической форме (а скорее всего, в кусочно аналитической) в зависимости от положения это точки на выбранном отрезке
ситуацию упрощает, что у нас есть направления сторон и соотношение их длин
если у нас отрезок параллелен одной из сторон, возможно два направления прямоугольника (если отрезок и прямоугольник горизонтальные, то прямоугольник может лежать справа или слева от точки), тогда нужно перебрать два варианта
в остальных случаях - направление точно известно
тогда мы просто находим размер, при котором прямоугольник упрётся в первое же препятствие
формула, дающая это число будет содержать всякие min, max от каких-то выражений, включающих функции (на первый взгляд линейные) от координат многоугольника
ну а если они окажутся линейными, то максимум будет достигаться в точках, где аргументы одного из min/max сравниваются, отсюда уже можно получить конечный набор точек-кандидатов на отрезке, а там уже можно просто перебрать их

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

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

зато придумал второй вариант:
для начала в целях упрощения повернём всё так, чтобы стороны прямоугольника стали вертикальны и горизонтальны, а потом растянем одну из координат так, чтобы соотношение стало 1 (т.е. квадрат)

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

Это сообщение отредактировал(а) maxim1000 - 2.11.2008, 01:13

Присоединённый файл ( Кол-во скачиваний: 11 )
 squares.PNG 10,04 Kb