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 |