1 /* 2 * Copyright (C) 2012 Adobe Systems Incorporated. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * 1. Redistributions of source code must retain the above 9 * copyright notice, this list of conditions and the following 10 * disclaimer. 11 * 2. Redistributions in binary form must reproduce the above 12 * copyright notice, this list of conditions and the following 13 * disclaimer in the documentation and/or other materials 14 * provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 19 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 20 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 21 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 23 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 25 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 27 * OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30 #include "config.h" 31 #include "core/rendering/shapes/ShapeInterval.h" 32 33 #include "wtf/MathExtras.h" 34 35 namespace WebCore { 36 37 struct IntervalX1Comparator { 38 bool operator() (const ShapeInterval& i1, const ShapeInterval& i2) const 39 { 40 return i1.x1 < i2.x1; 41 } 42 }; 43 44 bool ShapeInterval::intersect(const ShapeInterval& i, ShapeInterval& rv) const 45 { 46 if (x2 < i.x1 || x1 > i.x2) 47 return false; 48 rv.x1 = std::max(x1, i.x1); 49 rv.x2 = std::min(x2, i.x2); 50 return true; 51 } 52 53 void sortShapeIntervals(Vector<ShapeInterval>& v) 54 { 55 std::sort(v.begin(), v.end(), IntervalX1Comparator()); 56 } 57 58 void mergeShapeIntervals(const Vector<ShapeInterval>& v1, const Vector<ShapeInterval>& v2, Vector<ShapeInterval>& rv) 59 { 60 if (!v1.size()) { 61 rv.appendRange(v2.begin(), v2.end()); 62 } else if (!v2.size()) { 63 rv.appendRange(v1.begin(), v1.end()); 64 } else { 65 Vector<ShapeInterval> v(v1.size() + v2.size()); 66 ShapeInterval* interval = 0; 67 68 std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v.begin(), IntervalX1Comparator()); 69 70 for (size_t i = 0; i < v.size(); i++) { 71 if (!interval) { 72 interval = &v[i]; 73 } else if (v[i].x1 >= interval->x1 && v[i].x1 <= interval->x2) { // FIXME: 1st <= test not needed? 74 interval->x2 = std::max(interval->x2, v[i].x2); 75 } else { 76 rv.append(*interval); 77 interval = &v[i]; 78 } 79 } 80 81 if (interval) 82 rv.append(*interval); 83 } 84 } 85 86 void intersectShapeIntervals(const Vector<ShapeInterval>& v1, const Vector<ShapeInterval>& v2, Vector<ShapeInterval>& rv) 87 { 88 size_t v1Size = v1.size(); 89 size_t v2Size = v2.size(); 90 91 if (!v1Size || !v2Size) 92 return; 93 94 ShapeInterval interval; 95 bool overlap = false; 96 size_t i1 = 0; 97 size_t i2 = 0; 98 99 while (i1 < v1Size && i2 < v2Size) { 100 ShapeInterval v12; 101 if (v1[i1].intersect(v2[i2], v12)) { 102 if (!overlap || !v12.intersect(interval, interval)) { 103 if (overlap) 104 rv.append(interval); 105 interval = v12; 106 overlap = true; 107 } 108 if (v1[i1].x2 < v2[i2].x2) 109 i1++; 110 else 111 i2++; 112 } else { 113 if (overlap) 114 rv.append(interval); 115 overlap = false; 116 if (v1[i1].x1 < v2[i2].x1) 117 i1++; 118 else 119 i2++; 120 } 121 } 122 123 if (overlap) 124 rv.append(interval); 125 } 126 127 void subtractShapeIntervals(const Vector<ShapeInterval>& v1, const Vector<ShapeInterval>& v2, Vector<ShapeInterval>& rv) 128 { 129 size_t v1Size = v1.size(); 130 size_t v2Size = v2.size(); 131 132 if (!v1Size) 133 return; 134 135 if (!v2Size) { 136 rv.appendRange(v1.begin(), v1.end()); 137 } else { 138 size_t i1 = 0, i2 = 0; 139 rv.appendRange(v1.begin(), v1.end()); 140 141 while (i1 < rv.size() && i2 < v2Size) { 142 ShapeInterval& interval1 = rv[i1]; 143 const ShapeInterval& interval2 = v2[i2]; 144 145 if (interval2.x1 <= interval1.x1 && interval2.x2 >= interval1.x2) { 146 rv.remove(i1); 147 } else if (interval2.x2 < interval1.x1) { 148 i2 += 1; 149 } else if (interval2.x1 > interval1.x2) { 150 i1 += 1; 151 } else if (interval2.x1 > interval1.x1 && interval2.x2 < interval1.x2) { 152 rv.insert(i1, ShapeInterval(interval1.x1, interval2.x1)); 153 interval1.x1 = interval2.x2; 154 i2 += 1; 155 } else if (interval2.x1 <= interval1.x1) { 156 interval1.x1 = interval2.x2; 157 i2 += 1; 158 } else { // (interval2.x2 >= interval1.x2) 159 interval1.x2 = interval2.x1; 160 i1 += 1; 161 } 162 } 163 } 164 } 165 166 } // namespace WebCore 167