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

Question

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

• Пусть R быть ограничивающий прямоугольник, любого размера и соотношения сторон (в случае необходимости, позволяет предположить, соотношение сторон не будет превышать 2/1 и 1/2).

• Пусть С круг, центр которого находится внутри R, и одна точка, по крайней мере внутри R. Некоторые моменты, однако, может быть из R.

• Пусть г произвольное соотношение сторон, возможно, различные от R.

Есть ли известный алгоритм размер и положение прямоугольника R «с соотношением сторон г, что полностью пересекающая R, так что R» П С максимальна (п для пересекаются, не знают, как введите MathML здесь).

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

Я ожидаю, что R и R 'не будут вращаться, то есть их стороны либо параллельны единичному вектору, либо перпендикулярны ему. Но решение, где две стороны R параллельны двум сторонам R ', и оба они вращаются произвольно, будут идеально вписываться, тогда я был бы в конкретном случае.

Спасибо Вам много,

Матье

Answer 1

Некоторые замечания, которые могут быть полезны:

1) Как сказал Генри в комментариях «вы получите оптимальный, если R' как большой, насколько это возможно, так он будет либо иметь ту же высоту, либо такую ​​же ширину, что и R. Это позволит просто оптимизировать один параметр (одномерное положение) ».

2) Теперь у вас есть прямоугольник R', который можно скользить по высоте R или по ширине R. Я считаю, что вы обнаружите, что если вы переместите R' так, чтобы его центр был как можно ближе к центру круга, он будет охватывать большую площадь.

3) Является ли отношение r всегда шириной/высотой, или может быть также высота/ширина? Другими словами, можно ли поворачивать R', чтобы лучше вписаться в R? Если это так, вам нужно будет рассмотреть два ответа, если r != 1. Для сравнения вам нужно будет вычислить площадь пересечения R' и вашего круга. Вероятно, это самая сложная проблема. Вы даете радиус круга, или вы просто знаете, что какая-то часть края пересекает R?

4) Если R не параллельно и перпендикулярно осям, вы можете применить перевод довести центр окружности к происхождению (0, 0), а затем поворот, чтобы сделать R быть выровнены по осям. Затем разрешите найти координаты углов R', а затем примените обратное вращение и обратный перевод в координаты углов R', чтобы найти окончательное решение.