CODEWITHSUNDEEP
pythonpython-2.7geometrymeasureshapely
adrienlucca.net
adrienlucca.net

Reputation: 687

A simple algorithm to find the biggest rectangle fitting within a quadrangle

My problem comes from a concrete application: if you want to install a rectangular window EFGH inide of an existing near-rectangular hole ABCD, and you want to come with the biggest possible window (you want to build a metallic frame for an existing building where the opening is nearly perfect, but not completely...)

I want to implement this in python 2.7, but first I need the protocol that covers all cases - maybe a python library that I don't know (shapely?) can help doing that?

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

E_______H
|       |
|       |
|       |
F_______G

You have a near-rectangular quadrangle ABCD (the hole)

You know all sides AB, BC, CD, AD, and the diagonals AC, BD, thus thanks to the Al Kashi theorem and some trigonometry you also know all 4 angles a, b, c, d

How do you calculate the width and height of the largest rectangle EFGH (the window that you want to build, which will be rectangular) that can fit in the quadrangle, if the side FG of the rectangle is parallel to the side BC of the quadrangle?

(BC corresponds to the horizontal bottom part of the opening, on which FG - the bottom part of the window - stands).

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

Upvotes: 1

Views: 866

Answers (1)

dmuir
dmuir

Reputation: 4431

This is off the top of my head, so caveat emptor.

First rotate ABCD so that the side BC is horizontal. Then you want to fit an axis aligned rectangle into the rotated shape. Finally, if you need the coordinates of E,F,G,H you should rotate the rectangle through the negative of the angle used in the first step; if you just need the width and height you can take them from the axis aligned rectangle.

To fit the axis aligned rectangle: (I'll use the names A, B etc for the vertices of the rotated quad)

Find the rightmost of the two leftmost points (A and B), and call this W, and the lower of the two upper points (A and D) and call this X. Then the point E will be the intersection of vertical line through W with the horizontal line through X.

Similarly G is the intersection of the vertical line through the leftmost of the two rightmost points (D and C) with the horizontal line through the upper of the two lower points (B and C), and so on.

Upvotes: 1

Related Questions