103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)// Copyright 2014 The Chromium Authors. All rights reserved. 203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)// found in the LICENSE file. 403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)#include "cc/base/simple_enclosed_region.h" 603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)#include "base/logging.h" 803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)#include "cc/base/region.h" 903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 1003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)namespace cc { 1103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 1203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)static bool RectIsLargerArea(const gfx::Rect& a, const gfx::Rect b) { 1303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int64 a_area = static_cast<int64>(a.width()) * a.height(); 1403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int64 b_area = static_cast<int64>(b.width()) * b.height(); 1503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) return a_area > b_area; 1603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)} 1703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 1803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)SimpleEnclosedRegion::SimpleEnclosedRegion(const Region& region) { 1903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) for (Region::Iterator it(region); it.has_rect(); it.next()) 2003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) Union(it.rect()); 2103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)} 2203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 2303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)SimpleEnclosedRegion::~SimpleEnclosedRegion() { 2403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)} 2503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 2603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)void SimpleEnclosedRegion::Subtract(const gfx::Rect& sub_rect) { 2703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // We want to keep as much of the current rect as we can, so find the one 2803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // largest rectangle inside |rect_| that does not intersect with |sub_rect|. 2903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (!rect_.Intersects(sub_rect)) 3003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) return; 3103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (sub_rect.Contains(rect_)) { 3203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) rect_ = gfx::Rect(); 3303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) return; 3403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) } 3503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 3603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int left = rect_.x(); 3703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int right = rect_.right(); 3803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int top = rect_.y(); 3903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int bottom = rect_.bottom(); 4003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 4103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int delta_left = sub_rect.x() - left; 4203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int delta_right = right - sub_rect.right(); 4303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int delta_top = sub_rect.y() - top; 4403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int delta_bottom = bottom - sub_rect.bottom(); 4503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 4603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // The horizontal rect is the larger of the two rectangles above or below 4703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // |sub_rect| and inside rect_. 4803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int horizontal_top = top; 4903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int horizontal_bottom = bottom; 5003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (delta_top > delta_bottom) 5103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) horizontal_bottom = sub_rect.y(); 5203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) else 5303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) horizontal_top = sub_rect.bottom(); 5403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // The vertical rect is the larger of the two rectangles to the left or the 5503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // right of |sub_rect| and inside rect_. 5603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int vertical_left = left; 5703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int vertical_right = right; 5803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (delta_left > delta_right) 5903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) vertical_right = sub_rect.x(); 6003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) else 6103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) vertical_left = sub_rect.right(); 6203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 6303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) rect_.SetRect( 6403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) left, horizontal_top, right - left, horizontal_bottom - horizontal_top); 6503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 6603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) gfx::Rect vertical_rect( 6703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) vertical_left, top, vertical_right - vertical_left, bottom - top); 6803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (RectIsLargerArea(vertical_rect, rect_)) 6903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) rect_ = vertical_rect; 7003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)} 7103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 7203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)void SimpleEnclosedRegion::Union(const gfx::Rect& new_rect) { 7303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // We want to keep track of a region but bound its complexity at a constant 7403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // size. We keep track of the largest rectangle seen by area. If we can add 7503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // the |new_rect| to this rectangle then we do that, as that is the cheapest 7603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // way to increase the area returned without increasing the complexity. 7703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (new_rect.IsEmpty()) 7803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) return; 7903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (rect_.Contains(new_rect)) 8003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) return; 8103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (new_rect.Contains(rect_)) { 8203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) rect_ = new_rect; 8303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) return; 8403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) } 8503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 8603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int left = rect_.x(); 8703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int top = rect_.y(); 8803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int right = rect_.right(); 8903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int bottom = rect_.bottom(); 9003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 9103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int new_left = new_rect.x(); 9203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int new_top = new_rect.y(); 9303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int new_right = new_rect.right(); 9403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) int new_bottom = new_rect.bottom(); 9503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 9603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // This attempts to expand each edge of |rect_| if the |new_rect| entirely 9703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // covers or is adjacent to an entire edge of |rect_|. If this is true for 9803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // an edge of |rect_| then it can be expanded out to share that edge with the 9903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // same edge of |new_rect|. After, the same thing is done to try expand 10003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // |new_rect| relative to |rect_|. 10103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (new_top <= top && new_bottom >= bottom) { 10203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (new_left < left && new_right >= left) 10303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) left = new_left; 10403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (new_right > right && new_left <= right) 10503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) right = new_right; 10603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) } else if (new_left <= left && new_right >= right) { 10703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (new_top < top && new_bottom >= top) 10803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) top = new_top; 10903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (new_bottom > bottom && new_top <= bottom) 11003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) bottom = new_bottom; 11103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) } else if (top <= new_top && bottom >= new_bottom) { 11203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (left < new_left && right >= new_left) 11303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) new_left = left; 11403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (right > new_right && left <= new_right) 11503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) new_right = right; 11603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) } else if (left <= new_left && right >= new_right) { 11703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (top < new_top && bottom >= new_top) 11803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) new_top = top; 11903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (bottom > new_bottom && top <= new_bottom) 12003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) new_bottom = bottom; 12103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) } 12203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 12303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) rect_.SetRect(left, top, right - left, bottom - top); 12403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 12503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) gfx::Rect adjusted_new_rect( 12603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) new_left, new_top, new_right - new_left, new_bottom - new_top); 12703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) if (RectIsLargerArea(adjusted_new_rect, rect_)) 12803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) rect_ = adjusted_new_rect; 12903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)} 13003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 13103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)gfx::Rect SimpleEnclosedRegion::GetRect(size_t i) const { 13203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) DCHECK_LT(i, GetRegionComplexity()); 13303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) return rect_; 13403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)} 13503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 13603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles)} // namespace cc 137