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

Question

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

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

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

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

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

Answer 1

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

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

Answer 2

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

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

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

Во-первых, предположим, набор из 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) 

В два х значения х = p2p3_inv (у) и х = p1p2_inv (у) мы затем вычислить разницу в у к двум противоположным функций и принять расстояние к нашей текущей позиции 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. Область, очевидно, становится * b.

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

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

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

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 и т. Д. ...