Optimized DesktopRegion implementation.
Now DestktopRegion can merge overlapping rectangles.
R=wez@chromium.org
Review URL: https://webrtc-codereview.appspot.com/1526004
git-svn-id: http://webrtc.googlecode.com/svn/trunk@4161 4adac7df-926f-26a2-2b94-8c16560cd09d
diff --git a/webrtc/modules/desktop_capture/desktop_capture.gypi b/webrtc/modules/desktop_capture/desktop_capture.gypi
index 8ff238b..a9fdac6 100644
--- a/webrtc/modules/desktop_capture/desktop_capture.gypi
+++ b/webrtc/modules/desktop_capture/desktop_capture.gypi
@@ -59,6 +59,7 @@
'<(DEPTH)/testing/gtest.gyp:gtest',
],
'sources': [
+ "desktop_region_unittest.cc",
"window_capturer_unittest.cc",
],
},
diff --git a/webrtc/modules/desktop_capture/desktop_region.cc b/webrtc/modules/desktop_capture/desktop_region.cc
index 71398b3..8ba6c64 100644
--- a/webrtc/modules/desktop_capture/desktop_region.cc
+++ b/webrtc/modules/desktop_capture/desktop_region.cc
@@ -10,18 +10,70 @@
#include "webrtc/modules/desktop_capture/desktop_region.h"
+#include <algorithm>
+#include <cassert>
+
namespace webrtc {
+DesktopRegion::RowSpan::RowSpan(int32_t left, int32_t right)
+ : left(left), right(right) {
+}
+
+DesktopRegion::Row::Row(int32_t top, int32_t bottom)
+ : top(top), bottom(bottom) {
+}
+
DesktopRegion::DesktopRegion() {}
-DesktopRegion::DesktopRegion(const DesktopRegion& other)
- : rects_(other.rects_) {
+DesktopRegion::DesktopRegion(const DesktopRect& rect) {
+ AddRect(rect);
}
-DesktopRegion::~DesktopRegion() {}
+DesktopRegion::DesktopRegion(const DesktopRect* rects, int count) {
+ AddRects(rects, count);
+}
+
+DesktopRegion::DesktopRegion(const DesktopRegion& other) {
+ *this = other;
+}
+
+DesktopRegion::~DesktopRegion() {
+ Clear();
+}
+
+DesktopRegion& DesktopRegion::operator=(const DesktopRegion& other) {
+ rows_ = other.rows_;
+ for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) {
+ // Copy each row.
+ Row* row = it->second;
+ it->second = new Row(*row);
+ }
+ return *this;
+}
+
+bool DesktopRegion::Equals(const DesktopRegion& region) const {
+ // Iterate over rows of the tow regions and compare each row.
+ Rows::const_iterator it1 = rows_.begin();
+ Rows::const_iterator it2 = region.rows_.begin();
+ while (it1 != rows_.end()) {
+ if (it2 == region.rows_.end() ||
+ it1->first != it2->first ||
+ it1->second->top != it2->second->top ||
+ it1->second->bottom != it2->second->bottom ||
+ it1->second->spans != it2->second->spans) {
+ return false;
+ }
+ ++it1;
+ ++it2;
+ }
+ return it2 == region.rows_.end();
+}
void DesktopRegion::Clear() {
- rects_.clear();
+ for (Rows::iterator row = rows_.begin(); row != rows_.end(); ++row) {
+ delete row->second;
+ }
+ rows_.clear();
}
void DesktopRegion::SetRect(const DesktopRect& rect) {
@@ -30,55 +82,352 @@
}
void DesktopRegion::AddRect(const DesktopRect& rect) {
- if (!rect.is_empty())
- rects_.push_back(rect);
+ if (rect.is_empty())
+ return;
+
+ // Top of the part of the |rect| that hasn't been inserted yet. Increased as
+ // we iterate over the rows until it reaches |rect.bottom()|.
+ int top = rect.top();
+
+ // Iterate over all rows that may intersect with |rect| and add new rows when
+ // necessary.
+ Rows::iterator row = rows_.upper_bound(top);
+ while (top < rect.bottom()) {
+ if (row == rows_.end() || top < row->second->top) {
+ // If |top| is above the top of the current |row| then add a new row above
+ // the current one.
+ int32_t bottom = rect.bottom();
+ if (row != rows_.end() && row->second->top < bottom)
+ bottom = row->second->top;
+ row = rows_.insert(
+ row, Rows::value_type(bottom, new Row(top, bottom)));
+ } else if (top > row->second->top) {
+ // If the |top| falls in the middle of the |row| then split |row| into
+ // two, at |top|, and leave |row| referring to the lower of of the two,
+ // ready to insert a new span into.
+ assert(top <= row->second->bottom);
+ Rows::iterator new_row = rows_.insert(
+ row, Rows::value_type(top, new Row(row->second->top, top)));
+ row->second->top = top;
+ new_row->second->spans = row->second->spans;
+ }
+
+ if (rect.bottom() < row->second->bottom) {
+ // If the bottom of the |rect| falls in the middle of the |row| split
+ // |row| into two, at |top|, and leave |row| referring to the upper of
+ // the two, ready to insert a new span into.
+ Rows::iterator new_row = rows_.insert(
+ row, Rows::value_type(rect.bottom(), new Row(top, rect.bottom())));
+ row->second->top = rect.bottom();
+ new_row->second->spans = row->second->spans;
+ row = new_row;
+ }
+
+ // Add a new span to the current row.
+ AddSpanToRow(row->second, rect.left(), rect.right());
+ top = row->second->bottom;
+
+ MergeWithPrecedingRow(row);
+
+ // Move to the next row.
+ row++;
+ }
+
+ if (row != rows_.end())
+ MergeWithPrecedingRow(row);
+}
+
+void DesktopRegion::AddRects(const DesktopRect* rects, int count) {
+ for (int i = 0; i < count; ++i) {
+ AddRect(rects[i]);
+ }
+}
+
+void DesktopRegion::MergeWithPrecedingRow(Rows::iterator row) {
+ assert(row != rows_.end());
+
+ if (row != rows_.begin()) {
+ Rows::iterator previous_row = row;
+ previous_row--;
+
+ // If |row| and |previous_row| are next to each other and contain the same
+ // set of spans then they can be merged.
+ if (previous_row->second->bottom == row->second->top &&
+ previous_row->second->spans == row->second->spans) {
+ row->second->top = previous_row->second->top;
+ delete previous_row->second;
+ rows_.erase(previous_row);
+ }
+ }
}
void DesktopRegion::AddRegion(const DesktopRegion& region) {
+ // TODO(sergeyu): This function is not optimized - potentially it can iterate
+ // over rows of the two regions similar to how it works in Intersect().
for (Iterator it(region); !it.IsAtEnd(); it.Advance()) {
AddRect(it.rect());
}
}
-void DesktopRegion::IntersectWith(const DesktopRect& rect) {
- bool remove_empty_rects = false;
- for (RectsList::iterator it = rects_.begin(); it != rects_.end(); ++it) {
- it->IntersectWith(rect);
- remove_empty_rects = remove_empty_rects | it->is_empty();
- }
- if (remove_empty_rects) {
- RectsList new_rects;
- new_rects.reserve(rects_.size());
- for (RectsList::iterator it = rects_.begin(); it != rects_.end(); ++it) {
- if (!it->is_empty())
- new_rects.push_back(*it);
+void DesktopRegion::Intersect(const DesktopRegion& region1,
+ const DesktopRegion& region2) {
+ Clear();
+
+ Rows::const_iterator it1 = region1.rows_.begin();
+ Rows::const_iterator end1 = region1.rows_.end();
+ Rows::const_iterator it2 = region2.rows_.begin();
+ Rows::const_iterator end2 = region2.rows_.end();
+ if (it1 == end1 || it2 == end2)
+ return;
+
+ while (it1 != end1 && it2 != end2) {
+ // Arrange for |it1| to always be the top-most of the rows.
+ if (it2->second->top < it1->second->top) {
+ std::swap(it1, it2);
+ std::swap(end1, end2);
}
- rects_.swap(new_rects);
+
+ // Skip |it1| if it doesn't intersect |it2| at all.
+ if (it1->second->bottom <= it2->second->top) {
+ ++it1;
+ continue;
+ }
+
+ // Top of the |it1| row is above the top of |it2|, so top of the
+ // intersection is always the top of |it2|.
+ int32_t top = it2->second->top;
+ int32_t bottom = std::min(it1->second->bottom, it2->second->bottom);
+
+ Rows::iterator new_row = rows_.insert(
+ rows_.end(), Rows::value_type(bottom, new Row(top, bottom)));
+ IntersectRows(it1->second->spans, it2->second->spans,
+ &new_row->second->spans);
+ if (new_row->second->spans.empty()) {
+ delete new_row->second;
+ rows_.erase(new_row);
+ }
+
+ MergeWithPrecedingRow(new_row);
+
+ // If |it1| was completely consumed, move to the next one.
+ if (it1->second->bottom == bottom)
+ ++it1;
+ // If |it2| was completely consumed, move to the next one.
+ if (it2->second->bottom == bottom)
+ ++it2;
}
}
+// static
+void DesktopRegion::IntersectRows(const RowSpanSet& set1,
+ const RowSpanSet& set2,
+ RowSpanSet* output) {
+ RowSpanSet::const_iterator it1 = set1.begin();
+ RowSpanSet::const_iterator end1 = set1.end();
+ RowSpanSet::const_iterator it2 = set2.begin();
+ RowSpanSet::const_iterator end2 = set2.end();
+ assert(it1 != end1 && it2 != end2);
+
+ do {
+ // Arrange for |it1| to always be the left-most of the spans.
+ if (it2->left < it1->left) {
+ std::swap(it1, it2);
+ std::swap(end1, end2);
+ }
+
+ // Skip |it1| if it doesn't intersect |it2| at all.
+ if (it1->right <= it2->left) {
+ ++it1;
+ continue;
+ }
+
+ int32_t left = it2->left;
+ int32_t right = std::min(it1->right, it2->right);
+ assert(left < right);
+
+ output->push_back(RowSpan(left, right));
+
+ // If |it1| was completely consumed, move to the next one.
+ if (it1->right == right)
+ ++it1;
+ // If |it2| was completely consumed, move to the next one.
+ if (it2->right == right)
+ ++it2;
+ } while (it1 != end1 && it2 != end2);
+}
+
+void DesktopRegion::IntersectWith(const DesktopRegion& region) {
+ DesktopRegion old_region;
+ Swap(&old_region);
+ Intersect(old_region, region);
+}
+
+void DesktopRegion::IntersectWith(const DesktopRect& rect) {
+ DesktopRegion region;
+ region.AddRect(rect);
+ IntersectWith(region);
+}
+
void DesktopRegion::Translate(int32_t dx, int32_t dy) {
- for (RectsList::iterator it = rects_.begin(); it != rects_.end(); ++it) {
- it->Translate(dx, dy);
+ Rows new_rows;
+
+ for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) {
+ Row* row = it->second;
+
+ row->top += dy;
+ row->bottom += dy;
+
+ if (dx != 0) {
+ // Translate each span.
+ for (RowSpanSet::iterator span = row->spans.begin();
+ span != row->spans.end(); ++span) {
+ span->left += dx;
+ span->right += dx;
+ }
+ }
+
+ if (dy != 0)
+ new_rows.insert(new_rows.end(), Rows::value_type(row->bottom, row));
}
+
+ if (dy != 0)
+ new_rows.swap(rows_);
}
void DesktopRegion::Swap(DesktopRegion* region) {
- rects_.swap(region->rects_);
+ rows_.swap(region->rows_);
+}
+
+// static
+bool DesktopRegion::CompareSpanRight(const RowSpan& r, int32_t value) {
+ return r.right < value;
+}
+
+// static
+bool DesktopRegion::CompareSpanLeft(const RowSpan& r, int32_t value) {
+ return r.left < value;
+}
+
+// static
+void DesktopRegion::AddSpanToRow(Row* row, int left, int right) {
+ // First check if the new span is located to the right of all existing spans.
+ // This is an optimization to avoid binary search in the case when rectangles
+ // are inserted sequentially from left to right.
+ if (row->spans.empty() || left > row->spans.back().right) {
+ row->spans.push_back(RowSpan(left, right));
+ return;
+ }
+
+ // Find the first span that ends at or after |left|.
+ RowSpanSet::iterator start =
+ std::lower_bound(row->spans.begin(), row->spans.end(), left,
+ CompareSpanRight);
+ assert(start < row->spans.end());
+
+ // Find the first span that starts after |right|.
+ RowSpanSet::iterator end =
+ std::lower_bound(start, row->spans.end(), right + 1, CompareSpanLeft);
+ if (end == row->spans.begin()) {
+ // There are no overlaps. Just insert the new span at the beginning.
+ row->spans.insert(row->spans.begin(), RowSpan(left, right));
+ return;
+ }
+
+ // Move end to the left, so that it points the last span that ends at or
+ // before |right|.
+ end--;
+
+ // At this point [start, end] is the range of spans that intersect with the
+ // new one.
+ if (end < start) {
+ // There are no overlaps. Just insert the new span at the correct position.
+ row->spans.insert(start, RowSpan(left, right));
+ return;
+ }
+
+ left = std::min(left, start->left);
+ right = std::max(right, end->right);
+
+ // Replace range [start, end] with the new span.
+ *start = RowSpan(left, right);
+ ++start;
+ ++end;
+ if (start < end)
+ row->spans.erase(start, end);
+}
+
+// static
+bool DesktopRegion::IsSpanInRow(const Row& row, const RowSpan& span) {
+ // Find the first span that starts at or after |span.left| and then check if
+ // it's the same span.
+ RowSpanSet::const_iterator it =
+ std::lower_bound(row.spans.begin(), row.spans.end(), span.left,
+ CompareSpanLeft);
+ return it != row.spans.end() && *it == span;
}
DesktopRegion::Iterator::Iterator(const DesktopRegion& region)
: region_(region),
- it_(region.rects_.begin()) {
+ row_(region.rows_.begin()),
+ previous_row_(region.rows_.end()) {
+ if (!IsAtEnd()) {
+ assert(row_->second->spans.size() > 0);
+ row_span_ = row_->second->spans.begin();
+ UpdateCurrentRect();
+ }
}
bool DesktopRegion::Iterator::IsAtEnd() const {
- return it_ == region_.rects_.end();
+ return row_ == region_.rows_.end();
}
void DesktopRegion::Iterator::Advance() {
- ++it_;
+ assert(!IsAtEnd());
+
+ while (true) {
+ ++row_span_;
+ if (row_span_ == row_->second->spans.end()) {
+ previous_row_ = row_;
+ ++row_;
+ if (row_ != region_.rows_.end()) {
+ assert(row_->second->spans.size() > 0);
+ row_span_ = row_->second->spans.begin();
+ }
+ }
+
+ if (IsAtEnd())
+ return;
+
+ // If the same span exists on the previous row then skip it, as we've
+ // already returned this span merged into the previous one, via
+ // UpdateCurrentRect().
+ if (previous_row_ != region_.rows_.end() &&
+ previous_row_->second->bottom == row_->second->top &&
+ IsSpanInRow(*previous_row_->second, *row_span_)) {
+ continue;
+ }
+
+ break;
+ }
+
+ assert(!IsAtEnd());
+ UpdateCurrentRect();
+}
+
+void DesktopRegion::Iterator::UpdateCurrentRect() {
+ // Merge the current rectangle with the matching spans from later rows.
+ int bottom;
+ Rows::const_iterator bottom_row = row_;
+ Rows::const_iterator previous;
+ do {
+ bottom = bottom_row->second->bottom;
+ previous = bottom_row;
+ ++bottom_row;
+ } while (bottom_row != region_.rows_.end() &&
+ previous->second->bottom == bottom_row->second->top &&
+ IsSpanInRow(*bottom_row->second, *row_span_));
+ rect_ = DesktopRect::MakeLTRB(row_span_->left, row_->second->top,
+ row_span_->right, bottom);
}
} // namespace webrtc
-
diff --git a/webrtc/modules/desktop_capture/desktop_region.h b/webrtc/modules/desktop_capture/desktop_region.h
index 9a9daa4..403f2c2 100644
--- a/webrtc/modules/desktop_capture/desktop_region.h
+++ b/webrtc/modules/desktop_capture/desktop_region.h
@@ -11,6 +11,7 @@
#ifndef WEBRTC_MODULES_DESKTOP_CAPTURE_DESKTOP_REGION_H_
#define WEBRTC_MODULES_DESKTOP_CAPTURE_DESKTOP_REGION_H_
+#include <map>
#include <vector>
#include "webrtc/modules/desktop_capture/desktop_geometry.h"
@@ -21,9 +22,44 @@
// DesktopRegion represents a region of the screen or window.
//
-// TODO(sergeyu): Current implementation just stores list of rectangles that may
-// overlap. Optimize it.
+// Internally each region is stored as a set of rows where each row contains one
+// or more rectangles aligned vertically.
class DesktopRegion {
+ private:
+ // The following private types need to be declared first because they are used
+ // in the public Iterator.
+
+ // RowSpan represents a horizontal span withing a single row.
+ struct RowSpan {
+ RowSpan(int32_t left, int32_t right);
+
+ // Used by std::vector<>.
+ bool operator==(const RowSpan& that) const {
+ return left == that.left && right == that.right;
+ }
+
+ int32_t left;
+ int32_t right;
+ };
+
+ typedef std::vector<RowSpan> RowSpanSet;
+
+ // Row represents a single row of a region. A row is set of rectangles that
+ // have the same vertical position.
+ struct Row {
+ Row(int32_t top, int32_t bottom);
+
+ int32_t top;
+ int32_t bottom;
+
+ RowSpanSet spans;
+ };
+
+ // Type used to store list of rows in the region. The bottom position of row
+ // is used as the key so that rows are always ordered by their position. The
+ // map stores pointers to make Translate() more efficient.
+ typedef std::map<int, Row*> Rows;
+
public:
// Iterator that can be used to iterate over rectangles of a DesktopRegion.
// The region must not be mutated while the iterator is used.
@@ -34,24 +70,51 @@
bool IsAtEnd() const;
void Advance();
- const DesktopRect& rect() const { return *it_; }
+ const DesktopRect& rect() const { return rect_; }
private:
const DesktopRegion& region_;
- std::vector<DesktopRect>::const_iterator it_;
+
+ // Updates |rect_| based on the current |row_| and |row_span_|. If
+ // |row_span_| matches spans on consecutive rows then they are also merged
+ // into |rect_|, to generate more efficient output.
+ void UpdateCurrentRect();
+
+ Rows::const_iterator row_;
+ Rows::const_iterator previous_row_;
+ RowSpanSet::const_iterator row_span_;
+ DesktopRect rect_;
};
DesktopRegion();
+ explicit DesktopRegion(const DesktopRect& rect);
+ DesktopRegion(const DesktopRect* rects, int count);
DesktopRegion(const DesktopRegion& other);
~DesktopRegion();
- bool is_empty() const { return rects_.empty(); }
+ DesktopRegion& operator=(const DesktopRegion& other);
+ bool is_empty() const { return rows_.empty(); }
+
+ bool Equals(const DesktopRegion& region) const;
+
+ // Reset the region to be empty.
void Clear();
+
+ // Reset region to contain just |rect|.
void SetRect(const DesktopRect& rect);
+
+ // Adds specified rect(s) or region to the region.
void AddRect(const DesktopRect& rect);
+ void AddRects(const DesktopRect* rects, int count);
void AddRegion(const DesktopRegion& region);
+ // Finds intersection of two regions and stores them in the current region.
+ void Intersect(const DesktopRegion& region1, const DesktopRegion& region2);
+
+ // Same as above but intersects content of the current region with |region|.
+ void IntersectWith(const DesktopRegion& region);
+
// Clips the region by the |rect|.
void IntersectWith(const DesktopRect& rect);
@@ -61,8 +124,29 @@
void Swap(DesktopRegion* region);
private:
- typedef std::vector<DesktopRect> RectsList;
- RectsList rects_;
+ // Comparison functions used for std::lower_bound(). Compare left or right
+ // edges withs a given |value|.
+ static bool CompareSpanLeft(const RowSpan& r, int32_t value);
+ static bool CompareSpanRight(const RowSpan& r, int32_t value);
+
+ // Adds a new span to the row, coalescing spans if necessary.
+ static void AddSpanToRow(Row* row, int32_t left, int32_t right);
+
+ // Returns true if the |span| exists in the given |row|.
+ static bool IsSpanInRow(const Row& row, const RowSpan& rect);
+
+ // Calculates the intersection of two sets of spans.
+ static void IntersectRows(const RowSpanSet& set1,
+ const RowSpanSet& set2,
+ RowSpanSet* output);
+
+ // Merges |row| with the row above it if they contain the same spans. Doesn't
+ // do anything if called with |row| set to rows_.begin() (i.e. first row of
+ // the region). If the rows were merged |row| remains a valid iterator to the
+ // merged row.
+ void MergeWithPrecedingRow(Rows::iterator row);
+
+ Rows rows_;
};
} // namespace webrtc
diff --git a/webrtc/modules/desktop_capture/desktop_region_unittest.cc b/webrtc/modules/desktop_capture/desktop_region_unittest.cc
new file mode 100644
index 0000000..64ad4b8
--- /dev/null
+++ b/webrtc/modules/desktop_capture/desktop_region_unittest.cc
@@ -0,0 +1,464 @@
+/*
+ * Copyright (c) 2013 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "webrtc/modules/desktop_capture/desktop_region.h"
+
+#include <algorithm>
+
+#include "gtest/gtest.h"
+
+namespace webrtc {
+
+namespace {
+
+int RadmonInt(int max) {
+ return (rand() / 256) % max;
+}
+
+void CompareRegion(const DesktopRegion& region,
+ const DesktopRect rects[], int rects_size) {
+ DesktopRegion::Iterator it(region);
+ for (int i = 0; i < rects_size; ++i) {
+ SCOPED_TRACE(i);
+ ASSERT_FALSE(it.IsAtEnd());
+ EXPECT_TRUE(it.rect().equals(rects[i]))
+ << it.rect().left() << "-" << it.rect().right() << "."
+ << it.rect().top() << "-" << it.rect().bottom() << " "
+ << rects[i].left() << "-" << rects[i].right() << "."
+ << rects[i].top() << "-" << rects[i].bottom();
+ it.Advance();
+ }
+ EXPECT_TRUE(it.IsAtEnd());
+}
+
+} // namespace
+
+// Verify that regions are empty when created.
+TEST(DesktopRegionTest, Empty) {
+ DesktopRegion r;
+ CompareRegion(r, NULL, 0);
+}
+
+// Verify that empty rectangles are ignored.
+TEST(DesktopRegionTest, AddEmpty) {
+ DesktopRegion r;
+ DesktopRect rect = DesktopRect::MakeXYWH(1, 2, 0, 0);
+ r.AddRect(rect);
+ CompareRegion(r, NULL, 0);
+}
+
+// Verify that regions with a single rectangles are handled properly.
+TEST(DesktopRegionTest, SingleRect) {
+ DesktopRegion r;
+ DesktopRect rect = DesktopRect::MakeXYWH(1, 2, 3, 4);
+ r.AddRect(rect);
+ CompareRegion(r, &rect, 1);
+}
+
+// Verify that non-overlapping rectangles are not merged.
+TEST(DesktopRegionTest, NonOverlappingRects) {
+ struct Case {
+ int count;
+ DesktopRect rects[4];
+ } cases[] = {
+ { 1, { DesktopRect::MakeXYWH(10, 10, 10, 10) } },
+ { 2, { DesktopRect::MakeXYWH(10, 10, 10, 10),
+ DesktopRect::MakeXYWH(30, 10, 10, 15) } },
+ { 2, { DesktopRect::MakeXYWH(10, 10, 10, 10),
+ DesktopRect::MakeXYWH(10, 30, 10, 5) } },
+ { 3, { DesktopRect::MakeXYWH(10, 10, 10, 9),
+ DesktopRect::MakeXYWH(30, 10, 15, 10),
+ DesktopRect::MakeXYWH(10, 30, 8, 10) } },
+ { 4, { DesktopRect::MakeXYWH(0, 0, 30, 10),
+ DesktopRect::MakeXYWH(40, 0, 10, 30),
+ DesktopRect::MakeXYWH(0, 20, 10, 30),
+ DesktopRect::MakeXYWH(20, 40, 30, 10) } },
+ { 4, { DesktopRect::MakeXYWH(0, 0, 10, 100),
+ DesktopRect::MakeXYWH(20, 10, 30, 10),
+ DesktopRect::MakeXYWH(20, 30, 30, 10),
+ DesktopRect::MakeXYWH(20, 50, 30, 10) } },
+ };
+
+ for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
+ SCOPED_TRACE(i);
+
+ DesktopRegion r;
+
+ for (int j = 0; j < cases[i].count; ++j) {
+ r.AddRect(cases[i].rects[j]);
+ }
+ CompareRegion(r, cases[i].rects, cases[i].count);
+
+ SCOPED_TRACE("Reverse");
+
+ // Try inserting rects in reverse order.
+ r.Clear();
+ for (int j = cases[i].count - 1; j >= 0; --j) {
+ r.AddRect(cases[i].rects[j]);
+ }
+ CompareRegion(r, cases[i].rects, cases[i].count);
+ }
+}
+
+TEST(DesktopRegionTest, TwoRects) {
+ struct Case {
+ DesktopRect input_rect1;
+ DesktopRect input_rect2;
+ int expected_count;
+ DesktopRect expected_rects[3];
+ } cases[] = {
+ // Touching rectangles that merge into one.
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(0, 100, 100, 200),
+ 1, { DesktopRect::MakeLTRB(0, 100, 200, 200) } },
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(100, 0, 200, 100),
+ 1, { DesktopRect::MakeLTRB(100, 0, 200, 200) } },
+
+ // Rectangles touching on the vertical edge.
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(0, 150, 100, 250),
+ 3, { DesktopRect::MakeLTRB(100, 100, 200, 150),
+ DesktopRect::MakeLTRB(0, 150, 200, 200),
+ DesktopRect::MakeLTRB(0, 200, 100, 250) } },
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(0, 50, 100, 150),
+ 3, { DesktopRect::MakeLTRB(0, 50, 100, 100),
+ DesktopRect::MakeLTRB(0, 100, 200, 150),
+ DesktopRect::MakeLTRB(100, 150, 200, 200) } },
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(0, 120, 100, 180),
+ 3, { DesktopRect::MakeLTRB(100, 100, 200, 120),
+ DesktopRect::MakeLTRB(0, 120, 200, 180),
+ DesktopRect::MakeLTRB(100, 180, 200, 200) } },
+
+ // Rectangles touching on the horizontal edge.
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(150, 0, 250, 100),
+ 2, { DesktopRect::MakeLTRB(150, 0, 250, 100),
+ DesktopRect::MakeLTRB(100, 100, 200, 200) } },
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(50, 0, 150, 100),
+ 2, { DesktopRect::MakeLTRB(50, 0, 150, 100),
+ DesktopRect::MakeLTRB(100, 100, 200, 200) } },
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(120, 0, 180, 100),
+ 2, { DesktopRect::MakeLTRB(120, 0, 180, 100),
+ DesktopRect::MakeLTRB(100, 100, 200, 200) } },
+
+ // Overlapping rectangles.
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(50, 50, 150, 150),
+ 3, { DesktopRect::MakeLTRB(50, 50, 150, 100),
+ DesktopRect::MakeLTRB(50, 100, 200, 150),
+ DesktopRect::MakeLTRB(100, 150, 200, 200) } },
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(150, 50, 250, 150),
+ 3, { DesktopRect::MakeLTRB(150, 50, 250, 100),
+ DesktopRect::MakeLTRB(100, 100, 250, 150),
+ DesktopRect::MakeLTRB(100, 150, 200, 200) } },
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(0, 120, 150, 180),
+ 3, { DesktopRect::MakeLTRB(100, 100, 200, 120),
+ DesktopRect::MakeLTRB(0, 120, 200, 180),
+ DesktopRect::MakeLTRB(100, 180, 200, 200) } },
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(120, 0, 180, 150),
+ 2, { DesktopRect::MakeLTRB(120, 0, 180, 100),
+ DesktopRect::MakeLTRB(100, 100, 200, 200) } },
+ { DesktopRect::MakeLTRB(100, 0, 200, 300),
+ DesktopRect::MakeLTRB(0, 100, 300, 200),
+ 3, { DesktopRect::MakeLTRB(100, 0, 200, 100),
+ DesktopRect::MakeLTRB(0, 100, 300, 200),
+ DesktopRect::MakeLTRB(100, 200, 200, 300)} },
+
+ // One rectangle enclosing another.
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(150, 150, 180, 180),
+ 1, { DesktopRect::MakeLTRB(100, 100, 200, 200) } },
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(100, 100, 180, 180),
+ 1, { DesktopRect::MakeLTRB(100, 100, 200, 200) } },
+ { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(150, 150, 200, 200),
+ 1, { DesktopRect::MakeLTRB(100, 100, 200, 200) } },
+ };
+
+ for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
+ SCOPED_TRACE(i);
+
+ DesktopRegion r;
+
+ r.AddRect(cases[i].input_rect1);
+ r.AddRect(cases[i].input_rect2);
+ CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
+
+ SCOPED_TRACE("Reverse");
+
+ // Run the same test with rectangles inserted in reverse order.
+ r.Clear();
+ r.AddRect(cases[i].input_rect2);
+ r.AddRect(cases[i].input_rect1);
+ CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
+ }
+}
+
+// Verify that DesktopRegion::AddRectToRow() works correctly by creating a row
+// of not overlapping rectangles and insert an overlapping rectangle into the
+// row at different positions. Result is verified by building a map of the
+// region in an array and comparing it with the expected values.
+TEST(DesktopRegionTest, SameRow) {
+ const int kMapWidth = 50;
+ const int kLastRectSizes[] = {3, 27};
+
+ DesktopRegion base_region;
+ bool base_map[kMapWidth] = { false, };
+
+ base_region.AddRect(DesktopRect::MakeXYWH(5, 0, 5, 1));
+ std::fill_n(base_map + 5, 5, true);
+ base_region.AddRect(DesktopRect::MakeXYWH(15, 0, 5, 1));
+ std::fill_n(base_map + 15, 5, true);
+ base_region.AddRect(DesktopRect::MakeXYWH(25, 0, 5, 1));
+ std::fill_n(base_map + 25, 5, true);
+ base_region.AddRect(DesktopRect::MakeXYWH(35, 0, 5, 1));
+ std::fill_n(base_map + 35, 5, true);
+ base_region.AddRect(DesktopRect::MakeXYWH(45, 0, 5, 1));
+ std::fill_n(base_map + 45, 5, true);
+
+ for (size_t i = 0; i < sizeof(kLastRectSizes) / sizeof(kLastRectSizes[0]);
+ i++) {
+ int last_rect_size = kLastRectSizes[i];
+ for (int x = 0; x < kMapWidth - last_rect_size; x++) {
+ SCOPED_TRACE(x);
+
+ DesktopRegion r = base_region;
+ r.AddRect(DesktopRect::MakeXYWH(x, 0, last_rect_size, 1));
+
+ bool expected_map[kMapWidth];
+ std::copy(base_map, base_map + kMapWidth, expected_map);
+ std::fill_n(expected_map + x, last_rect_size, true);
+
+ bool map[kMapWidth] = { false, };
+
+ int pos = -1;
+ for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) {
+ EXPECT_GT(it.rect().left(), pos);
+ pos = it.rect().right();
+ std::fill_n(map + it.rect().left(), it.rect().width(), true);
+ }
+
+ EXPECT_TRUE(std::equal(map, map + kMapWidth, expected_map));
+ }
+ }
+}
+
+TEST(DesktopRegionTest, ComplexRegions) {
+ struct Case {
+ int input_count;
+ DesktopRect input_rects[4];
+ int expected_count;
+ DesktopRect expected_rects[6];
+ } cases[] = {
+ { 3, { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(0, 100, 100, 200),
+ DesktopRect::MakeLTRB(310, 110, 320, 120), },
+ 2, { DesktopRect::MakeLTRB(0, 100, 200, 200),
+ DesktopRect::MakeLTRB(310, 110, 320, 120) } },
+ { 3, { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(50, 50, 150, 150),
+ DesktopRect::MakeLTRB(300, 125, 350, 175) },
+ 4, { DesktopRect::MakeLTRB(50, 50, 150, 100),
+ DesktopRect::MakeLTRB(50, 100, 200, 150),
+ DesktopRect::MakeLTRB(300, 125, 350, 175),
+ DesktopRect::MakeLTRB(100, 150, 200, 200) } },
+ { 4, { DesktopRect::MakeLTRB(0, 0, 30, 30),
+ DesktopRect::MakeLTRB(10, 10, 40, 40),
+ DesktopRect::MakeLTRB(20, 20, 50, 50),
+ DesktopRect::MakeLTRB(50, 0, 65, 15) },
+ 6, { DesktopRect::MakeLTRB(0, 0, 30, 10),
+ DesktopRect::MakeLTRB(50, 0, 65, 15),
+ DesktopRect::MakeLTRB(0, 10, 40, 20),
+ DesktopRect::MakeLTRB(0, 20, 50, 30),
+ DesktopRect::MakeLTRB(10, 30, 50, 40),
+ DesktopRect::MakeLTRB(20, 40, 50, 50) } },
+ { 3, { DesktopRect::MakeLTRB(10, 10, 40, 20),
+ DesktopRect::MakeLTRB(10, 30, 40, 40),
+ DesktopRect::MakeLTRB(10, 20, 40, 30) },
+ 1, { DesktopRect::MakeLTRB(10, 10, 40, 40) } },
+ };
+
+ for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
+ SCOPED_TRACE(i);
+
+ DesktopRegion r;
+ r.AddRects(cases[i].input_rects, cases[i].input_count);
+ CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
+
+ // Try inserting rectangles in reverse order.
+ r.Clear();
+ for (int j = cases[i].input_count - 1; j >= 0; --j) {
+ r.AddRect(cases[i].input_rects[j]);
+ }
+ CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
+ }
+}
+
+TEST(DesktopRegionTest, Equals) {
+ struct Region {
+ int count;
+ DesktopRect rects[4];
+ int id;
+ } regions[] = {
+ // Same region with one of the rectangles 1 pixel wider/taller.
+ { 2, { DesktopRect::MakeLTRB(0, 100, 200, 200),
+ DesktopRect::MakeLTRB(310, 110, 320, 120) }, 0 },
+ { 2, { DesktopRect::MakeLTRB(0, 100, 201, 200),
+ DesktopRect::MakeLTRB(310, 110, 320, 120) }, 1 },
+ { 2, { DesktopRect::MakeLTRB(0, 100, 200, 201),
+ DesktopRect::MakeLTRB(310, 110, 320, 120) }, 2 },
+
+ // Same region with one of the rectangles shifted horizontally and
+ // vertically.
+ { 4, { DesktopRect::MakeLTRB(0, 0, 30, 30),
+ DesktopRect::MakeLTRB(10, 10, 40, 40),
+ DesktopRect::MakeLTRB(20, 20, 50, 50),
+ DesktopRect::MakeLTRB(50, 0, 65, 15) }, 3 },
+ { 4, { DesktopRect::MakeLTRB(0, 0, 30, 30),
+ DesktopRect::MakeLTRB(10, 10, 40, 40),
+ DesktopRect::MakeLTRB(20, 20, 50, 50),
+ DesktopRect::MakeLTRB(50, 1, 65, 16) }, 4 },
+ { 4, { DesktopRect::MakeLTRB(0, 0, 30, 30),
+ DesktopRect::MakeLTRB(10, 10, 40, 40),
+ DesktopRect::MakeLTRB(20, 20, 50, 50),
+ DesktopRect::MakeLTRB(51, 0, 66, 15) }, 5 },
+
+ // Same region defined by a different set of rectangles - one of the
+ // rectangle is split horizontally into two.
+ { 3, { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(50, 50, 150, 150),
+ DesktopRect::MakeLTRB(300, 125, 350, 175) }, 6 },
+ { 4, { DesktopRect::MakeLTRB(100, 100, 200, 200),
+ DesktopRect::MakeLTRB(50, 50, 100, 150),
+ DesktopRect::MakeLTRB(100, 50, 150, 150),
+ DesktopRect::MakeLTRB(300, 125, 350, 175) }, 6 },
+
+ // Rectangle region defined by a set of rectangles that merge into one.
+ { 3, { DesktopRect::MakeLTRB(10, 10, 40, 20),
+ DesktopRect::MakeLTRB(10, 30, 40, 40),
+ DesktopRect::MakeLTRB(10, 20, 40, 30) }, 7 },
+ { 1, { DesktopRect::MakeLTRB(10, 10, 40, 40) }, 7 },
+ };
+ int kTotalRegions = sizeof(regions) / sizeof(Region);
+
+ for (int i = 0; i < kTotalRegions; ++i) {
+ SCOPED_TRACE(i);
+
+ DesktopRegion r1(regions[i].rects, regions[i].count);
+ for (int j = 0; j < kTotalRegions; ++j) {
+ SCOPED_TRACE(j);
+
+ DesktopRegion r2(regions[j].rects, regions[j].count);
+ EXPECT_EQ(regions[i].id == regions[j].id, r1.Equals(r2));
+ }
+ }
+}
+
+TEST(DesktopRegionTest, Translate) {
+ struct Case {
+ int input_count;
+ DesktopRect input_rects[4];
+ int dx;
+ int dy;
+ int expected_count;
+ DesktopRect expected_rects[5];
+ } cases[] = {
+ { 3, { DesktopRect::MakeLTRB(0, 0, 30, 30),
+ DesktopRect::MakeLTRB(10, 10, 40, 40),
+ DesktopRect::MakeLTRB(20, 20, 50, 50) },
+ 3, 5,
+ 5, { DesktopRect::MakeLTRB(3, 5, 33, 15),
+ DesktopRect::MakeLTRB(3, 15, 43, 25),
+ DesktopRect::MakeLTRB(3, 25, 53, 35),
+ DesktopRect::MakeLTRB(13, 35, 53, 45),
+ DesktopRect::MakeLTRB(23, 45, 53, 55) } },
+ };
+
+ for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
+ SCOPED_TRACE(i);
+
+ DesktopRegion r(cases[i].input_rects, cases[i].input_count);
+ r.Translate(cases[i].dx, cases[i].dy);
+ CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
+ }
+}
+
+TEST(DesktopRegionTest, Intersect) {
+ struct Case {
+ int input1_count;
+ DesktopRect input1_rects[4];
+ int input2_count;
+ DesktopRect input2_rects[4];
+ int expected_count;
+ DesktopRect expected_rects[5];
+ } cases[] = {
+ { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 1, { DesktopRect::MakeLTRB(50, 50, 150, 150) },
+ 1, { DesktopRect::MakeLTRB(50, 50, 100, 100) } },
+
+ { 1, { DesktopRect::MakeLTRB(100, 0, 200, 300) },
+ 1, { DesktopRect::MakeLTRB(0, 100, 300, 200) },
+ 1, { DesktopRect::MakeLTRB(100, 100, 200, 200) } },
+
+ { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 2, { DesktopRect::MakeLTRB(50, 10, 150, 30),
+ DesktopRect::MakeLTRB(50, 30, 160, 50) },
+ 1, { DesktopRect::MakeLTRB(50, 10, 100, 50) } },
+
+ { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
+ 2, { DesktopRect::MakeLTRB(50, 10, 150, 30),
+ DesktopRect::MakeLTRB(50, 30, 90, 50) },
+ 2, { DesktopRect::MakeLTRB(50, 10, 100, 30),
+ DesktopRect::MakeLTRB(50, 30, 90, 50) } },
+ };
+
+ for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
+ SCOPED_TRACE(i);
+
+ DesktopRegion r1(cases[i].input1_rects, cases[i].input1_count);
+ DesktopRegion r2(cases[i].input2_rects, cases[i].input2_count);
+
+ DesktopRegion r;
+ r.Intersect(r1, r2);
+
+ CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
+ }
+}
+
+TEST(DesktopRegionTest, DISABLED_Performance) {
+ for (int c = 0; c < 1000; ++c) {
+ DesktopRegion r;
+ for (int i = 0; i < 10; ++i) {
+ r.AddRect(DesktopRect::MakeXYWH(
+ RadmonInt(1000), RadmonInt(1000), 200, 200));
+ }
+
+ for (int i = 0; i < 1000; ++i) {
+ r.AddRect(DesktopRect::MakeXYWH(
+ RadmonInt(1000), RadmonInt(1000),
+ 5 + RadmonInt(10) * 5, 5 + RadmonInt(10) * 5));
+ }
+
+ // Iterate over the rectangles.
+ for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) {
+ }
+ }
+}
+
+} // namespace webrtc