quad_f.cc 7.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226
  1. // Copyright (c) 2012 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "ui/gfx/geometry/quad_f.h"
  5. #include <limits>
  6. #include "base/strings/stringprintf.h"
  7. #include "ui/gfx/geometry/triangle_f.h"
  8. namespace gfx {
  9. namespace {
  10. PointF RightMostCornerToVector(const RectF& rect, const Vector2dF& vector) {
  11. // Return the corner of the rectangle that if it is to the left of the vector
  12. // would mean all of the rectangle is to the left of the vector.
  13. // The vector here represents the side between two points in a clockwise
  14. // convex polygon.
  15. //
  16. // Q XXX
  17. // QQQ XXX If the lower left corner of X is left of the vector that goes
  18. // QQQ from the top corner of Q to the right corner of Q, then all of X
  19. // Q is left of the vector, and intersection impossible.
  20. //
  21. PointF point;
  22. if (vector.x() >= 0)
  23. point.set_y(rect.bottom());
  24. else
  25. point.set_y(rect.y());
  26. if (vector.y() >= 0)
  27. point.set_x(rect.x());
  28. else
  29. point.set_x(rect.right());
  30. return point;
  31. }
  32. // Tests whether the line is contained by or intersected with the circle.
  33. bool LineIntersectsCircle(const PointF& center,
  34. float radius,
  35. const PointF& p0,
  36. const PointF& p1) {
  37. float x0 = p0.x() - center.x(), y0 = p0.y() - center.y();
  38. float x1 = p1.x() - center.x(), y1 = p1.y() - center.y();
  39. float radius2 = radius * radius;
  40. if ((x0 * x0 + y0 * y0) <= radius2 || (x1 * x1 + y1 * y1) <= radius2)
  41. return true;
  42. if (p0 == p1)
  43. return false;
  44. float a = y0 - y1;
  45. float b = x1 - x0;
  46. float c = x0 * y1 - x1 * y0;
  47. float distance2 = c * c / (a * a + b * b);
  48. // If distance between the center point and the line > the radius,
  49. // the line doesn't cross (or is contained by) the ellipse.
  50. if (distance2 > radius2)
  51. return false;
  52. // The nearest point on the line is between p0 and p1?
  53. float x = -a * c / (a * a + b * b);
  54. float y = -b * c / (a * a + b * b);
  55. return (((x0 <= x && x <= x1) || (x0 >= x && x >= x1)) &&
  56. ((y0 <= y && y <= y1) || (y1 <= y && y <= y0)));
  57. }
  58. } // anonymous namespace
  59. void QuadF::operator=(const RectF& rect) {
  60. p1_ = PointF(rect.x(), rect.y());
  61. p2_ = PointF(rect.right(), rect.y());
  62. p3_ = PointF(rect.right(), rect.bottom());
  63. p4_ = PointF(rect.x(), rect.bottom());
  64. }
  65. std::string QuadF::ToString() const {
  66. return base::StringPrintf("%s;%s;%s;%s",
  67. p1_.ToString().c_str(),
  68. p2_.ToString().c_str(),
  69. p3_.ToString().c_str(),
  70. p4_.ToString().c_str());
  71. }
  72. static inline bool WithinEpsilon(float a, float b) {
  73. return std::abs(a - b) < std::numeric_limits<float>::epsilon();
  74. }
  75. bool QuadF::IsRectilinear() const {
  76. return
  77. (WithinEpsilon(p1_.x(), p2_.x()) && WithinEpsilon(p2_.y(), p3_.y()) &&
  78. WithinEpsilon(p3_.x(), p4_.x()) && WithinEpsilon(p4_.y(), p1_.y())) ||
  79. (WithinEpsilon(p1_.y(), p2_.y()) && WithinEpsilon(p2_.x(), p3_.x()) &&
  80. WithinEpsilon(p3_.y(), p4_.y()) && WithinEpsilon(p4_.x(), p1_.x()));
  81. }
  82. bool QuadF::IsCounterClockwise() const {
  83. // This math computes the signed area of the quad. Positive area
  84. // indicates the quad is clockwise; negative area indicates the quad is
  85. // counter-clockwise. Note carefully: this is backwards from conventional
  86. // math because our geometric space uses screen coordiantes with y-axis
  87. // pointing downards.
  88. // Reference: http://mathworld.wolfram.com/PolygonArea.html.
  89. // The equation can be written:
  90. // Signed area = determinant1 + determinant2 + determinant3 + determinant4
  91. // In practise, Refactoring the computation of adding determinants so that
  92. // reducing the number of operations. The equation is:
  93. // Signed area = element1 + element2 - element3 - element4
  94. float p24 = p2_.y() - p4_.y();
  95. float p31 = p3_.y() - p1_.y();
  96. // Up-cast to double so this cannot overflow.
  97. double element1 = static_cast<double>(p1_.x()) * p24;
  98. double element2 = static_cast<double>(p2_.x()) * p31;
  99. double element3 = static_cast<double>(p3_.x()) * p24;
  100. double element4 = static_cast<double>(p4_.x()) * p31;
  101. return element1 + element2 < element3 + element4;
  102. }
  103. bool QuadF::Contains(const PointF& point) const {
  104. return PointIsInTriangle(point, p1_, p2_, p3_) ||
  105. PointIsInTriangle(point, p1_, p3_, p4_);
  106. }
  107. bool QuadF::ContainsQuad(const QuadF& other) const {
  108. return Contains(other.p1()) && Contains(other.p2()) && Contains(other.p3()) &&
  109. Contains(other.p4());
  110. }
  111. void QuadF::Scale(float x_scale, float y_scale) {
  112. p1_.Scale(x_scale, y_scale);
  113. p2_.Scale(x_scale, y_scale);
  114. p3_.Scale(x_scale, y_scale);
  115. p4_.Scale(x_scale, y_scale);
  116. }
  117. void QuadF::operator+=(const Vector2dF& rhs) {
  118. p1_ += rhs;
  119. p2_ += rhs;
  120. p3_ += rhs;
  121. p4_ += rhs;
  122. }
  123. void QuadF::operator-=(const Vector2dF& rhs) {
  124. p1_ -= rhs;
  125. p2_ -= rhs;
  126. p3_ -= rhs;
  127. p4_ -= rhs;
  128. }
  129. QuadF operator+(const QuadF& lhs, const Vector2dF& rhs) {
  130. QuadF result = lhs;
  131. result += rhs;
  132. return result;
  133. }
  134. QuadF operator-(const QuadF& lhs, const Vector2dF& rhs) {
  135. QuadF result = lhs;
  136. result -= rhs;
  137. return result;
  138. }
  139. bool QuadF::IntersectsRect(const RectF& rect) const {
  140. // For each side of the quad clockwise we check if the rectangle is to the
  141. // left of it since only content on the right can overlap with the quad.
  142. // This only works if the quad is convex.
  143. Vector2dF v1, v2, v3, v4;
  144. // Ensure we use clockwise vectors.
  145. if (IsCounterClockwise()) {
  146. v1 = p4_ - p1_;
  147. v2 = p1_ - p2_;
  148. v3 = p2_ - p3_;
  149. v4 = p3_ - p4_;
  150. } else {
  151. v1 = p2_ - p1_;
  152. v2 = p3_ - p2_;
  153. v3 = p4_ - p3_;
  154. v4 = p1_ - p4_;
  155. }
  156. PointF p = RightMostCornerToVector(rect, v1);
  157. if (CrossProduct(v1, p - p1_) < 0)
  158. return false;
  159. p = RightMostCornerToVector(rect, v2);
  160. if (CrossProduct(v2, p - p2_) < 0)
  161. return false;
  162. p = RightMostCornerToVector(rect, v3);
  163. if (CrossProduct(v3, p - p3_) < 0)
  164. return false;
  165. p = RightMostCornerToVector(rect, v4);
  166. if (CrossProduct(v4, p - p4_) < 0)
  167. return false;
  168. // If not all of the rectangle is outside one of the quad's four sides, then
  169. // that means at least a part of the rectangle is overlapping the quad.
  170. return true;
  171. }
  172. bool QuadF::IntersectsCircle(const PointF& center, float radius) const {
  173. return Contains(center) || LineIntersectsCircle(center, radius, p1_, p2_) ||
  174. LineIntersectsCircle(center, radius, p2_, p3_) ||
  175. LineIntersectsCircle(center, radius, p3_, p4_) ||
  176. LineIntersectsCircle(center, radius, p4_, p1_);
  177. }
  178. bool QuadF::IntersectsEllipse(const PointF& center, const SizeF& radii) const {
  179. // Transform the ellipse to an origin-centered circle whose radius is the
  180. // product of major radius and minor radius. Here we apply the same
  181. // transformation to the quad.
  182. QuadF transformed_quad = *this;
  183. transformed_quad -= center.OffsetFromOrigin();
  184. transformed_quad.Scale(radii.height(), radii.width());
  185. PointF origin_point;
  186. return transformed_quad.IntersectsCircle(origin_point,
  187. radii.height() * radii.width());
  188. }
  189. } // namespace gfx