Categories &

Functions List

Function Reference: geom.largestrect

drafting: R = geom.largestrect (P)
drafting: R = geom.largestrect (P, MARGINS)
drafting: [R, B] = geom.largestrect (…)

Largest axis-aligned rectangle inscribed in a rectilinear polygon.

R = geom.largestrect (P) returns the largest axis-aligned rectangle that fits inside the polygon P, as a 4-by-2 matrix of vertices wound counter-clockwise starting from the lower-left corner.

R = geom.largestrect (P, MARGINS) additionally keeps the rectangle clear of every wall of P by the given margins, the face of a notch included and not merely the bounding box. MARGINS is a scalar applied to all four sides, or the 1-by-4 vector [left, bottom, right, top] naming them individually, in the units of P. All values must be non-negative and it defaults to zero.

Clearance is measured per axis, so the right margin is held against whichever wall bounds the rectangle on its right — the outline’s own right-hand side, or the inner face of a notch, whichever it meets first.

This is the operation that fits a usable rectangle inside an irregular outline: the per-side margins are the clearance budget — whatever has to be kept free along each side — and the result is the largest rectangle that budget leaves room for.

[R, B] = geom.largestrect (…) also returns the rectangle in the compact form [xmin, ymin, xmax, ymax] used by geom.bbox.

Rectilinear input only. P must satisfy geom.isrectilinear. The search considers only rectangles whose edges lie on lines through vertices of P, which is exactly where an optimal rectangle must lie when the outline is rectilinear; on a sloped edge that reasoning fails and the answer would be wrong rather than merely conservative, so such input is rejected instead.

Where several rectangles tie for the largest area, the first encountered is returned, scanning x bounds before y bounds and each in ascending order. The result is therefore deterministic.

See also: geom.bbox, geom.offset, geom.isrectilinear

Source Code: geom.largestrect

The largest axis-aligned rectangle that fits inside an outline, with a per-side clearance kept free. The margins are the budget; the rectangle is what that budget leaves room for.

 P = [0, 0; 60, 0; 60, 20; 30, 20; 30, 45; 0, 45];
 [R, B] = geom.largestrect (P, [4, 6, 4, 3])
R =

    4    6
   26    6
   26   42
    4   42

B =

    4    6   26   42
 D = draw.Drawing ().polyline (P, true);
 D.Colour = 'red';
 D = D.polyline (R, true);
 plot (D);
 title ('the biggest rectangle that fits, after the clearances');
plotted figure