15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2010, 2011 Apple Inc. All rights reserved. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modification, are permitted provided that the following conditions 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * are met: 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1. Redistributions of source code must retain the above copyright 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer. 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2. Redistributions in binary form must reproduce the above copyright 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer in the 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * documentation and/or other materials provided with the distribution. 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THE POSSIBILITY OF SUCH DAMAGE. 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "config.h" 2753e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)#include "core/platform/graphics/Region.h" 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include <stdio.h> 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// A region class based on the paper "Scanline Coherent Shape Algebra" 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// by Jonathan E. Steinhart from the book "Graphics Gems II". 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// This implementation uses two vectors instead of linked list, and 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// also compresses regions when possible. 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace WebCore { 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Region() 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Region(const IntRect& rect) 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_bounds(rect) 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_shape(rect) 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Vector<IntRect> Region::rects() const 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<IntRect> rects; 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (Shape::SpanIterator span = m_shape.spans_begin(), end = m_shape.spans_end(); span != end && span + 1 != end; ++span) { 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int y = span->y; 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int height = (span + 1)->y - y; 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (Shape::SegmentIterator segment = m_shape.segments_begin(span), end = m_shape.segments_end(span); segment != end && segment + 1 != end; segment += 2) { 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int x = *segment; 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int width = *(segment + 1) - x; 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) rects.append(IntRect(x, y, width, height)); 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return rects; 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)bool Region::contains(const Region& region) const 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_bounds.contains(region.m_bounds)) 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return Shape::compareShapes<Shape::CompareContainsOperation>(m_shape, region.m_shape); 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)bool Region::contains(const IntPoint& point) const 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_bounds.contains(point)) 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (Shape::SpanIterator span = m_shape.spans_begin(), end = m_shape.spans_end(); span != end && span + 1 != end; ++span) { 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int y = span->y; 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int maxY = (span + 1)->y; 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (y > point.y()) 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (maxY <= point.y()) 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) continue; 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (Shape::SegmentIterator segment = m_shape.segments_begin(span), end = m_shape.segments_end(span); segment != end && segment + 1 != end; segment += 2) { 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int x = *segment; 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int maxX = *(segment + 1); 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (x > point.x()) 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (maxX > point.x()) 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)bool Region::intersects(const Region& region) const 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_bounds.intersects(region.m_bounds)) 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return Shape::compareShapes<Shape::CompareIntersectsOperation>(m_shape, region.m_shape); 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)unsigned Region::totalArea() const 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<IntRect> rects = this->rects(); 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t size = rects.size(); 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned totalArea = 0; 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (size_t i = 0; i < size; ++i) { 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) IntRect rect = rects[i]; 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) totalArea += (rect.width() * rect.height()); 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return totalArea; 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<typename CompareOperation> 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)bool Region::Shape::compareShapes(const Shape& aShape, const Shape& bShape) 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool result = CompareOperation::defaultResult; 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape::SpanIterator aSpan = aShape.spans_begin(); 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape::SpanIterator aSpanEnd = aShape.spans_end(); 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape::SpanIterator bSpan = bShape.spans_begin(); 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape::SpanIterator bSpanEnd = bShape.spans_end(); 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool aHadSegmentInPreviousSpan = false; 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool bHadSegmentInPreviousSpan = false; 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (aSpan != aSpanEnd && aSpan + 1 != aSpanEnd && bSpan != bSpanEnd && bSpan + 1 != bSpanEnd) { 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int aY = aSpan->y; 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int aMaxY = (aSpan + 1)->y; 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int bY = bSpan->y; 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int bMaxY = (bSpan + 1)->y; 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape::SegmentIterator aSegment = aShape.segments_begin(aSpan); 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape::SegmentIterator aSegmentEnd = aShape.segments_end(aSpan); 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape::SegmentIterator bSegment = bShape.segments_begin(bSpan); 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape::SegmentIterator bSegmentEnd = bShape.segments_end(bSpan); 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Look for a non-overlapping part of the spans. If B had a segment in its previous span, then we already tested A against B within that span. 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool aHasSegmentInSpan = aSegment != aSegmentEnd; 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool bHasSegmentInSpan = bSegment != bSegmentEnd; 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (aY < bY && !bHadSegmentInPreviousSpan && aHasSegmentInSpan && CompareOperation::aOutsideB(result)) 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (bY < aY && !aHadSegmentInPreviousSpan && bHasSegmentInSpan && CompareOperation::bOutsideA(result)) 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) aHadSegmentInPreviousSpan = aHasSegmentInSpan; 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bHadSegmentInPreviousSpan = bHasSegmentInSpan; 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool spansOverlap = bMaxY > aY && bY < aMaxY; 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (spansOverlap) { 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (aSegment != aSegmentEnd && bSegment != bSegmentEnd) { 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int aX = *aSegment; 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int aMaxX = *(aSegment + 1); 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int bX = *bSegment; 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int bMaxX = *(bSegment + 1); 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool segmentsOverlap = bMaxX > aX && bX < aMaxX; 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (segmentsOverlap && CompareOperation::aOverlapsB(result)) 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (aX < bX && CompareOperation::aOutsideB(result)) 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (bX < aX && CompareOperation::bOutsideA(result)) 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (aMaxX < bMaxX) 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) aSegment += 2; 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else if (bMaxX < aMaxX) 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bSegment += 2; 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else { 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) aSegment += 2; 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bSegment += 2; 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (aSegment != aSegmentEnd && CompareOperation::aOutsideB(result)) 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 1885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (bSegment != bSegmentEnd && CompareOperation::bOutsideA(result)) 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (aMaxY < bMaxY) 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) aSpan += 1; 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else if (bMaxY < aMaxY) 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bSpan += 1; 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else { 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) aSpan += 1; 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bSpan += 1; 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (aSpan != aSpanEnd && aSpan + 1 != aSpanEnd && CompareOperation::aOutsideB(result)) 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (bSpan != bSpanEnd && bSpan + 1 != bSpanEnd && CompareOperation::bOutsideA(result)) 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct Region::Shape::CompareContainsOperation { 2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const static bool defaultResult = true; 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline static bool aOutsideB(bool& /* result */) { return false; } 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline static bool bOutsideA(bool& result) { result = false; return true; } 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline static bool aOverlapsB(bool& /* result */) { return false; } 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct Region::Shape::CompareIntersectsOperation { 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const static bool defaultResult = false; 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline static bool aOutsideB(bool& /* result */) { return false; } 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline static bool bOutsideA(bool& /* result */) { return false; } 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline static bool aOverlapsB(bool& result) { result = true; return true; } 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape::Shape() 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape::Shape(const IntRect& rect) 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) appendSpan(rect.y()); 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) appendSegment(rect.x()); 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) appendSegment(rect.maxX()); 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) appendSpan(rect.maxY()); 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::Shape::appendSpan(int y) 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_spans.append(Span(y, m_segments.size())); 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)bool Region::Shape::canCoalesce(SegmentIterator begin, SegmentIterator end) 2425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_spans.isEmpty()) 2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator lastSpanBegin = m_segments.data() + m_spans.last().segmentIndex; 2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator lastSpanEnd = m_segments.data() + m_segments.size(); 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Check if both spans have an equal number of segments. 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (lastSpanEnd - lastSpanBegin != end - begin) 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Check if both spans are equal. 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!std::equal(begin, end, lastSpanBegin)) 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Since the segments are equal the second segment can just be ignored. 2585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::Shape::appendSpan(int y, SegmentIterator begin, SegmentIterator end) 2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (canCoalesce(begin, end)) 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 26502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) appendSpan(y); 2675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_segments.appendRange(begin, end); 2685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::Shape::appendSpans(const Shape& shape, SpanIterator begin, SpanIterator end) 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (SpanIterator it = begin; it != end; ++it) 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) appendSpan(it->y, shape.segments_begin(it), shape.segments_end(it)); 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::Shape::appendSegment(int x) 2775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_segments.append(x); 2795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape::SpanIterator Region::Shape::spans_begin() const 2825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_spans.data(); 2845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape::SpanIterator Region::Shape::spans_end() const 2875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_spans.data() + m_spans.size(); 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape::SegmentIterator Region::Shape::segments_begin(SpanIterator it) const 2925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(it >= m_spans.data()); 2945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(it < m_spans.data() + m_spans.size()); 2955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Check if this span has any segments. 2975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (it->segmentIndex == m_segments.size()) 2985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 2995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return &m_segments[it->segmentIndex]; 3015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape::SegmentIterator Region::Shape::segments_end(SpanIterator it) const 3045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 3055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(it >= m_spans.data()); 3065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(it < m_spans.data() + m_spans.size()); 3075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Check if this span has any segments. 3095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (it->segmentIndex == m_segments.size()) 3105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 3115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(it + 1 < m_spans.data() + m_spans.size()); 3135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t segmentIndex = (it + 1)->segmentIndex; 3145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 315926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size()); 3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_segments.data() + segmentIndex; 3175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::Shape::dump() const 3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 3225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (Shape::SpanIterator span = spans_begin(), end = spans_end(); span != end; ++span) { 3235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) printf("%6d: (", span->y); 3245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (Shape::SegmentIterator segment = segments_begin(span), end = segments_end(span); segment != end; ++segment) 3265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) printf("%d ", *segment); 3275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) printf(")\n"); 3285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) printf("\n"); 3315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)IntRect Region::Shape::bounds() const 3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isEmpty()) 3375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return IntRect(); 3385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SpanIterator span = spans_begin(); 3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int minY = span->y; 3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SpanIterator lastSpan = spans_end() - 1; 3435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int maxY = lastSpan->y; 3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int minX = std::numeric_limits<int>::max(); 3465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int maxX = std::numeric_limits<int>::min(); 3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (span != lastSpan) { 3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator firstSegment = segments_begin(span); 3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator lastSegment = segments_end(span) - 1; 3515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (firstSegment && lastSegment) { 3535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(firstSegment != lastSegment); 3545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (*firstSegment < minX) 3565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) minX = *firstSegment; 3575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (*lastSegment > maxX) 3595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) maxX = *lastSegment; 3605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++span; 3635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(minX <= maxX); 3665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(minY <= maxY); 3675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return IntRect(minX, minY, maxX - minX, maxY - minY); 3695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::Shape::translate(const IntSize& offset) 3725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 3735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (size_t i = 0; i < m_segments.size(); ++i) 3745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_segments[i] += offset.width(); 3755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (size_t i = 0; i < m_spans.size(); ++i) 3765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_spans[i].y += offset.height(); 3775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::Shape::swap(Shape& other) 3805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 3815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_segments.swap(other.m_segments); 3825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_spans.swap(other.m_spans); 3835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)enum { 3865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape1, 3875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape2, 3885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 3895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<typename Operation> 3915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& shape2) 3925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 3935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operation::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination); 3945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation::shouldAddRemainingSpansFromShape2), invalid_span_combination); 3955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape result; 3975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Operation::trySimpleOperation(shape1, shape2, result)) 3985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 3995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SpanIterator spans1 = shape1.spans_begin(); 4015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SpanIterator spans1End = shape1.spans_end(); 4025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SpanIterator spans2 = shape2.spans_begin(); 4045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SpanIterator spans2End = shape2.spans_end(); 4055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator segments1 = 0; 4075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator segments1End = 0; 4085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator segments2 = 0; 4105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator segments2End = 0; 4115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Iterate over all spans. 4135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (spans1 != spans1End && spans2 != spans2End) { 4145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int y = 0; 4155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int test = spans1->y - spans2->y; 4165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (test <= 0) { 4185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y = spans1->y; 4195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) segments1 = shape1.segments_begin(spans1); 4215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) segments1End = shape1.segments_end(spans1); 4225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++spans1; 4235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (test >= 0) { 4255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y = spans2->y; 4265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) segments2 = shape2.segments_begin(spans2); 4285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) segments2End = shape2.segments_end(spans2); 4295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++spans2; 4305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int flag = 0; 4335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int oldFlag = 0; 4345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator s1 = segments1; 4365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator s2 = segments2; 4375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<int, 32> segments; 4395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Now iterate over the segments in each span and construct a new vector of segments. 4415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (s1 != segments1End && s2 != segments2End) { 4425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int test = *s1 - *s2; 4435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int x; 4445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (test <= 0) { 4465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = *s1; 4475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) flag = flag ^ 1; 4485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++s1; 4495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (test >= 0) { 4515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = *s2; 4525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) flag = flag ^ 2; 4535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++s2; 4545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (flag == Operation::opCode || oldFlag == Operation::opCode) 4575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) segments.append(x); 45802772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 4595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) oldFlag = flag; 4605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Add any remaining segments. 4635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Operation::shouldAddRemainingSegmentsFromSpan1 && s1 != segments1End) 4645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) segments.appendRange(s1, segments1End); 4655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else if (Operation::shouldAddRemainingSegmentsFromSpan2 && s2 != segments2End) 4665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) segments.appendRange(s2, segments2End); 4675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Add the span. 4695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!segments.isEmpty() || !result.isEmpty()) 4705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result.appendSpan(y, segments.data(), segments.data() + segments.size()); 4715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Add any remaining spans. 4745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End) 4755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result.appendSpans(shape1, spans1, spans1End); 4765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End) 4775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result.appendSpans(shape2, spans2, spans2End); 4785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 4805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct Region::Shape::UnionOperation { 4835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Shape& result) 4845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (shape1.isEmpty()) { 4865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result = shape2; 4875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 4885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 48902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 4905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 4915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int opCode = 0; 4945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSegmentsFromSpan1 = true; 4965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSegmentsFromSpan2 = true; 4975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSpansFromShape1 = true; 4985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSpansFromShape2 = true; 4995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 5005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape Region::Shape::unionShapes(const Shape& shape1, const Shape& shape2) 5025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 5035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return shapeOperation<UnionOperation>(shape1, shape2); 5045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct Region::Shape::IntersectOperation { 5075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool trySimpleOperation(const Shape&, const Shape&, Shape&) 5085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 5105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 51102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int opCode = 3; 51302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSegmentsFromSpan1 = false; 5155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSegmentsFromSpan2 = false; 5165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSpansFromShape1 = false; 5175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSpansFromShape2 = false; 5185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 5195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape Region::Shape::intersectShapes(const Shape& shape1, const Shape& shape2) 5215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 5225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return shapeOperation<IntersectOperation>(shape1, shape2); 5235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct Region::Shape::SubtractOperation { 5265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool trySimpleOperation(const Shape&, const Shape&, Region::Shape&) 5275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 5295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 53002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int opCode = 1; 53202772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSegmentsFromSpan1 = true; 5345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSegmentsFromSpan2 = false; 5355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSpansFromShape1 = true; 5365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSpansFromShape2 = false; 5375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 5385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape Region::Shape::subtractShapes(const Shape& shape1, const Shape& shape2) 5405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 5415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return shapeOperation<SubtractOperation>(shape1, shape2); 5425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 5455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::dump() const 5465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 5475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) printf("Bounds: (%d, %d, %d, %d)\n", 5485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_bounds.x(), m_bounds.y(), m_bounds.width(), m_bounds.height()); 5495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_shape.dump(); 5505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 5525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::intersect(const Region& region) 5545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 5555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_bounds.isEmpty()) 5565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_bounds.intersects(region.m_bounds)) { 5585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_shape = Shape(); 5595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_bounds = IntRect(); 5605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape intersectedShape = Shape::intersectShapes(m_shape, region.m_shape); 5645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_shape.swap(intersectedShape); 5665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_bounds = m_shape.bounds(); 5675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::unite(const Region& region) 5705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 5715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (region.isEmpty()) 5725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isRect() && m_bounds.contains(region.m_bounds)) 5745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (region.isRect() && region.m_bounds.contains(m_bounds)) { 5765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_shape = region.m_shape; 5775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_bounds = region.m_bounds; 5785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // FIXME: We may want another way to construct a Region without doing this test when we expect it to be false. 5815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!isRect() && contains(region)) 5825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape unitedShape = Shape::unionShapes(m_shape, region.m_shape); 5855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_shape.swap(unitedShape); 5875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_bounds.unite(region.m_bounds); 5885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::subtract(const Region& region) 5915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 5925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_bounds.isEmpty()) 5935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (region.isEmpty()) 5955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_bounds.intersects(region.m_bounds)) 5975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape subtractedShape = Shape::subtractShapes(m_shape, region.m_shape); 6005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_shape.swap(subtractedShape); 6025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_bounds = m_shape.bounds(); 6035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 6045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::translate(const IntSize& offset) 6065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 6075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_bounds.move(offset); 6085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_shape.translate(offset); 6095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 6105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace WebCore 612