2 * Copyright (c) 2013 The WebRTC project authors. All Rights Reserved.
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
11 #include "webrtc/modules/desktop_capture/desktop_region.h"
19 DesktopRegion::RowSpan::RowSpan(int32_t left, int32_t right)
20 : left(left), right(right) {
23 DesktopRegion::Row::Row(int32_t top, int32_t bottom)
24 : top(top), bottom(bottom) {
27 DesktopRegion::Row::~Row() {}
29 DesktopRegion::DesktopRegion() {}
31 DesktopRegion::DesktopRegion(const DesktopRect& rect) {
35 DesktopRegion::DesktopRegion(const DesktopRect* rects, int count) {
36 AddRects(rects, count);
39 DesktopRegion::DesktopRegion(const DesktopRegion& other) {
43 DesktopRegion::~DesktopRegion() {
47 DesktopRegion& DesktopRegion::operator=(const DesktopRegion& other) {
50 for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) {
52 Row* row = it->second;
53 it->second = new Row(*row);
58 bool DesktopRegion::Equals(const DesktopRegion& region) const {
59 // Iterate over rows of the tow regions and compare each row.
60 Rows::const_iterator it1 = rows_.begin();
61 Rows::const_iterator it2 = region.rows_.begin();
62 while (it1 != rows_.end()) {
63 if (it2 == region.rows_.end() ||
64 it1->first != it2->first ||
65 it1->second->top != it2->second->top ||
66 it1->second->bottom != it2->second->bottom ||
67 it1->second->spans != it2->second->spans) {
73 return it2 == region.rows_.end();
76 void DesktopRegion::Clear() {
77 for (Rows::iterator row = rows_.begin(); row != rows_.end(); ++row) {
83 void DesktopRegion::SetRect(const DesktopRect& rect) {
88 void DesktopRegion::AddRect(const DesktopRect& rect) {
92 // Top of the part of the |rect| that hasn't been inserted yet. Increased as
93 // we iterate over the rows until it reaches |rect.bottom()|.
96 // Iterate over all rows that may intersect with |rect| and add new rows when
98 Rows::iterator row = rows_.upper_bound(top);
99 while (top < rect.bottom()) {
100 if (row == rows_.end() || top < row->second->top) {
101 // If |top| is above the top of the current |row| then add a new row above
103 int32_t bottom = rect.bottom();
104 if (row != rows_.end() && row->second->top < bottom)
105 bottom = row->second->top;
107 row, Rows::value_type(bottom, new Row(top, bottom)));
108 } else if (top > row->second->top) {
109 // If the |top| falls in the middle of the |row| then split |row| into
110 // two, at |top|, and leave |row| referring to the lower of the two,
111 // ready to insert a new span into.
112 assert(top <= row->second->bottom);
113 Rows::iterator new_row = rows_.insert(
114 row, Rows::value_type(top, new Row(row->second->top, top)));
115 row->second->top = top;
116 new_row->second->spans = row->second->spans;
119 if (rect.bottom() < row->second->bottom) {
120 // If the bottom of the |rect| falls in the middle of the |row| split
121 // |row| into two, at |top|, and leave |row| referring to the upper of
122 // the two, ready to insert a new span into.
123 Rows::iterator new_row = rows_.insert(
124 row, Rows::value_type(rect.bottom(), new Row(top, rect.bottom())));
125 row->second->top = rect.bottom();
126 new_row->second->spans = row->second->spans;
130 // Add a new span to the current row.
131 AddSpanToRow(row->second, rect.left(), rect.right());
132 top = row->second->bottom;
134 MergeWithPrecedingRow(row);
136 // Move to the next row.
140 if (row != rows_.end())
141 MergeWithPrecedingRow(row);
144 void DesktopRegion::AddRects(const DesktopRect* rects, int count) {
145 for (int i = 0; i < count; ++i) {
150 void DesktopRegion::MergeWithPrecedingRow(Rows::iterator row) {
151 assert(row != rows_.end());
153 if (row != rows_.begin()) {
154 Rows::iterator previous_row = row;
157 // If |row| and |previous_row| are next to each other and contain the same
158 // set of spans then they can be merged.
159 if (previous_row->second->bottom == row->second->top &&
160 previous_row->second->spans == row->second->spans) {
161 row->second->top = previous_row->second->top;
162 delete previous_row->second;
163 rows_.erase(previous_row);
168 void DesktopRegion::AddRegion(const DesktopRegion& region) {
169 // TODO(sergeyu): This function is not optimized - potentially it can iterate
170 // over rows of the two regions similar to how it works in Intersect().
171 for (Iterator it(region); !it.IsAtEnd(); it.Advance()) {
176 void DesktopRegion::Intersect(const DesktopRegion& region1,
177 const DesktopRegion& region2) {
180 Rows::const_iterator it1 = region1.rows_.begin();
181 Rows::const_iterator end1 = region1.rows_.end();
182 Rows::const_iterator it2 = region2.rows_.begin();
183 Rows::const_iterator end2 = region2.rows_.end();
184 if (it1 == end1 || it2 == end2)
187 while (it1 != end1 && it2 != end2) {
188 // Arrange for |it1| to always be the top-most of the rows.
189 if (it2->second->top < it1->second->top) {
191 std::swap(end1, end2);
194 // Skip |it1| if it doesn't intersect |it2| at all.
195 if (it1->second->bottom <= it2->second->top) {
200 // Top of the |it1| row is above the top of |it2|, so top of the
201 // intersection is always the top of |it2|.
202 int32_t top = it2->second->top;
203 int32_t bottom = std::min(it1->second->bottom, it2->second->bottom);
205 Rows::iterator new_row = rows_.insert(
206 rows_.end(), Rows::value_type(bottom, new Row(top, bottom)));
207 IntersectRows(it1->second->spans, it2->second->spans,
208 &new_row->second->spans);
209 if (new_row->second->spans.empty()) {
210 delete new_row->second;
211 rows_.erase(new_row);
213 MergeWithPrecedingRow(new_row);
216 // If |it1| was completely consumed, move to the next one.
217 if (it1->second->bottom == bottom)
219 // If |it2| was completely consumed, move to the next one.
220 if (it2->second->bottom == bottom)
226 void DesktopRegion::IntersectRows(const RowSpanSet& set1,
227 const RowSpanSet& set2,
228 RowSpanSet* output) {
229 RowSpanSet::const_iterator it1 = set1.begin();
230 RowSpanSet::const_iterator end1 = set1.end();
231 RowSpanSet::const_iterator it2 = set2.begin();
232 RowSpanSet::const_iterator end2 = set2.end();
233 assert(it1 != end1 && it2 != end2);
236 // Arrange for |it1| to always be the left-most of the spans.
237 if (it2->left < it1->left) {
239 std::swap(end1, end2);
242 // Skip |it1| if it doesn't intersect |it2| at all.
243 if (it1->right <= it2->left) {
248 int32_t left = it2->left;
249 int32_t right = std::min(it1->right, it2->right);
250 assert(left < right);
252 output->push_back(RowSpan(left, right));
254 // If |it1| was completely consumed, move to the next one.
255 if (it1->right == right)
257 // If |it2| was completely consumed, move to the next one.
258 if (it2->right == right)
260 } while (it1 != end1 && it2 != end2);
263 void DesktopRegion::IntersectWith(const DesktopRegion& region) {
264 DesktopRegion old_region;
266 Intersect(old_region, region);
269 void DesktopRegion::IntersectWith(const DesktopRect& rect) {
270 DesktopRegion region;
271 region.AddRect(rect);
272 IntersectWith(region);
275 void DesktopRegion::Subtract(const DesktopRegion& region) {
276 if (region.rows_.empty())
279 // |row_b| refers to the current row being subtracted.
280 Rows::const_iterator row_b = region.rows_.begin();
282 // Current vertical position at which subtraction is happening.
283 int top = row_b->second->top;
285 // |row_a| refers to the current row we are subtracting from. Skip all rows
287 Rows::iterator row_a = rows_.upper_bound(top);
289 // Step through rows of the both regions subtracting content of |row_b| from
291 while (row_a != rows_.end() && row_b != region.rows_.end()) {
292 // Skip |row_a| if it doesn't intersect with the |row_b|.
293 if (row_a->second->bottom <= top) {
294 // Each output row is merged with previously-processed rows before further
295 // rows are processed.
296 MergeWithPrecedingRow(row_a);
301 if (top > row_a->second->top) {
302 // If |top| falls in the middle of |row_a| then split |row_a| into two, at
303 // |top|, and leave |row_a| referring to the lower of the two, ready to
304 // subtract spans from.
305 assert(top <= row_a->second->bottom);
306 Rows::iterator new_row = rows_.insert(
307 row_a, Rows::value_type(top, new Row(row_a->second->top, top)));
308 row_a->second->top = top;
309 new_row->second->spans = row_a->second->spans;
310 } else if (top < row_a->second->top) {
311 // If the |top| is above |row_a| then skip the range between |top| and
312 // top of |row_a| because it's empty.
313 top = row_a->second->top;
314 if (top >= row_b->second->bottom) {
316 if (row_b != region.rows_.end())
317 top = row_b->second->top;
322 if (row_b->second->bottom < row_a->second->bottom) {
323 // If the bottom of |row_b| falls in the middle of the |row_a| split
324 // |row_a| into two, at |top|, and leave |row_a| referring to the upper of
325 // the two, ready to subtract spans from.
326 int bottom = row_b->second->bottom;
327 Rows::iterator new_row =
328 rows_.insert(row_a, Rows::value_type(bottom, new Row(top, bottom)));
329 row_a->second->top = bottom;
330 new_row->second->spans = row_a->second->spans;
334 // At this point the vertical range covered by |row_a| lays within the
335 // range covered by |row_b|. Subtract |row_b| spans from |row_a|.
336 RowSpanSet new_spans;
337 SubtractRows(row_a->second->spans, row_b->second->spans, &new_spans);
338 new_spans.swap(row_a->second->spans);
339 top = row_a->second->bottom;
341 if (top >= row_b->second->bottom) {
343 if (row_b != region.rows_.end())
344 top = row_b->second->top;
347 // Check if the row is empty after subtraction and delete it. Otherwise move
349 if (row_a->second->spans.empty()) {
350 Rows::iterator row_to_delete = row_a;
352 delete row_to_delete->second;
353 rows_.erase(row_to_delete);
355 MergeWithPrecedingRow(row_a);
360 if (row_a != rows_.end())
361 MergeWithPrecedingRow(row_a);
364 void DesktopRegion::Subtract(const DesktopRect& rect) {
365 DesktopRegion region;
366 region.AddRect(rect);
370 void DesktopRegion::Translate(int32_t dx, int32_t dy) {
373 for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) {
374 Row* row = it->second;
380 // Translate each span.
381 for (RowSpanSet::iterator span = row->spans.begin();
382 span != row->spans.end(); ++span) {
389 new_rows.insert(new_rows.end(), Rows::value_type(row->bottom, row));
393 new_rows.swap(rows_);
396 void DesktopRegion::Swap(DesktopRegion* region) {
397 rows_.swap(region->rows_);
401 bool DesktopRegion::CompareSpanRight(const RowSpan& r, int32_t value) {
402 return r.right < value;
406 bool DesktopRegion::CompareSpanLeft(const RowSpan& r, int32_t value) {
407 return r.left < value;
411 void DesktopRegion::AddSpanToRow(Row* row, int left, int right) {
412 // First check if the new span is located to the right of all existing spans.
413 // This is an optimization to avoid binary search in the case when rectangles
414 // are inserted sequentially from left to right.
415 if (row->spans.empty() || left > row->spans.back().right) {
416 row->spans.push_back(RowSpan(left, right));
420 // Find the first span that ends at or after |left|.
421 RowSpanSet::iterator start =
422 std::lower_bound(row->spans.begin(), row->spans.end(), left,
424 assert(start < row->spans.end());
426 // Find the first span that starts after |right|.
427 RowSpanSet::iterator end =
428 std::lower_bound(start, row->spans.end(), right + 1, CompareSpanLeft);
429 if (end == row->spans.begin()) {
430 // There are no overlaps. Just insert the new span at the beginning.
431 row->spans.insert(row->spans.begin(), RowSpan(left, right));
435 // Move end to the left, so that it points the last span that ends at or
439 // At this point [start, end] is the range of spans that intersect with the
442 // There are no overlaps. Just insert the new span at the correct position.
443 row->spans.insert(start, RowSpan(left, right));
447 left = std::min(left, start->left);
448 right = std::max(right, end->right);
450 // Replace range [start, end] with the new span.
451 *start = RowSpan(left, right);
455 row->spans.erase(start, end);
459 bool DesktopRegion::IsSpanInRow(const Row& row, const RowSpan& span) {
460 // Find the first span that starts at or after |span.left| and then check if
461 // it's the same span.
462 RowSpanSet::const_iterator it =
463 std::lower_bound(row.spans.begin(), row.spans.end(), span.left,
465 return it != row.spans.end() && *it == span;
469 void DesktopRegion::SubtractRows(const RowSpanSet& set_a,
470 const RowSpanSet& set_b,
471 RowSpanSet* output) {
472 assert(!set_a.empty() && !set_b.empty());
474 RowSpanSet::const_iterator it_b = set_b.begin();
476 // Iterate over all spans in |set_a| adding parts of it that do not intersect
477 // with |set_b| to the |output|.
478 for (RowSpanSet::const_iterator it_a = set_a.begin(); it_a != set_a.end();
480 // If there is no intersection then append the current span and continue.
481 if (it_b == set_b.end() || it_a->right < it_b->left) {
482 output->push_back(*it_a);
486 // Iterate over |set_b| spans that may intersect with |it_a|.
487 int pos = it_a->left;
488 while (it_b != set_b.end() && it_b->left < it_a->right) {
489 if (it_b->left > pos)
490 output->push_back(RowSpan(pos, it_b->left));
491 if (it_b->right > pos) {
493 if (pos >= it_a->right)
498 if (pos < it_a->right)
499 output->push_back(RowSpan(pos, it_a->right));
503 DesktopRegion::Iterator::Iterator(const DesktopRegion& region)
505 row_(region.rows_.begin()),
506 previous_row_(region.rows_.end()) {
508 assert(row_->second->spans.size() > 0);
509 row_span_ = row_->second->spans.begin();
514 bool DesktopRegion::Iterator::IsAtEnd() const {
515 return row_ == region_.rows_.end();
518 void DesktopRegion::Iterator::Advance() {
523 if (row_span_ == row_->second->spans.end()) {
524 previous_row_ = row_;
526 if (row_ != region_.rows_.end()) {
527 assert(row_->second->spans.size() > 0);
528 row_span_ = row_->second->spans.begin();
535 // If the same span exists on the previous row then skip it, as we've
536 // already returned this span merged into the previous one, via
537 // UpdateCurrentRect().
538 if (previous_row_ != region_.rows_.end() &&
539 previous_row_->second->bottom == row_->second->top &&
540 IsSpanInRow(*previous_row_->second, *row_span_)) {
551 void DesktopRegion::Iterator::UpdateCurrentRect() {
552 // Merge the current rectangle with the matching spans from later rows.
554 Rows::const_iterator bottom_row = row_;
555 Rows::const_iterator previous;
557 bottom = bottom_row->second->bottom;
558 previous = bottom_row;
560 } while (bottom_row != region_.rows_.end() &&
561 previous->second->bottom == bottom_row->second->top &&
562 IsSpanInRow(*bottom_row->second, *row_span_));
563 rect_ = DesktopRect::MakeLTRB(row_span_->left, row_->second->top,
564 row_span_->right, bottom);
567 } // namespace webrtc