diff options
Diffstat (limited to 'gfx/src/nsRegion.cpp')
| -rw-r--r-- | gfx/src/nsRegion.cpp | 1024 |
1 files changed, 1024 insertions, 0 deletions
diff --git a/gfx/src/nsRegion.cpp b/gfx/src/nsRegion.cpp new file mode 100644 index 0000000000..aa50d44fc4 --- /dev/null +++ b/gfx/src/nsRegion.cpp @@ -0,0 +1,1024 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "nsRegion.h" +#include "nsTArray.h" +#include "gfxUtils.h" +#include "gfx2DGlue.h" +#include "mozilla/ToString.h" + +void nsRegion::AssertStateInternal() const { + bool failed = false; + // Verify consistent state inside the region. + int32_t lastY = INT32_MIN; + int32_t lowestX = INT32_MAX; + int32_t highestX = INT32_MIN; + for (auto iter = mBands.begin(); iter != mBands.end(); iter++) { + const Band& band = *iter; + if (band.bottom <= band.top) { + failed = true; + break; + } + if (band.top < lastY) { + failed = true; + break; + } + lastY = band.bottom; + + lowestX = std::min(lowestX, band.mStrips.begin()->left); + highestX = std::max(highestX, band.mStrips.LastElement().right); + + int32_t lastX = INT32_MIN; + if (iter != mBands.begin()) { + auto prev = iter; + prev--; + + if (prev->bottom == iter->top) { + if (band.EqualStrips(*prev)) { + failed = true; + break; + } + } + } + for (const Strip& strip : band.mStrips) { + if (strip.right <= strip.left) { + failed = true; + break; + } + if (strip.left <= lastX) { + failed = true; + break; + } + lastX = strip.right; + } + if (failed) { + break; + } + } + + if (!(mBounds.IsEqualEdges(CalculateBounds()))) { + failed = true; + } + + if (failed) { +#ifdef DEBUG_REGIONS + if (mCurrentOpGenerator) { + mCurrentOpGenerator->OutputOp(); + } +#endif + MOZ_ASSERT(false); + } +} + +bool nsRegion::Contains(const nsRegion& aRgn) const { + // XXX this could be made faster by iterating over + // both regions at the same time some how + for (auto iter = aRgn.RectIter(); !iter.Done(); iter.Next()) { + if (!Contains(iter.Get())) { + return false; + } + } + return true; +} + +bool nsRegion::Intersects(const nsRectAbsolute& aRect) const { + if (mBands.IsEmpty()) { + return mBounds.Intersects(aRect); + } + + if (!mBounds.Intersects(aRect)) { + return false; + } + + Strip rectStrip(aRect.X(), aRect.XMost()); + + auto iter = mBands.begin(); + while (iter != mBands.end()) { + if (iter->top >= aRect.YMost()) { + return false; + } + + if (iter->bottom <= aRect.Y()) { + // This band is entirely before aRect, move on. + iter++; + continue; + } + + if (!iter->Intersects(rectStrip)) { + // This band does not intersect aRect horizontally. Move on. + iter++; + continue; + } + + // This band intersects with aRect. + return true; + } + + return false; +} + +void nsRegion::Inflate(const nsMargin& aMargin) { + nsRegion newRegion; + for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) { + nsRectAbsolute rect = iter.GetAbsolute(); + rect.Inflate(aMargin); + newRegion.AddRect(rect); + } + + *this = std::move(newRegion); +} + +void nsRegion::SimplifyOutward(uint32_t aMaxRects) { + MOZ_ASSERT(aMaxRects >= 1, "Invalid max rect count"); + + if (GetNumRects() <= aMaxRects) { + return; + } + + // Try combining rects in horizontal bands into a single rect + // The goal here is to try to keep groups of rectangles that are vertically + // discontiguous as separate rectangles in the final region. This is + // simple and fast to implement and page contents tend to vary more + // vertically than horizontally (which is why our rectangles are stored + // sorted by y-coordinate, too). + // + // Note: if boxes share y1 because of the canonical representation they + // will share y2 + + size_t idx = 0; + + while (idx < mBands.Length()) { + size_t oldIdx = idx; + mBands[idx].mStrips.begin()->right = + mBands[idx].mStrips.LastElement().right; + mBands[idx].mStrips.TruncateLength(1); + idx++; + + // Merge any bands with the same bounds. + while (idx < mBands.Length() && + mBands[idx].mStrips.begin()->left == + mBands[oldIdx].mStrips.begin()->left && + mBands[idx].mStrips.LastElement().right == + mBands[oldIdx].mStrips.begin()->right) { + mBands[oldIdx].bottom = mBands[idx].bottom; + mBands.RemoveElementAt(idx); + } + } + + AssertState(); + + // mBands.size() is now equal to our rect count. + if (mBands.Length() > aMaxRects) { + *this = GetBounds(); + } +} + +// compute the covered area difference between two rows. +// by iterating over both rows simultaneously and adding up +// the additional increase in area caused by extending each +// of the rectangles to the combined height of both rows +uint32_t nsRegion::ComputeMergedAreaIncrease(const Band& aTopBand, + const Band& aBottomBand) { + uint32_t totalArea = 0; + + uint32_t topHeight = aBottomBand.top - aTopBand.top; + uint32_t bottomHeight = aBottomBand.bottom - aTopBand.bottom; + uint32_t currentStripBottom = 0; + + // This could be done with slightly better worse case performance by merging + // these two for-loops, but this makes the code a lot easier to understand. + for (auto& strip : aTopBand.mStrips) { + if (currentStripBottom == aBottomBand.mStrips.Length() || + strip.right < aBottomBand.mStrips[currentStripBottom].left) { + totalArea += bottomHeight * strip.Size(); + continue; + } + + int32_t currentX = strip.left; + while (currentStripBottom != aBottomBand.mStrips.Length() && + aBottomBand.mStrips[currentStripBottom].left < strip.right) { + if (currentX >= strip.right) { + break; + } + if (currentX < aBottomBand.mStrips[currentStripBottom].left) { + // Add the part that's not intersecting. + totalArea += (aBottomBand.mStrips[currentStripBottom].left - currentX) * + bottomHeight; + } + + currentX = + std::max(aBottomBand.mStrips[currentStripBottom].right, currentX); + currentStripBottom++; + } + + // Add remainder of this strip. + if (currentX < strip.right) { + totalArea += (strip.right - currentX) * bottomHeight; + } + if (currentStripBottom) { + currentStripBottom--; + } + } + uint32_t currentStripTop = 0; + for (auto& strip : aBottomBand.mStrips) { + if (currentStripTop == aTopBand.mStrips.Length() || + strip.right < aTopBand.mStrips[currentStripTop].left) { + totalArea += topHeight * strip.Size(); + continue; + } + + int32_t currentX = strip.left; + while (currentStripTop != aTopBand.mStrips.Length() && + aTopBand.mStrips[currentStripTop].left < strip.right) { + if (currentX >= strip.right) { + break; + } + if (currentX < aTopBand.mStrips[currentStripTop].left) { + // Add the part that's not intersecting. + totalArea += + (aTopBand.mStrips[currentStripTop].left - currentX) * topHeight; + } + + currentX = std::max(aTopBand.mStrips[currentStripTop].right, currentX); + currentStripTop++; + } + + // Add remainder of this strip. + if (currentX < strip.right) { + totalArea += (strip.right - currentX) * topHeight; + } + if (currentStripTop) { + currentStripTop--; + } + } + return totalArea; +} + +void nsRegion::SimplifyOutwardByArea(uint32_t aThreshold) { + if (mBands.Length() < 2) { + // We have only one or no row and we're done. + return; + } + + uint32_t currentBand = 0; + do { + Band& band = mBands[currentBand]; + + uint32_t totalArea = + ComputeMergedAreaIncrease(band, mBands[currentBand + 1]); + + if (totalArea <= aThreshold) { + for (Strip& strip : mBands[currentBand + 1].mStrips) { + // This could use an optimized function to merge two bands. + band.InsertStrip(strip); + } + band.bottom = mBands[currentBand + 1].bottom; + mBands.RemoveElementAt(currentBand + 1); + } else { + currentBand++; + } + } while (currentBand + 1 < mBands.Length()); + + EnsureSimplified(); + AssertState(); +} + +typedef void (*visit_fn)(void* closure, VisitSide side, int x1, int y1, int x2, + int y2); + +void nsRegion::VisitEdges(visit_fn visit, void* closure) const { + if (mBands.IsEmpty()) { + visit(closure, VisitSide::LEFT, mBounds.X(), mBounds.Y(), mBounds.X(), + mBounds.YMost()); + visit(closure, VisitSide::RIGHT, mBounds.XMost(), mBounds.Y(), + mBounds.XMost(), mBounds.YMost()); + visit(closure, VisitSide::TOP, mBounds.X() - 1, mBounds.Y(), + mBounds.XMost() + 1, mBounds.Y()); + visit(closure, VisitSide::BOTTOM, mBounds.X() - 1, mBounds.YMost(), + mBounds.XMost() + 1, mBounds.YMost()); + return; + } + + auto band = std::begin(mBands); + auto bandFinal = std::end(mBands); + bandFinal--; + for (const Strip& strip : band->mStrips) { + visit(closure, VisitSide::LEFT, strip.left, band->top, strip.left, + band->bottom); + visit(closure, VisitSide::RIGHT, strip.right, band->top, strip.right, + band->bottom); + visit(closure, VisitSide::TOP, strip.left - 1, band->top, strip.right + 1, + band->top); + } + + if (band != bandFinal) { + do { + const Band& topBand = *band; + band++; + + for (const Strip& strip : band->mStrips) { + visit(closure, VisitSide::LEFT, strip.left, band->top, strip.left, + band->bottom); + visit(closure, VisitSide::RIGHT, strip.right, band->top, strip.right, + band->bottom); + } + + if (band->top == topBand.bottom) { + // Two bands touching each other vertically. + const Band& bottomBand = *band; + auto topStrip = std::begin(topBand.mStrips); + auto bottomStrip = std::begin(bottomBand.mStrips); + + int y = topBand.bottom; + + // State from this point on along the vertical edge: + // 0 - Empty + // 1 - Touched by top rect + // 2 - Touched by bottom rect + // 3 - Touched on both sides + int state; + const int TouchedByNothing = 0; + const int TouchedByTop = 1; + const int TouchedByBottom = 2; + // We always start with nothing. + int oldState = TouchedByNothing; + // Last state change, adjusted by -1 if the last state change was + // a change away from 0. + int lastX = std::min(topStrip->left, bottomStrip->left) - 1; + + // Current edge being considered for top and bottom, + // 0 - left, 1 - right. + bool topEdgeIsLeft = true; + bool bottomEdgeIsLeft = true; + while (topStrip != std::end(topBand.mStrips) && + bottomStrip != std::end(bottomBand.mStrips)) { + int topPos; + int bottomPos; + if (topEdgeIsLeft) { + topPos = topStrip->left; + } else { + topPos = topStrip->right; + } + if (bottomEdgeIsLeft) { + bottomPos = bottomStrip->left; + } else { + bottomPos = bottomStrip->right; + } + + int currentX = std::min(topPos, bottomPos); + if (topPos < bottomPos) { + if (topEdgeIsLeft) { + state = oldState | TouchedByTop; + } else { + state = oldState ^ TouchedByTop; + topStrip++; + } + topEdgeIsLeft = !topEdgeIsLeft; + } else if (bottomPos < topPos) { + if (bottomEdgeIsLeft) { + state = oldState | TouchedByBottom; + } else { + state = oldState ^ TouchedByBottom; + bottomStrip++; + } + bottomEdgeIsLeft = !bottomEdgeIsLeft; + } else { + // bottomPos == topPos + state = TouchedByNothing; + if (bottomEdgeIsLeft) { + state = TouchedByBottom; + } else { + bottomStrip++; + } + if (topEdgeIsLeft) { + state |= TouchedByTop; + } else { + topStrip++; + } + topEdgeIsLeft = !topEdgeIsLeft; + bottomEdgeIsLeft = !bottomEdgeIsLeft; + } + + MOZ_ASSERT(state != oldState); + if (oldState == TouchedByNothing) { + // We had nothing before, make sure the left edge will be padded. + lastX = currentX - 1; + } else if (oldState == TouchedByTop) { + if (state == TouchedByNothing) { + visit(closure, VisitSide::BOTTOM, lastX, y, currentX + 1, y); + } else { + visit(closure, VisitSide::BOTTOM, lastX, y, currentX, y); + lastX = currentX; + } + } else if (oldState == TouchedByBottom) { + if (state == TouchedByNothing) { + visit(closure, VisitSide::TOP, lastX, y, currentX + 1, y); + } else { + visit(closure, VisitSide::TOP, lastX, y, currentX, y); + lastX = currentX; + } + } else { + lastX = currentX; + } + oldState = state; + } + + MOZ_ASSERT(!state || (topEdgeIsLeft || bottomEdgeIsLeft)); + if (topStrip != std::end(topBand.mStrips)) { + if (!topEdgeIsLeft) { + visit(closure, VisitSide::BOTTOM, lastX, y, topStrip->right + 1, y); + topStrip++; + } + while (topStrip != std::end(topBand.mStrips)) { + visit(closure, VisitSide::BOTTOM, topStrip->left - 1, y, + topStrip->right + 1, y); + topStrip++; + } + } else if (bottomStrip != std::end(bottomBand.mStrips)) { + if (!bottomEdgeIsLeft) { + visit(closure, VisitSide::TOP, lastX, y, bottomStrip->right + 1, y); + bottomStrip++; + } + while (bottomStrip != std::end(bottomBand.mStrips)) { + visit(closure, VisitSide::TOP, bottomStrip->left - 1, y, + bottomStrip->right + 1, y); + bottomStrip++; + } + } + } else { + for (const Strip& strip : topBand.mStrips) { + visit(closure, VisitSide::BOTTOM, strip.left - 1, topBand.bottom, + strip.right + 1, topBand.bottom); + } + for (const Strip& strip : band->mStrips) { + visit(closure, VisitSide::TOP, strip.left - 1, band->top, + strip.right + 1, band->top); + } + } + } while (band != bandFinal); + } + + for (const Strip& strip : band->mStrips) { + visit(closure, VisitSide::BOTTOM, strip.left - 1, band->bottom, + strip.right + 1, band->bottom); + } +} + +void nsRegion::SimplifyInward(uint32_t aMaxRects) { + NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count"); + + if (GetNumRects() <= aMaxRects) return; + + SetEmpty(); +} + +uint64_t nsRegion::Area() const { + if (mBands.IsEmpty()) { + return mBounds.Area(); + } + + uint64_t area = 0; + for (const Band& band : mBands) { + uint32_t height = band.bottom - band.top; + for (const Strip& strip : band.mStrips) { + area += (strip.right - strip.left) * height; + } + } + + return area; +} + +nsRegion& nsRegion::ScaleRoundOut(float aXScale, float aYScale) { + if (mozilla::gfx::FuzzyEqual(aXScale, 1.0f) && + mozilla::gfx::FuzzyEqual(aYScale, 1.0f)) { + return *this; + } + + nsRegion newRegion; + for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) { + nsRectAbsolute rect = iter.GetAbsolute(); + rect.ScaleRoundOut(aXScale, aYScale); + newRegion.AddRect(rect); + } + + *this = std::move(newRegion); + return *this; +} + +nsRegion& nsRegion::ScaleInverseRoundOut(float aXScale, float aYScale) { + nsRegion newRegion; + for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) { + nsRectAbsolute rect = iter.GetAbsolute(); + rect.ScaleInverseRoundOut(aXScale, aYScale); + newRegion.AddRect(rect); + } + + *this = std::move(newRegion); + return *this; +} + +static mozilla::gfx::IntRect TransformRect( + const mozilla::gfx::IntRect& aRect, + const mozilla::gfx::Matrix4x4& aTransform) { + if (aRect.IsEmpty()) { + return mozilla::gfx::IntRect(); + } + + mozilla::gfx::RectDouble rect(aRect.X(), aRect.Y(), aRect.Width(), + aRect.Height()); + rect = aTransform.TransformAndClipBounds( + rect, mozilla::gfx::RectDouble::MaxIntRect()); + rect.RoundOut(); + + mozilla::gfx::IntRect intRect; + if (!gfxUtils::GfxRectToIntRect(ThebesRect(rect), &intRect)) { + return mozilla::gfx::IntRect(); + } + + return intRect; +} + +nsRegion& nsRegion::Transform(const mozilla::gfx::Matrix4x4& aTransform) { + nsRegion newRegion; + for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) { + nsRect rect = nsIntRegion::ToRect( + TransformRect(nsIntRegion::FromRect(iter.Get()), aTransform)); + newRegion.AddRect(nsRectAbsolute::FromRect(rect)); + } + + *this = std::move(newRegion); + return *this; +} + +nsRegion nsRegion::ScaleToOtherAppUnitsRoundOut(int32_t aFromAPP, + int32_t aToAPP) const { + if (aFromAPP == aToAPP) { + return *this; + } + nsRegion newRegion; + for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) { + nsRect rect = iter.Get(); + rect = rect.ScaleToOtherAppUnitsRoundOut(aFromAPP, aToAPP); + newRegion.AddRect(nsRectAbsolute::FromRect(rect)); + } + + return newRegion; +} + +nsRegion nsRegion::ScaleToOtherAppUnitsRoundIn(int32_t aFromAPP, + int32_t aToAPP) const { + if (aFromAPP == aToAPP) { + return *this; + } + + nsRegion newRegion; + for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) { + nsRect rect = iter.Get(); + rect = rect.ScaleToOtherAppUnitsRoundIn(aFromAPP, aToAPP); + newRegion.AddRect(nsRectAbsolute::FromRect(rect)); + } + + return newRegion; +} + +nsIntRegion nsRegion::ToPixels(nscoord aAppUnitsPerPixel, + bool aOutsidePixels) const { + nsIntRegion intRegion; + for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) { + mozilla::gfx::IntRect deviceRect; + nsRect rect = iter.Get(); + if (aOutsidePixels) + deviceRect = rect.ToOutsidePixels(aAppUnitsPerPixel); + else + deviceRect = rect.ToNearestPixels(aAppUnitsPerPixel); + intRegion.OrWith(deviceRect); + } + + return intRegion; +} + +nsIntRegion nsRegion::ToOutsidePixels(nscoord aAppUnitsPerPixel) const { + return ToPixels(aAppUnitsPerPixel, true); +} + +nsIntRegion nsRegion::ToNearestPixels(nscoord aAppUnitsPerPixel) const { + return ToPixels(aAppUnitsPerPixel, false); +} + +nsIntRegion nsRegion::ScaleToNearestPixels(float aScaleX, float aScaleY, + nscoord aAppUnitsPerPixel) const { + nsIntRegion result; + for (auto iter = RectIter(); !iter.Done(); iter.Next()) { + mozilla::gfx::IntRect deviceRect = + iter.Get().ScaleToNearestPixels(aScaleX, aScaleY, aAppUnitsPerPixel); + result.Or(result, deviceRect); + } + return result; +} + +nsIntRegion nsRegion::ScaleToOutsidePixels(float aScaleX, float aScaleY, + nscoord aAppUnitsPerPixel) const { + // make a copy of the region so that we can mutate it inplace + nsIntRegion intRegion; + for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) { + nsRect rect = iter.Get(); + intRegion.OrWith( + rect.ScaleToOutsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel)); + } + return intRegion; +} + +nsIntRegion nsRegion::ScaleToInsidePixels(float aScaleX, float aScaleY, + nscoord aAppUnitsPerPixel) const { + /* When scaling a rect, walk forward through the rect list up until the y + * value is greater than the current rect's YMost() value. + * + * For each rect found, check if the rects have a touching edge (in unscaled + * coordinates), and if one edge is entirely contained within the other. + * + * If it is, then the contained edge can be moved (in scaled pixels) to ensure + * that no gap exists. + * + * Since this could be potentially expensive - O(n^2), we only attempt this + * algorithm for the first rect. + */ + + if (mBands.IsEmpty()) { + nsIntRect rect = mBounds.ToNSRect().ScaleToInsidePixels(aScaleX, aScaleY, + aAppUnitsPerPixel); + return nsIntRegion(rect); + } + + nsIntRegion intRegion; + RectIterator iter = RectIterator(*this); + + nsRect first = iter.Get(); + + mozilla::gfx::IntRect firstDeviceRect = + first.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel); + + for (iter.Next(); !iter.Done(); iter.Next()) { + nsRect rect = iter.Get(); + mozilla::gfx::IntRect deviceRect = + rect.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel); + + if (rect.Y() <= first.YMost()) { + if (rect.XMost() == first.X() && rect.YMost() <= first.YMost()) { + // rect is touching on the left edge of the first rect and contained + // within the length of its left edge + deviceRect.SetRightEdge(firstDeviceRect.X()); + } else if (rect.X() == first.XMost() && rect.YMost() <= first.YMost()) { + // rect is touching on the right edge of the first rect and contained + // within the length of its right edge + deviceRect.SetLeftEdge(firstDeviceRect.XMost()); + } else if (rect.Y() == first.YMost()) { + // The bottom of the first rect is on the same line as the top of rect, + // but they aren't necessarily contained. + if (rect.X() <= first.X() && rect.XMost() >= first.XMost()) { + // The top of rect contains the bottom of the first rect + firstDeviceRect.SetBottomEdge(deviceRect.Y()); + } else if (rect.X() >= first.X() && rect.XMost() <= first.XMost()) { + // The bottom of the first contains the top of rect + deviceRect.SetTopEdge(firstDeviceRect.YMost()); + } + } + } + + intRegion.OrWith(deviceRect); + } + + intRegion.OrWith(firstDeviceRect); + return intRegion; +} + +// 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 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. +// +// Step 1 is O(k) in time and O(m+n) in space for the sparse grid. +// Step 2 is O(mn) in time and O(mn) in additional space for the full grid. +// Step 3 is O(m^2 n) in time and O(mn) in additional space +// +// The implementation of steps 1 and 2 are rather straightforward. However our +// implementation of step 3 uses dynamic programming to achieve its efficiency. +// +// Psuedo code for step 3 is as follows where G is the grid from step 1 and A +// is the array from step 2: +// 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 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) +// if (area > maxRect.area) { +// maxRect := (m', m'', l, r, area) +// } +// } +// +// return maxRect; +// } +// +// Originally taken from Improved algorithms for the k-maximum subarray problem +// for small k - SE Bae, T Takaoka but modified to show the explicit tracking +// of indices and we already have the prefix sums from our one call site so +// there's no need to construct them. +// MaxSum1D = function (A,n) { +// var minIdx = 0; +// var min = 0; +// var maxIndices = (0,0); +// var max = 0; +// for i in range(n) { +// let cand = A[i] - min; +// if (cand > max) { +// max := cand; +// maxIndices := (minIdx, i) +// } +// if (min > A[i]) { +// min := A[i]; +// minIdx := i; +// } +// } +// return (minIdx, maxIdx, max); +// } + +namespace { +// This class represents a partitioning of an axis delineated by coordinates. +// It internally maintains a sorted array of coordinates. +class AxisPartition { + public: + // Adds a new partition at the given coordinate to this partitioning. If + // the coordinate is already present in the partitioning, this does nothing. + void InsertCoord(nscoord c) { + uint32_t i = mStops.IndexOfFirstElementGt(c); + if (i == 0 || mStops[i - 1] != c) { + mStops.InsertElementAt(i, c); + } + } + + // Returns the array index of the given partition point. The partition + // point must already be present in the partitioning. + int32_t IndexOf(nscoord p) const { return mStops.BinaryIndexOf(p); } + + // Returns the partition at the given index which must be non-zero and + // less than the number of partitions in this partitioning. + nscoord StopAt(int32_t index) const { return mStops[index]; } + + // Returns the size of the gap between the partition at the given index and + // the next partition in this partitioning. If the index is the last index + // in the partitioning, the result is undefined. + nscoord StopSize(int32_t index) const { + return mStops[index + 1] - mStops[index]; + } + + // Returns the number of partitions in this partitioning. + int32_t GetNumStops() const { return mStops.Length(); } + + private: + nsTArray<nscoord> mStops; +}; + +const int64_t kVeryLargeNegativeNumber = 0xffff000000000000ll; + +struct SizePair { + int64_t mSizeContainingRect; + int64_t mSize; + + SizePair() : mSizeContainingRect(0), mSize(0) {} + + static SizePair VeryLargeNegative() { + SizePair result; + result.mSize = result.mSizeContainingRect = kVeryLargeNegativeNumber; + return result; + } + bool operator<(const SizePair& aOther) const { + if (mSizeContainingRect < aOther.mSizeContainingRect) return true; + if (mSizeContainingRect > aOther.mSizeContainingRect) return false; + return mSize < aOther.mSize; + } + bool 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. +SizePair MaxSum1D(const nsTArray<SizePair>& A, int32_t n, int32_t* minIdx, + int32_t* maxIdx) { + // The min/max indicies of the largest subarray found so far + SizePair min, max; + int32_t currentMinIdx = 0; + + *minIdx = 0; + *maxIdx = 0; + + // Because we're given the array in prefix sum form, we know the first + // element is 0 + for (int32_t i = 1; i < n; i++) { + 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; +} +} // namespace + +nsRect nsRegion::GetLargestRectangle(const nsRect& aContainingRect) const { + nsRect bestRect; + + if (GetNumRects() <= 1) { + bestRect = GetBounds(); + return bestRect; + } + + AxisPartition xaxis, yaxis; + + // Step 1: Calculate the grid lines + for (auto iter = RectIter(); !iter.Done(); iter.Next()) { + const nsRect& rect = iter.Get(); + xaxis.InsertCoord(rect.X()); + xaxis.InsertCoord(rect.XMost()); + yaxis.InsertCoord(rect.Y()); + yaxis.InsertCoord(rect.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. + int32_t matrixHeight = yaxis.GetNumStops() - 1; + int32_t matrixWidth = xaxis.GetNumStops() - 1; + int32_t matrixSize = matrixHeight * matrixWidth; + nsTArray<SizePair> areas(matrixSize); + areas.SetLength(matrixSize); + + for (auto iter = RectIter(); !iter.Done(); iter.Next()) { + const nsRect& rect = iter.Get(); + int32_t xstart = xaxis.IndexOf(rect.X()); + int32_t xend = xaxis.IndexOf(rect.XMost()); + int32_t y = yaxis.IndexOf(rect.Y()); + int32_t yend = yaxis.IndexOf(rect.YMost()); + + for (; y < yend; y++) { + nscoord height = yaxis.StopSize(y); + for (int32_t x = xstart; x < xend; x++) { + nscoord width = xaxis.StopSize(x); + int64_t size = width * int64_t(height); + if (rect.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 + int32_t m = matrixHeight + 1; + int32_t n = matrixWidth + 1; + nsTArray<SizePair> pareas(m * n); + pareas.SetLength(m * n); + for (int32_t y = 1; y < m; y++) { + for (int32_t x = 1; x < n; x++) { + 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); + + SizePair bestArea; + struct { + int32_t left, top, right, bottom; + } bestRectIndices = {0, 0, 0, 0}; + for (int32_t m1 = 0; m1 < m; m1++) { + for (int32_t m2 = m1 + 1; m2 < m; m2++) { + nsTArray<SizePair> B; + B.SetLength(n); + for (int32_t i = 0; i < n; i++) { + B[i] = pareas[m2 * n + i] - pareas[m1 * n + i]; + } + int32_t 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; + } + } + } + + bestRect.MoveTo(xaxis.StopAt(bestRectIndices.left), + yaxis.StopAt(bestRectIndices.top)); + bestRect.SizeTo(xaxis.StopAt(bestRectIndices.right) - bestRect.X(), + yaxis.StopAt(bestRectIndices.bottom) - bestRect.Y()); + } + + return bestRect; +} + +std::ostream& operator<<(std::ostream& stream, const nsRegion& m) { + stream << "["; + + bool first = true; + for (auto iter = m.RectIter(); !iter.Done(); iter.Next()) { + if (!first) { + stream << "; "; + } else { + first = false; + } + const nsRect& rect = iter.Get(); + stream << rect.X() << "," << rect.Y() << "," << rect.XMost() << "," + << rect.YMost(); + } + + stream << "]"; + return stream; +} + +void nsRegion::OutputToStream(std::string aObjName, + std::ostream& stream) const { + auto iter = RectIter(); + nsRect r = iter.Get(); + stream << "nsRegion " << aObjName << "(nsRect(" << r.X() << ", " << r.Y() + << ", " << r.Width() << ", " << r.Height() << "));\n"; + iter.Next(); + + for (; !iter.Done(); iter.Next()) { + nsRect r = iter.Get(); + stream << aObjName << ".OrWith(nsRect(" << r.X() << ", " << r.Y() << ", " + << r.Width() << ", " << r.Height() << "));\n"; + } +} + +nsCString nsRegion::ToString() const { + return nsCString(mozilla::ToString(*this).c_str()); +} |