Как я могу вписать прямоугольник или круг в произвольный четырехугольник

Question

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

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

Вот 2 примера вписанного максимизации, которого я пытаюсь достичь:

Я провел предварительный поиск, но не нашел ничего определенного.Кажется, что какая-то форма динамического программирования может быть решением.Похоже, что это должна быть задача линейной оптимизации, которая должна встречаться чаще, чем я обнаружил, и, возможно, я ищу неправильные термины.что мы знаем целевое соотношение w / h, которое мы ищем (например, 4: 3).Для квадрата предположим, что стороны не будут пересекаться и будут вогнутыми (если это упрощает расчет).

Answer 1

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

2) Прямоугольник.
Вы не можете иметь "наибольшая высота и ширина" , вам нужно выбрать другой критерий. Например, на вашем изображении я могу увеличить ширину, уменьшив высоту и наоборот.

Answer 2

4-летняя тема, но я случайно наткнулся на нее, когда гуглил мою проблему.

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

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

Сначала предположим набор из 4 точек, образующих наш (выпуклый) четырехугольник:

    x   y
P1  -2  -5
P2  1   7
P3  4   5  
P4  3   -2

Для этой процедуры самой левой точкой является P1, следующие точки нумеруются по часовой стрелке. Это выглядит так:

Затем мы создадим линейные функции между точками. Для каждой функции мы должны знать наклон k и расстояние от 0: d. k - это просто разница в Y двух точек, деленная на разницу в X. d можно рассчитать, решив линейную функцию для d. Итак, у нас есть

k=dy/dx
d=y1-k*x1

Нам также понадобятся обратные функции.

k_inv = 1/k
d_inv = -d/k

Затем мы создаем функцию и обратную функцию для каждой стороны четырехугольника

        k        d                        k         d
p1p2    4       3           p1p2_inv    0.25    -0.75
p2p3    -0.67   7.67        p2p3_inv    -1.5    11.5
p3p4    7       -23         p3p4_inv    0.14    3.29
p4p1    0.6     -3.8        p4p1_inv    1.67    6.33

Если бы у нас были полностью горизонтальные или вертикальные линии, мы бы получили DIV / 0 в одной из функций или обратных функций, поэтому нам пришлось бы обрабатывать этот случай отдельно.

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

Мы начинаем с P2 и перебираем значения y между P2 и старшим из P1 и P3 с соответствующим размером шага и используем обратные функции для вычисления расстояния между функциями в горизонтальном направлении. Это даст нам одну сторону прямоугольника

a=p2p3_inv(y)-p1p2_inv(y)

При двух значениях x x = p2p3_inv (y) и x = p1p2_inv (y) мы затем вычисляем разницу в y для двух противоположных функций и принимаем расстояние до нашей текущей позиции y в качестве кандидата на вторую сторону наш прямоугольник.

b_candidate_1 = y-p4p1(p2p3_inv(y))
b_candidate_2 = y-p4p1(p1p2_inv(y))
b_candidate_3 = y-P3p4(p2p3_inv(y))
b_candidate_4 = y-P3p4(p1p2_inv(y))

Меньший из четырех параметров будет решением для стороны b. Область, очевидно, становится * б.

Я сделал быстрый пример в Excel, чтобы продемонстрировать:

минимальное значение b здесь равно 6,9, поэтому верхний правый угол решения находится на p2p3, а прямоугольник проходит a по горизонтали и b по вертикали влево и вниз соответственно.

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

Rect    x       y
R1      0.65    -1.3
R2      0.65    5.6
R3      3.1     5.6
R4      3.1     -1.3

Мне нужно будет поместить это в код C ++ и выполнить несколько тестов, чтобы увидеть, обобщает ли решение или это просто «удача».

Я думаю, что также должно быть возможно заменить a и b в A = a * b функциями и поместить их в одну линейную формулу, которую нужно максимизировать при условии, что p1p2 определено только между P1 и P2 и т. Д. ..