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

Question

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

Я хочу реализовать это в python 2.7, но сначала мне нужен протокол, который охватывает все случаи - может быть, библиотека python, которую я не знаю (стройная?), может помочь в этом?

A________D 
| a d | 
|  | 
|  | 
| b c | 
B________C 

E_______H 
|  | 
|  | 
|  | 
F_______G 

Вы почти прямоугольной четырехугольник ABCD (отверстие)

Вы знаете все стороны AB, BC, CD, AD и диагоналей AC, BD, что благодаря теореме Аль Каши и некоторые тригонометрию вы также знаете все 4 угла a, b, c, d

Как вы вычисляете ширину и высоту самого большого прямоугольника EFGH (окно, которое вы хотите построить, которое будет прямоугольным), которое может вписываться в t он четырехугольник, если сторона FG прямоугольника параллельная сторона BC четырехугольника?

(BC соответствует горизонтальной нижней части отверстия, на которой FG - нижняя часть окна-стойки).

A__________D 
|E________H| 
||  || 
||  || 
||  || 
||  || 
BF________GC 

Answer 1

Это с головы, так что предостерегайте emptor.

Сначала поверните ABCD так, чтобы сторона BC была горизонтальной. Затем вы хотите поместить выровненный по оси прямоугольник в повернутую форму. Наконец, если вам нужны координаты E, F, G, H, вы должны повернуть прямоугольник через отрицательный угол угла, используемого на первом шаге; если вам просто нужна ширина и высота, вы можете взять их из выровненного по оси прямоугольника.

Для установки оси выровнена прямоугольника: (я буду использовать имена A, B и т.д. для вершин повернутого четырехугольника)

Найти крайние правые из двух крайних левых точек (А и В), и вызове это W и нижняя из двух верхних точек (A и D) и назовем это X. Тогда точкой E будет пересечение вертикальной линии по W с горизонтальной линией через X.

Аналогично, G является пересечением вертикальной линии через крайнюю левую из двух самых правых точек (D и C) с горизонтальной линией через верхнюю часть двух нижних точек (B и C) и т. д.