| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2008 Apple Inc. All rights reserved. | 2 * Copyright (C) 2008 Apple Inc. All rights reserved. |
| 3 * Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies) | 3 * Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies) |
| 4 * Copyright (C) 2013 Xidorn Quan (quanxunzhen@gmail.com) | 4 * Copyright (C) 2013 Xidorn Quan (quanxunzhen@gmail.com) |
| 5 * | 5 * |
| 6 * Redistribution and use in source and binary forms, with or without | 6 * Redistribution and use in source and binary forms, with or without |
| 7 * modification, are permitted provided that the following conditions | 7 * modification, are permitted provided that the following conditions |
| 8 * are met: | 8 * are met: |
| 9 * | 9 * |
| 10 * 1. Redistributions of source code must retain the above copyright | 10 * 1. Redistributions of source code must retain the above copyright |
| (...skipping 115 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 126 // Note that we only handle convex quads here. | 126 // Note that we only handle convex quads here. |
| 127 bool FloatQuad::containsQuad(const FloatQuad& other) const { | 127 bool FloatQuad::containsQuad(const FloatQuad& other) const { |
| 128 return containsPoint(other.p1()) && containsPoint(other.p2()) && | 128 return containsPoint(other.p1()) && containsPoint(other.p2()) && |
| 129 containsPoint(other.p3()) && containsPoint(other.p4()); | 129 containsPoint(other.p3()) && containsPoint(other.p4()); |
| 130 } | 130 } |
| 131 | 131 |
| 132 static inline FloatPoint rightMostCornerToVector(const FloatRect& rect, | 132 static inline FloatPoint rightMostCornerToVector(const FloatRect& rect, |
| 133 const FloatSize& vector) { | 133 const FloatSize& vector) { |
| 134 // Return the corner of the rectangle that if it is to the left of the vector | 134 // Return the corner of the rectangle that if it is to the left of the vector |
| 135 // would mean all of the rectangle is to the left of the vector. | 135 // would mean all of the rectangle is to the left of the vector. |
| 136 // The vector here represents the side between two points in a clockwise conve
x polygon. | 136 // The vector here represents the side between two points in a clockwise |
| 137 // convex polygon. |
| 137 // | 138 // |
| 138 // Q XXX | 139 // Q XXX |
| 139 // QQQ XXX If the lower left corner of X is left of the vector that goes fro
m the top corner of Q to | 140 // QQQ XXX If the lower left corner of X is left of the vector that goes |
| 140 // QQQ the right corner of Q, then all of X is left of the vector, and i
ntersection impossible. | 141 // QQQ from the top corner of Q to the right corner of Q, then all of X |
| 141 // Q | 142 // Q is left of the vector, and intersection impossible. |
| 142 // | 143 // |
| 143 FloatPoint point; | 144 FloatPoint point; |
| 144 if (vector.width() >= 0) | 145 if (vector.width() >= 0) |
| 145 point.setY(rect.maxY()); | 146 point.setY(rect.maxY()); |
| 146 else | 147 else |
| 147 point.setY(rect.y()); | 148 point.setY(rect.y()); |
| 148 if (vector.height() >= 0) | 149 if (vector.height() >= 0) |
| 149 point.setX(rect.x()); | 150 point.setX(rect.x()); |
| 150 else | 151 else |
| 151 point.setX(rect.maxX()); | 152 point.setX(rect.maxX()); |
| 152 return point; | 153 return point; |
| 153 } | 154 } |
| 154 | 155 |
| 155 bool FloatQuad::intersectsRect(const FloatRect& rect) const { | 156 bool FloatQuad::intersectsRect(const FloatRect& rect) const { |
| 156 // For each side of the quad clockwise we check if the rectangle is to the lef
t of it | 157 // For each side of the quad clockwise we check if the rectangle is to the |
| 157 // since only content on the right can onlap with the quad. | 158 // left of it since only content on the right can onlap with the quad. This |
| 158 // This only works if the quad is convex. | 159 // only works if the quad is convex. |
| 159 FloatSize v1, v2, v3, v4; | 160 FloatSize v1, v2, v3, v4; |
| 160 | 161 |
| 161 // Ensure we use clockwise vectors. | 162 // Ensure we use clockwise vectors. |
| 162 if (!isCounterclockwise()) { | 163 if (!isCounterclockwise()) { |
| 163 v1 = m_p2 - m_p1; | 164 v1 = m_p2 - m_p1; |
| 164 v2 = m_p3 - m_p2; | 165 v2 = m_p3 - m_p2; |
| 165 v3 = m_p4 - m_p3; | 166 v3 = m_p4 - m_p3; |
| 166 v4 = m_p1 - m_p4; | 167 v4 = m_p1 - m_p4; |
| 167 } else { | 168 } else { |
| 168 v1 = m_p4 - m_p1; | 169 v1 = m_p4 - m_p1; |
| (...skipping 11 matching lines...) Expand all Loading... |
| 180 return false; | 181 return false; |
| 181 | 182 |
| 182 p = rightMostCornerToVector(rect, v3); | 183 p = rightMostCornerToVector(rect, v3); |
| 183 if (determinant(v3, p - m_p3) < 0) | 184 if (determinant(v3, p - m_p3) < 0) |
| 184 return false; | 185 return false; |
| 185 | 186 |
| 186 p = rightMostCornerToVector(rect, v4); | 187 p = rightMostCornerToVector(rect, v4); |
| 187 if (determinant(v4, p - m_p4) < 0) | 188 if (determinant(v4, p - m_p4) < 0) |
| 188 return false; | 189 return false; |
| 189 | 190 |
| 190 // If not all of the rectangle is outside one of the quad's four sides, then t
hat means at least | 191 // If not all of the rectangle is outside one of the quad's four sides, then |
| 191 // a part of the rectangle is overlapping the quad. | 192 // that means at least a part of the rectangle is overlapping the quad. |
| 192 return true; | 193 return true; |
| 193 } | 194 } |
| 194 | 195 |
| 195 // Tests whether the line is contained by or intersected with the circle. | 196 // Tests whether the line is contained by or intersected with the circle. |
| 196 static inline bool lineIntersectsCircle(const FloatPoint& center, | 197 static inline bool lineIntersectsCircle(const FloatPoint& center, |
| 197 float radius, | 198 float radius, |
| 198 const FloatPoint& p0, | 199 const FloatPoint& p0, |
| 199 const FloatPoint& p1) { | 200 const FloatPoint& p1) { |
| 200 float x0 = p0.x() - center.x(), y0 = p0.y() - center.y(); | 201 float x0 = p0.x() - center.x(), y0 = p0.y() - center.y(); |
| 201 float x1 = p1.x() - center.x(), y1 = p1.y() - center.y(); | 202 float x1 = p1.x() - center.x(), y1 = p1.y() - center.y(); |
| (...skipping 24 matching lines...) Expand all Loading... |
| 226 return containsPoint( | 227 return containsPoint( |
| 227 center) // The circle may be totally contained by the quad. | 228 center) // The circle may be totally contained by the quad. |
| 228 || lineIntersectsCircle(center, radius, m_p1, m_p2) || | 229 || lineIntersectsCircle(center, radius, m_p1, m_p2) || |
| 229 lineIntersectsCircle(center, radius, m_p2, m_p3) || | 230 lineIntersectsCircle(center, radius, m_p2, m_p3) || |
| 230 lineIntersectsCircle(center, radius, m_p3, m_p4) || | 231 lineIntersectsCircle(center, radius, m_p3, m_p4) || |
| 231 lineIntersectsCircle(center, radius, m_p4, m_p1); | 232 lineIntersectsCircle(center, radius, m_p4, m_p1); |
| 232 } | 233 } |
| 233 | 234 |
| 234 bool FloatQuad::intersectsEllipse(const FloatPoint& center, | 235 bool FloatQuad::intersectsEllipse(const FloatPoint& center, |
| 235 const FloatSize& radii) const { | 236 const FloatSize& radii) const { |
| 236 // Transform the ellipse to an origin-centered circle whose radius is the prod
uct of major radius and minor radius. | 237 // Transform the ellipse to an origin-centered circle whose radius is the |
| 237 // Here we apply the same transformation to the quad. | 238 // product of major radius and minor radius. Here we apply the same |
| 239 // transformation to the quad. |
| 238 FloatQuad transformedQuad(*this); | 240 FloatQuad transformedQuad(*this); |
| 239 transformedQuad.move(-center.x(), -center.y()); | 241 transformedQuad.move(-center.x(), -center.y()); |
| 240 transformedQuad.scale(radii.height(), radii.width()); | 242 transformedQuad.scale(radii.height(), radii.width()); |
| 241 | 243 |
| 242 FloatPoint originPoint; | 244 FloatPoint originPoint; |
| 243 return transformedQuad.intersectsCircle(originPoint, | 245 return transformedQuad.intersectsCircle(originPoint, |
| 244 radii.height() * radii.width()); | 246 radii.height() * radii.width()); |
| 245 } | 247 } |
| 246 | 248 |
| 247 bool FloatQuad::isCounterclockwise() const { | 249 bool FloatQuad::isCounterclockwise() const { |
| 248 // Return if the two first vectors are turning clockwise. If the quad is conve
x then all following vectors will turn the same way. | 250 // Return if the two first vectors are turning clockwise. If the quad is |
| 251 // convex then all following vectors will turn the same way. |
| 249 return determinant(m_p2 - m_p1, m_p3 - m_p2) < 0; | 252 return determinant(m_p2 - m_p1, m_p3 - m_p2) < 0; |
| 250 } | 253 } |
| 251 | 254 |
| 252 String FloatQuad::toString() const { | 255 String FloatQuad::toString() const { |
| 253 return String::format("%s; %s; %s; %s", m_p1.toString().ascii().data(), | 256 return String::format("%s; %s; %s; %s", m_p1.toString().ascii().data(), |
| 254 m_p2.toString().ascii().data(), | 257 m_p2.toString().ascii().data(), |
| 255 m_p3.toString().ascii().data(), | 258 m_p3.toString().ascii().data(), |
| 256 m_p4.toString().ascii().data()); | 259 m_p4.toString().ascii().data()); |
| 257 } | 260 } |
| 258 | 261 |
| 259 } // namespace blink | 262 } // namespace blink |
| OLD | NEW |