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" 271e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include "platform/geometry/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) 531e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) for (Shape::SpanIterator span = m_shape.spansBegin(), end = m_shape.spansEnd(); 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) 571e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) for (Shape::SegmentIterator segment = m_shape.segmentsBegin(span), end = m_shape.segmentsEnd(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) 811e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) for (Shape::SpanIterator span = m_shape.spansBegin(), end = m_shape.spansEnd(); 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) 901e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) for (Shape::SegmentIterator segment = m_shape.segmentsBegin(span), end = m_shape.segmentsEnd(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) 1311e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) Shape::SpanIterator aSpan = aShape.spansBegin(); 1321e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) Shape::SpanIterator aSpanEnd = aShape.spansEnd(); 1331e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) Shape::SpanIterator bSpan = bShape.spansBegin(); 1341e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) Shape::SpanIterator bSpanEnd = bShape.spansEnd(); 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) 1441e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) Shape::SegmentIterator aSegment = aShape.segmentsBegin(aSpan); 1451e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) Shape::SegmentIterator aSegmentEnd = aShape.segmentsEnd(aSpan); 1461e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) Shape::SegmentIterator bSegment = bShape.segmentsBegin(bSpan); 1471e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) Shape::SegmentIterator bSegmentEnd = bShape.segmentsEnd(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) 1761e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) if (aMaxX < bMaxX) { 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) aSegment += 2; 1781e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } else if (bMaxX < aMaxX) { 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bSegment += 2; 1801e202183a5dc46166763171984b285173f8585e5Torne (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) 1921e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) if (aMaxY < bMaxY) { 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) aSpan += 1; 1941e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } else if (bMaxY < aMaxY) { 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bSpan += 1; 1961e202183a5dc46166763171984b285173f8585e5Torne (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) 2105d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)void Region::Shape::trimCapacities() 2115d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles){ 2125d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) m_segments.shrinkToReasonableCapacity(); 2135d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) m_spans.shrinkToReasonableCapacity(); 2145d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)} 2155d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct Region::Shape::CompareContainsOperation { 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const static bool defaultResult = true; 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline static bool aOutsideB(bool& /* result */) { return false; } 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline static bool bOutsideA(bool& result) { result = false; return true; } 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline static bool aOverlapsB(bool& /* result */) { return false; } 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct Region::Shape::CompareIntersectsOperation { 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const static bool defaultResult = false; 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline static bool aOutsideB(bool& /* result */) { return false; } 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline static bool bOutsideA(bool& /* result */) { return false; } 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline static bool aOverlapsB(bool& result) { result = true; return true; } 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape::Shape() 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape::Shape(const IntRect& rect) 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) appendSpan(rect.y()); 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) appendSegment(rect.x()); 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) appendSegment(rect.maxX()); 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) appendSpan(rect.maxY()); 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2425d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)Region::Shape::Shape(size_t segmentsCapacity, size_t spansCapacity) 2435d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles){ 2445d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) m_segments.reserveCapacity(segmentsCapacity); 2455d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) m_spans.reserveCapacity(spansCapacity); 2465d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)} 2475d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::Shape::appendSpan(int y) 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_spans.append(Span(y, m_segments.size())); 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)bool Region::Shape::canCoalesce(SegmentIterator begin, SegmentIterator end) 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_spans.isEmpty()) 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator lastSpanBegin = m_segments.data() + m_spans.last().segmentIndex; 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator lastSpanEnd = m_segments.data() + m_segments.size(); 2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Check if both spans have an equal number of segments. 2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (lastSpanEnd - lastSpanBegin != end - begin) 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Check if both spans are equal. 2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!std::equal(begin, end, lastSpanBegin)) 2675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 2685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Since the segments are equal the second segment can just be ignored. 2705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::Shape::appendSpan(int y, SegmentIterator begin, SegmentIterator end) 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (canCoalesce(begin, end)) 2765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 27702772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 2785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) appendSpan(y); 2795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_segments.appendRange(begin, end); 2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::Shape::appendSpans(const Shape& shape, SpanIterator begin, SpanIterator end) 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (SpanIterator it = begin; it != end; ++it) 2851e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) appendSpan(it->y, shape.segmentsBegin(it), shape.segmentsEnd(it)); 2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::Shape::appendSegment(int x) 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_segments.append(x); 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2931e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)Region::Shape::SpanIterator Region::Shape::spansBegin() const 2945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_spans.data(); 2965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2981e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)Region::Shape::SpanIterator Region::Shape::spansEnd() const 2995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 3005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_spans.data() + m_spans.size(); 3015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3031e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)Region::Shape::SegmentIterator Region::Shape::segmentsBegin(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) return &m_segments[it->segmentIndex]; 3135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3151e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)Region::Shape::SegmentIterator Region::Shape::segmentsEnd(SpanIterator it) const 3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 3175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(it >= m_spans.data()); 3185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(it < m_spans.data() + m_spans.size()); 3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Check if this span has any segments. 3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (it->segmentIndex == m_segments.size()) 3225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 3235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(it + 1 < m_spans.data() + m_spans.size()); 3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t segmentIndex = (it + 1)->segmentIndex; 3265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 327926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size()); 3285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_segments.data() + segmentIndex; 3295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::Shape::dump() const 3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 3341e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) for (Shape::SpanIterator span = spansBegin(), end = spansEnd(); span != end; ++span) { 3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) printf("%6d: (", span->y); 3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3371e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) for (Shape::SegmentIterator segment = segmentsBegin(span), end = segmentsEnd(span); segment != end; ++segment) 3385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) printf("%d ", *segment); 3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) printf(")\n"); 3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) printf("\n"); 3435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 3455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)IntRect Region::Shape::bounds() const 3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 3485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isEmpty()) 3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return IntRect(); 3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3511e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) SpanIterator span = spansBegin(); 3525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int minY = span->y; 3535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3541e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) SpanIterator lastSpan = spansEnd() - 1; 3555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int maxY = lastSpan->y; 3565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int minX = std::numeric_limits<int>::max(); 3585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int maxX = std::numeric_limits<int>::min(); 3595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (span != lastSpan) { 3611e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) SegmentIterator firstSegment = segmentsBegin(span); 3621e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) SegmentIterator lastSegment = segmentsEnd(span) - 1; 3635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (firstSegment && lastSegment) { 3655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(firstSegment != lastSegment); 3665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (*firstSegment < minX) 3685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) minX = *firstSegment; 3695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (*lastSegment > maxX) 3715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) maxX = *lastSegment; 3725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++span; 3755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(minX <= maxX); 3785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(minY <= maxY); 3795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return IntRect(minX, minY, maxX - minX, maxY - minY); 3815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::Shape::translate(const IntSize& offset) 3845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 3855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (size_t i = 0; i < m_segments.size(); ++i) 3865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_segments[i] += offset.width(); 3875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (size_t i = 0; i < m_spans.size(); ++i) 3885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_spans[i].y += offset.height(); 3895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::Shape::swap(Shape& other) 3925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 3935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_segments.swap(other.m_segments); 3945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_spans.swap(other.m_spans); 3955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)enum { 3985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape1, 3995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape2, 4005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 4015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<typename Operation> 4035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& shape2) 4045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 4055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operation::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination); 4065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation::shouldAddRemainingSpansFromShape2), invalid_span_combination); 4075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4085d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) size_t segmentsCapacity = shape1.segmentsSize() + shape2.segmentsSize(); 4095d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) size_t spansCapacity = shape1.spansSize() + shape2.spansSize(); 4105d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) Shape result(segmentsCapacity, spansCapacity); 4115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Operation::trySimpleOperation(shape1, shape2, result)) 4125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 4135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4141e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) SpanIterator spans1 = shape1.spansBegin(); 4151e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) SpanIterator spans1End = shape1.spansEnd(); 4165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4171e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) SpanIterator spans2 = shape2.spansBegin(); 4181e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) SpanIterator spans2End = shape2.spansEnd(); 4195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator segments1 = 0; 4215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator segments1End = 0; 4225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator segments2 = 0; 4245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator segments2End = 0; 4255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4265d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) Vector<int, 32> segments; 4275d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) segments.reserveCapacity(std::max(shape1.segmentsSize(), shape2.segmentsSize())); 4285d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) 4295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Iterate over all spans. 4305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (spans1 != spans1End && spans2 != spans2End) { 4315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int y = 0; 4325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int test = spans1->y - spans2->y; 4335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (test <= 0) { 4355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y = spans1->y; 4365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4371e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) segments1 = shape1.segmentsBegin(spans1); 4381e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) segments1End = shape1.segmentsEnd(spans1); 4395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++spans1; 4405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (test >= 0) { 4425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y = spans2->y; 4435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4441e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) segments2 = shape2.segmentsBegin(spans2); 4451e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) segments2End = shape2.segmentsEnd(spans2); 4465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++spans2; 4475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int flag = 0; 4505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int oldFlag = 0; 4515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator s1 = segments1; 4535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SegmentIterator s2 = segments2; 4545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4555d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) // Clear vector without dropping capacity. 4565d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) segments.resize(0); 4575d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) ASSERT(segments.capacity()); 4585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Now iterate over the segments in each span and construct a new vector of segments. 4605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (s1 != segments1End && s2 != segments2End) { 4615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int test = *s1 - *s2; 4625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int x; 4635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (test <= 0) { 4655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = *s1; 4665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) flag = flag ^ 1; 4675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++s1; 4685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (test >= 0) { 4705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = *s2; 4715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) flag = flag ^ 2; 4725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++s2; 4735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (flag == Operation::opCode || oldFlag == Operation::opCode) 4765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) segments.append(x); 47702772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 4785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) oldFlag = flag; 4795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Add any remaining segments. 4825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Operation::shouldAddRemainingSegmentsFromSpan1 && s1 != segments1End) 4835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) segments.appendRange(s1, segments1End); 4845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else if (Operation::shouldAddRemainingSegmentsFromSpan2 && s2 != segments2End) 4855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) segments.appendRange(s2, segments2End); 4865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Add the span. 4885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!segments.isEmpty() || !result.isEmpty()) 4895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result.appendSpan(y, segments.data(), segments.data() + segments.size()); 4905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Add any remaining spans. 4935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End) 4945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result.appendSpans(shape1, spans1, spans1End); 4955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End) 4965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result.appendSpans(shape2, spans2, spans2End); 4975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4985d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) result.trimCapacities(); 4995d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) 5005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 5015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct Region::Shape::UnionOperation { 5045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Shape& result) 5055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (shape1.isEmpty()) { 5075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result = shape2; 5085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 5095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 51002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 5125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int opCode = 0; 5155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSegmentsFromSpan1 = true; 5175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSegmentsFromSpan2 = true; 5185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSpansFromShape1 = true; 5195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSpansFromShape2 = true; 5205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 5215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape Region::Shape::unionShapes(const Shape& shape1, const Shape& shape2) 5235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 5245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return shapeOperation<UnionOperation>(shape1, shape2); 5255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct Region::Shape::IntersectOperation { 5285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool trySimpleOperation(const Shape&, const Shape&, Shape&) 5295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 5315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 53202772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int opCode = 3; 53402772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSegmentsFromSpan1 = false; 5365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSegmentsFromSpan2 = false; 5375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSpansFromShape1 = false; 5385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSpansFromShape2 = false; 5395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 5405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape Region::Shape::intersectShapes(const Shape& shape1, const Shape& shape2) 5425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 5435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return shapeOperation<IntersectOperation>(shape1, shape2); 5445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct Region::Shape::SubtractOperation { 5475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool trySimpleOperation(const Shape&, const Shape&, Region::Shape&) 5485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 5505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 55102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int opCode = 1; 55302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSegmentsFromSpan1 = true; 5555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSegmentsFromSpan2 = false; 5565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSpansFromShape1 = true; 5575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool shouldAddRemainingSpansFromShape2 = false; 5585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 5595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Region::Shape Region::Shape::subtractShapes(const Shape& shape1, const Shape& shape2) 5615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 5625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return shapeOperation<SubtractOperation>(shape1, shape2); 5635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 5665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::dump() const 5675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 5681e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) printf("Bounds: (%d, %d, %d, %d)\n", m_bounds.x(), m_bounds.y(), m_bounds.width(), m_bounds.height()); 5695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_shape.dump(); 5705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 5725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::intersect(const Region& region) 5745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 5755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_bounds.isEmpty()) 5765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_bounds.intersects(region.m_bounds)) { 5785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_shape = Shape(); 5795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_bounds = IntRect(); 5805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape intersectedShape = Shape::intersectShapes(m_shape, region.m_shape); 5845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_shape.swap(intersectedShape); 5865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_bounds = m_shape.bounds(); 5875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::unite(const Region& region) 5905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 5915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (region.isEmpty()) 5925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isRect() && m_bounds.contains(region.m_bounds)) 5945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (region.isRect() && region.m_bounds.contains(m_bounds)) { 5965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_shape = region.m_shape; 5975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_bounds = region.m_bounds; 5985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // FIXME: We may want another way to construct a Region without doing this test when we expect it to be false. 6015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!isRect() && contains(region)) 6025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 6035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape unitedShape = Shape::unionShapes(m_shape, region.m_shape); 6055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_shape.swap(unitedShape); 6075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_bounds.unite(region.m_bounds); 6085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 6095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::subtract(const Region& region) 6115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 6125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_bounds.isEmpty()) 6135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 6145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (region.isEmpty()) 6155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 6165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_bounds.intersects(region.m_bounds)) 6175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 6185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Shape subtractedShape = Shape::subtractShapes(m_shape, region.m_shape); 6205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_shape.swap(subtractedShape); 6225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_bounds = m_shape.bounds(); 6235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 6245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void Region::translate(const IntSize& offset) 6265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 6275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_bounds.move(offset); 6285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_shape.translate(offset); 6295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 6305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace WebCore 632