Bug 613449. Extend GetLargestRectangle to support considering only rectangles that contain a given rectangle. r=robarnold
authorRobert O'Callahan <robert@ocallahan.org>
Tue, 04 Jan 2011 16:56:57 +1300
changeset 59821 cf82d60b3f1c61815f4d1c61f7525280c285d488
parent 59820 c2325c5439c3f9fac931666c22f3b9249eca0832
child 59822 9713b198fe3d41b5f706deb16b42785b7164ab3f
push idunknown
push userunknown
push dateunknown
reviewersrobarnold
bugs613449
milestone2.0b9pre
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 613449. Extend GetLargestRectangle to support considering only rectangles that contain a given rectangle. r=robarnold
gfx/src/nsRegion.cpp
gfx/src/nsRegion.h
gfx/tests/TestRegion.cpp
--- a/gfx/src/nsRegion.cpp
+++ b/gfx/src/nsRegion.cpp
@@ -1334,22 +1334,32 @@ nsIntRegion nsRegion::ToOutsidePixels (n
   const nsRect* currentRect;
   while ((currentRect = rgnIter.Next())) {
     nsIntRect deviceRect = currentRect->ToOutsidePixels(aAppUnitsPerPixel);
     result.Or(result, deviceRect);
   }
   return result;
 }
 
-// This algorithm works in three phases:
+// A cell's "value" is a pair consisting of
+// a) the area of the subrectangle it corresponds to, if it's in
+// aContainingRect and in the region, 0 otherwise
+// b) the area of the subrectangle it corresponds to, if it's in the region,
+// 0 otherwise
+// Addition, subtraction and identity are defined on these values in the
+// obvious way. Partial order is lexicographic.
+// A "large negative value" is defined with large negative numbers for both
+// fields of the pair. This negative value has the property that adding any
+// number of non-negative values to it always results in a negative value.
+//
+// The GetLargestRectangle algorithm works in three phases:
 //  1) Convert the region into a grid by adding vertical/horizontal lines for
 //     each edge of each rectangle in the region.
 //  2) For each rectangle in the region, for each cell it contains, set that
-//     cells's value to the area of the subrectangle it corresponds to. Cells
-//     that are not contained by any rectangle have the value 0.
+//     cells's value as described above.
 //  3) Calculate the submatrix with the largest sum such that none of its cells
 //     contain any 0s (empty regions). The rectangle represented by the
 //     submatrix is the largest rectangle in the region.
 //
 // Let k be the number of rectangles in the region.
 // Let m be the height of the grid generated in step 1.
 // Let n be the width of the grid generated in step 1.
 //
@@ -1365,17 +1375,17 @@ nsIntRegion nsRegion::ToOutsidePixels (n
 // Phase3 = function (G, A, m, n) {
 //   let (t,b,l,r,_) = MaxSum2D(A,m,n)
 //   return rect(G[t],G[l],G[r],G[b]);
 // }
 // MaxSum2D = function (A, m, n) {
 //   S = array(m+1,n+1)
 //   S[0][i] = 0 for i in [0,n]
 //   S[j][0] = 0 for j in [0,m]
-//   S[j][i] = (if A[j-1][i-1] = 0 then some large negative number else A[j-1][i-1])
+//   S[j][i] = (if A[j-1][i-1] = 0 then some large negative value else A[j-1][i-1])
 //           + S[j-1][n] + S[j][i-1] - S[j-1][i-1]
 //
 //   // top, bottom, left, right, area
 //   var maxRect = (-1, -1, -1, -1, 0);
 //
 //   for all (m',m'') in [0, m]^2 {
 //     let B = { S[m'][i] - S[m''][i] | 0 <= i <= n }
 //     let ((l,r),area) = MaxSum1D(B,n+1)
@@ -1447,48 +1457,87 @@ namespace {
     PRInt32 GetNumStops() const { return mStops.Length(); }
 
   private:
     nsTArray<nscoord> mStops;
   };
 
   const PRInt64 kVeryLargeNegativeNumber = 0xffff000000000000ll;
 
+  struct SizePair {
+    PRInt64 mSizeContainingRect;
+    PRInt64 mSize;
+
+    SizePair() : mSizeContainingRect(0), mSize(0) {}
+
+    static SizePair VeryLargeNegative() {
+      SizePair result;
+      result.mSize = result.mSizeContainingRect = kVeryLargeNegativeNumber;
+      return result;
+    }
+    SizePair& operator=(const SizePair& aOther) {
+      mSizeContainingRect = aOther.mSizeContainingRect;
+      mSize = aOther.mSize;
+      return *this;
+    }
+    PRBool operator<(const SizePair& aOther) const {
+      if (mSizeContainingRect < aOther.mSizeContainingRect)
+        return PR_TRUE;
+      if (mSizeContainingRect > aOther.mSizeContainingRect)
+        return PR_FALSE;
+      return mSize < aOther.mSize;
+    }
+    PRBool operator>(const SizePair& aOther) const {
+      return aOther.operator<(*this);
+    }
+    SizePair operator+(const SizePair& aOther) const {
+      SizePair result = *this;
+      result.mSizeContainingRect += aOther.mSizeContainingRect;
+      result.mSize += aOther.mSize;
+      return result;
+    }
+    SizePair operator-(const SizePair& aOther) const {
+      SizePair result = *this;
+      result.mSizeContainingRect -= aOther.mSizeContainingRect;
+      result.mSize -= aOther.mSize;
+      return result;
+    }
+  };
+
   // Returns the sum and indices of the subarray with the maximum sum of the
   // given array (A,n), assuming the array is already in prefix sum form.
-  PRInt64 MaxSum1D(const nsTArray<PRInt64> &A, PRInt32 n,
-                   PRInt32 *minIdx, PRInt32 *maxIdx) {
+  SizePair MaxSum1D(const nsTArray<SizePair> &A, PRInt32 n,
+                    PRInt32 *minIdx, PRInt32 *maxIdx) {
     // The min/max indicies of the largest subarray found so far
-    PRInt64 min = 0,
-            max = 0;
+    SizePair min, max;
     PRInt32 currentMinIdx = 0;
 
     *minIdx = 0;
     *maxIdx = 0;
 
     // Because we're given the array in prefix sum form, we know the first
     // element is 0
     for(PRInt32 i = 1; i < n; i++) {
-      PRInt64 cand = A[i] - min;
+      SizePair cand = A[i] - min;
       if (cand > max) {
         max = cand;
         *minIdx = currentMinIdx;
         *maxIdx = i;
       }
       if (min > A[i]) {
         min = A[i];
         currentMinIdx = i;
       }
     }
 
     return max;
   }
 }
 
-nsRect nsRegion::GetLargestRectangle () const {
+nsRect nsRegion::GetLargestRectangle (const nsRect& aContainingRect) const {
   nsRect bestRect;
 
   if (mRectCount <= 1) {
     bestRect = mBoundRect;
     return bestRect;
   }
 
   AxisPartition xaxis, yaxis;
@@ -1497,82 +1546,88 @@ nsRect nsRegion::GetLargestRectangle () 
   nsRegionRectIterator iter(*this);
   const nsRect *currentRect;
   while ((currentRect = iter.Next())) {
     xaxis.InsertCoord(currentRect->x);
     xaxis.InsertCoord(currentRect->XMost());
     yaxis.InsertCoord(currentRect->y);
     yaxis.InsertCoord(currentRect->YMost());
   }
+  if (!aContainingRect.IsEmpty()) {
+    xaxis.InsertCoord(aContainingRect.x);
+    xaxis.InsertCoord(aContainingRect.XMost());
+    yaxis.InsertCoord(aContainingRect.y);
+    yaxis.InsertCoord(aContainingRect.YMost());
+  }
 
   // Step 2: Fill out the grid with the areas
   // Note: due to the ordering of rectangles in the region, it is not always
   // possible to combine steps 2 and 3 so we don't try to be clever.
   PRInt32 matrixHeight = yaxis.GetNumStops() - 1;
   PRInt32 matrixWidth = xaxis.GetNumStops() - 1;
   PRInt32 matrixSize = matrixHeight * matrixWidth;
-  nsTArray<PRInt64> areas(matrixSize);
+  nsTArray<SizePair> areas(matrixSize);
   areas.SetLength(matrixSize);
-  memset(areas.Elements(), 0, matrixSize * sizeof(PRInt64));
 
   iter.Reset();
   while ((currentRect = iter.Next())) {
     PRInt32 xstart = xaxis.IndexOf(currentRect->x);
     PRInt32 xend = xaxis.IndexOf(currentRect->XMost());
     PRInt32 y = yaxis.IndexOf(currentRect->y);
     PRInt32 yend = yaxis.IndexOf(currentRect->YMost());
 
     for (; y < yend; y++) {
       nscoord height = yaxis.StopSize(y);
       for (PRInt32 x = xstart; x < xend; x++) {
         nscoord width = xaxis.StopSize(x);
-        areas[y*matrixWidth+x] = width*PRInt64(height);
+        PRInt64 size = width*PRInt64(height);
+        if (currentRect->Intersects(aContainingRect)) {
+          areas[y*matrixWidth+x].mSizeContainingRect = size;
+        }
+        areas[y*matrixWidth+x].mSize = size;
       }
     }
   }
 
   // Step 3: Find the maximum submatrix sum that does not contain a rectangle
   {
     // First get the prefix sum array
     PRInt32 m = matrixHeight + 1;
     PRInt32 n = matrixWidth + 1;
-    nsTArray<PRInt64> pareas(m*n);
+    nsTArray<SizePair> pareas(m*n);
     pareas.SetLength(m*n);
-    // Zero out the first row
-    for (PRInt32 x = 0; x < n; x++)
-      pareas[x] = 0;
     for (PRInt32 y = 1; y < m; y++) {
-      // Zero out the left column
-      pareas[y*n] = 0;
       for (PRInt32 x = 1; x < n; x++) {
-        PRInt64 area = areas[(y-1)*matrixWidth+x-1];
-        if (!area)
-          area = kVeryLargeNegativeNumber;
-        area += pareas[    y*n+x-1]
-              + pareas[(y-1)*n+x  ]
-              - pareas[(y-1)*n+x-1];
+        SizePair area = areas[(y-1)*matrixWidth+x-1];
+        if (!area.mSize) {
+          area = SizePair::VeryLargeNegative();
+        }
+        area = area + pareas[    y*n+x-1]
+                    + pareas[(y-1)*n+x  ]
+                    - pareas[(y-1)*n+x-1];
         pareas[y*n+x] = area;
       }
     }
 
     // No longer need the grid
     areas.SetLength(0);
 
-    PRInt64 bestArea = 0;
+    SizePair bestArea;
     struct {
       PRInt32 left, top, right, bottom;
     } bestRectIndices = { 0, 0, 0, 0 };
     for (PRInt32 m1 = 0; m1 < m; m1++) {
       for (PRInt32 m2 = m1+1; m2 < m; m2++) {
-        nsTArray<PRInt64> B;
+        nsTArray<SizePair> B;
         B.SetLength(n);
-        for (PRInt32 i = 0; i < n; i++)
+        for (PRInt32 i = 0; i < n; i++) {
           B[i] = pareas[m2*n+i] - pareas[m1*n+i];
+        }
         PRInt32 minIdx, maxIdx;
-        PRInt64 area = MaxSum1D(B, n, &minIdx, &maxIdx);
+        SizePair area = MaxSum1D(B, n, &minIdx, &maxIdx);
         if (area > bestArea) {
           bestRectIndices.left = minIdx;
           bestRectIndices.top = m1;
           bestRectIndices.right = maxIdx;
           bestRectIndices.bottom = m2;
           bestArea = area;
         }
       }
--- a/gfx/src/nsRegion.h
+++ b/gfx/src/nsRegion.h
@@ -179,17 +179,23 @@ public:
   PRUint32 GetNumRects () const { return mRectCount; }
   const nsRect& GetBounds () const { return mBoundRect; }
   // Converts this region from aFromAPP, an appunits per pixel ratio, to
   // aToAPP. This applies nsRect::ConvertAppUnitsRoundOut/In to each rect of
   // the region.
   nsRegion ConvertAppUnitsRoundOut (PRInt32 aFromAPP, PRInt32 aToAPP) const;
   nsRegion ConvertAppUnitsRoundIn (PRInt32 aFromAPP, PRInt32 aToAPP) const;
   nsIntRegion ToOutsidePixels (nscoord aAppUnitsPerPixel) const;
-  nsRect GetLargestRectangle () const;
+  /**
+   * Gets the largest rectangle contained in the region.
+   * @param aContainingRect if non-empty, we choose a rectangle that
+   * maximizes the area intersecting with aContainingRect (and break ties by
+   * then choosing the largest rectangle overall)
+   */
+  nsRect GetLargestRectangle (const nsRect& aContainingRect = nsRect()) const;
 
   /**
    * Make sure the region has at most aMaxRects by adding area to it
    * if necessary. The simplified region will be a superset of the
    * original region. The simplified region's bounding box will be
    * the same as for the current region.
    */
   void SimplifyOutward (PRUint32 aMaxRects);
@@ -416,17 +422,20 @@ public:
   PRBool IsComplex () const { return mImpl.IsComplex (); }
   PRBool IsEqual (const nsIntRegion& aRegion) const
   {
     return mImpl.IsEqual (aRegion.mImpl);
   }
   PRUint32 GetNumRects () const { return mImpl.GetNumRects (); }
   nsIntRect GetBounds () const { return FromRect (mImpl.GetBounds ()); }
   nsRegion ToAppUnits (nscoord aAppUnitsPerPixel) const;
-  nsIntRect GetLargestRectangle () const { return FromRect (mImpl.GetLargestRectangle()); }
+  nsIntRect GetLargestRectangle (const nsIntRect& aContainingRect = nsIntRect()) const
+  {
+    return FromRect (mImpl.GetLargestRectangle( ToRect(aContainingRect) ));
+  }
 
   /**
    * Make sure the region has at most aMaxRects by adding area to it
    * if necessary. The simplified region will be a superset of the
    * original region. The simplified region's bounding box will be
    * the same as for the current region.
    */
   void SimplifyOutward (PRUint32 aMaxRects)
--- a/gfx/tests/TestRegion.cpp
+++ b/gfx/tests/TestRegion.cpp
@@ -126,28 +126,50 @@ class TestLargestRegion {
       nsRect largest = r2.GetLargestRectangle();
       if (largest.width * largest.height != tests[i].expectedArea) {
         fail("Did not succesfully find largest rectangle in two-rect-subtract region on iteration %d", i);
         success = PR_FALSE;
       }
     }
     return success;
   }
+  static PRBool TestContainsSpecifiedRect() {
+    nsRegion r(nsRect(0, 0, 100, 100));
+    r.Or(r, nsRect(0, 300, 50, 50));
+    if (r.GetLargestRectangle(nsRect(0, 300, 10, 10)) != nsRect(0, 300, 50, 50)) {
+      fail("Chose wrong rectangle");
+      return PR_FALSE;
+    }
+    return PR_TRUE;
+  }
+  static PRBool TestContainsSpecifiedOverflowingRect() {
+    nsRegion r(nsRect(0, 0, 100, 100));
+    r.Or(r, nsRect(0, 300, 50, 50));
+    if (r.GetLargestRectangle(nsRect(0, 290, 10, 20)) != nsRect(0, 300, 50, 50)) {
+      fail("Chose wrong rectangle");
+      return PR_FALSE;
+    }
+    return PR_TRUE;
+  }
 public:
   static PRBool Test() {
     if (!TestSingleRect(nsRect(0, 52, 720, 480)) ||
         !TestSingleRect(nsRect(-20, 40, 50, 20)) ||
         !TestSingleRect(nsRect(-20, 40, 10, 8)) ||
         !TestSingleRect(nsRect(-20, -40, 10, 8)) ||
         !TestSingleRect(nsRect(-10, -10, 20, 20)))
       return PR_FALSE;
     if (!TestNonRectangular())
       return PR_FALSE;
     if (!TwoRectTest())
       return PR_FALSE;
+    if (!TestContainsSpecifiedRect())
+      return PR_FALSE;
+    if (!TestContainsSpecifiedOverflowingRect())
+      return PR_FALSE;
     passed("TestLargestRegion");
     return PR_TRUE;
   }
 };
 
 int main(int argc, char** argv) {
   ScopedXPCOM xpcom("TestRegion");
   if (xpcom.failed())