Maximal Rectangle

About

It is a Delphi implementation of the maximal empty rectangle problem³. Interest was sparked by an article by David Vandevoorde,The Maximal Rectangle Problem¹. The idea of the algorithm for solving the problem is based on a paper by Thomas M. Breuel, Two Geometric Algorithms for Layout Analysis².

Note: The accompanied example app will avoid enumerating Windows Store based apps because of the lack of cloaked window detection. That requires further usage of DwmAPI, and more code to be written. That is outside the scope and intentions of the example code provided.

API

Constructor

TMaximalRectangle.Create(bound);

Properties

Methods

Usage

procedure TfrmMain.DoFindMaximalWhiteSpace;
var
  BoundingRect : TRect;
  MaximalRect : TRect;
begin
  BoundingRect := Rect(0, 0, 1024, 512);
  Maximal := TMaximalRectangle.Create(BoundingRect);
  try
    Maximal.ClearObstacles;

    Maximal.AddObstacle(Rect(0, 0, 100, 100));

    if Maximal.GetMaxWhitespace(MaximalRect) then begin
      Self.BoundsRect := MaximalRect;
    end;
  finally
    Maximal.Free;
  end;
end;

References

1. David Vandevoorde, "The Maximal Rectangle Problem", Dr Dobb's, 1998.

2. Thomas M. Breuel, "Two Geometric Algorithms for Layout Analysis", Xerox Palo Alto Research Center, 2002.

3. "Largest empty rectangle", In Wikipedia. Retrieved February, 2017.

License

Maximal Rectangle is released under the MIT license. See LICENSE for details.