ui: Create the gfx::QuadF class.

ui/gfx/quad_f.cc

Index: ui/gfx/quad_f.cc
diff --git a/ui/gfx/quad_f.cc b/ui/gfx/quad_f.cc
new file mode 100644
index 0000000000000000000000000000000000000000..d58d7db16eb38cd85abcb65443ae115914db792f
--- /dev/null
+++ b/ui/gfx/quad_f.cc
@@ -0,0 +1,151 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "ui/gfx/quad_f.h"
+
+#include <cmath>
+#include <limits>
+
+#include "base/stringprintf.h"
+
+namespace gfx {
+
+QuadF::QuadF() {
+}
+
+QuadF::QuadF(const PointF& p1,
+             const PointF& p2,
+             const PointF& p3,
+             const PointF& p4)
+    : p1_(p1),
+      p2_(p2),
+      p3_(p3),
+      p4_(p4) {
+}
+
+QuadF::QuadF(const RectF& rect)
+    : p1_(rect.x(), rect.y()),

[Peter Kasting, 2012/11/02 18:09:37]

Nit: could be rect.origin() (2 places)

[danakj, 2012/11/02 18:34:10]

Ya, I liked the clarity of having each of x(), y(), right(), and bottom() appear
twice.

+      p2_(rect.right(), rect.y()),
+      p3_(rect.right(), rect.bottom()),
+      p4_(rect.x(), rect.bottom()) {
+}
+
+QuadF::~QuadF() {
+}
+
+void QuadF::operator=(const QuadF& quad) {
+  p1_ = quad.p1_;
+  p2_ = quad.p2_;
+  p3_ = quad.p3_;
+  p4_ = quad.p4_;
+}
+
+void QuadF::operator=(const RectF& rect) {
+  p1_ = PointF(rect.x(), rect.y());
+  p2_ = PointF(rect.right(), rect.y());
+  p3_ = PointF(rect.right(), rect.bottom());
+  p4_ = PointF(rect.x(), rect.bottom());
+}
+
+std::string QuadF::ToString() const {
+  return base::StringPrintf("%s;%s;%s;%s",
+                            p1_.ToString().c_str(),
+                            p2_.ToString().c_str(),
+                            p3_.ToString().c_str(),
+                            p4_.ToString().c_str());

[Peter Kasting, 2012/11/02 18:09:37]

Nit: simpler:

  return p1_.ToString() + ";" + p2_.ToString() + ";" + p3_.ToString() + ";" +
      p4_.ToString();

(Allows killing stringprintf include)

+}
+
+static inline bool WithinEpsilon(float a, float b) {

[Peter Kasting, 2012/11/02 18:09:37]

Nit: Prefer to place in an anonymous namespace atop the file(2 places)

+  return std::abs(a - b) < std::numeric_limits<float>::epsilon();

[Peter Kasting, 2012/11/02 18:09:37]

I know very little about floating-point.  Is it even possible for a - b to
return a value greater than zero but smaller than epsilon?  I would have
expected that the value would be exactly zero, epsilon, or some larger number
than epsilon.  Maybe that's wrong.

[danakj, 2012/11/02 18:34:10]

#include <limits>
#include <cmath>
#include <iostream>
int main() {
  float eps = std::numeric_limits<float>::epsilon();
  float a = 0.0000001;
  float b = 0.00000011;
  std::cout << "Epsilon : " << eps << "\n";
  std::cout << "A       : " << a << "\n";
  std::cout << "B       : " << b << "\n";
  std::cout << "Result  : " << std::abs(a - b) << "\n";
  std::cout << "Result==: " << (a == b) << "\n";
  std::cout << "Result <: " << (std::abs(a - b) < eps) << "\n";
  return 0;
}

----

Epsilon : 1.19209e-07
A       : 1e-07
B       : 1.1e-07
Result  : 1e-08
Result==: 0
Result <: 1

[danakj, 2012/11/02 18:38:42]

To further explain this. epsilon is difference to the smallest expressible value
greater than *1* and 1. The granularity of a float changes at different ranges.
This epsilon isn't large enough to catch everything at higher values, but it
does catch everything in the 0-1 range.

+}
+
+bool QuadF::IsRectilinear() const {
+  return
+      (WithinEpsilon(p1_.x(), p2_.x()) && WithinEpsilon(p2_.y(), p3_.y()) &&
+       WithinEpsilon(p3_.x(), p4_.x()) && WithinEpsilon(p4_.y(), p1_.y())) ||
+      (WithinEpsilon(p1_.y(), p2_.y()) && WithinEpsilon(p2_.x(), p3_.x()) &&
+       WithinEpsilon(p3_.y(), p4_.y()) && WithinEpsilon(p4_.x(), p1_.x()));
+}
+
+bool QuadF::IsCounterClockwise() const {
+  // Compute if the first three points turn counter-clockwise. If the quad is
+  // convex, this will match the result for all other triples of points as well.

[Peter Kasting, 2012/11/02 18:09:37]

Should we have some sort of IsConvex() function that this DCHECKs?  It worries
me to have the header say "assumes x" but the code not assert it (and callers
presumably not have an easy way to check it).

Same with the co-linear issue.

[danakj, 2012/11/02 18:34:10]

I thought about this too, but I'm not sure if it is worth the trouble. We don't
have any such checks now and we've been getting on okay, but maybe it would be
good.

I know Shawn likes to think about these sorts of things so I will open a bug
against him and let him think this through.

+  return CrossProduct(p2_ - p1_, p3_ - p2_) < 0;
+}
+
+static inline bool PointIsInTriangle(const PointF& point,
+                                     const PointF& r1,
+                                     const PointF& r2,
+                                     const PointF& r3) {
+  // Compute the barycentric coordinates of |point| relative to the triangle
+  // (r1, r2, r3). This algorithm comes from Christer Ericson's Real-Time
+  // Collision Detection.
+  Vector2dF v0 = r2 - r1;
+  Vector2dF v1 = r3 - r1;
+  Vector2dF v2 = point - r1;
+
+  double dot00 = DotProduct(v0, v0);
+  double dot01 = DotProduct(v0, v1);
+  double dot11 = DotProduct(v1, v1);
+  double dot20 = DotProduct(v2, v0);
+  double dot21 = DotProduct(v2, v1);
+
+  double denom = dot00 * dot11 - dot01 * dot01;
+
+  double v = (dot11 * dot20 - dot01 * dot21) / denom;
+  double w = (dot00 * dot21 - dot01 * dot20) / denom;
+  double u = 1 - v - w;
+
+  // Use the barycentric coordinates to test if |point| is inside the
+  // triangle (r1, r2, r2).
+  return (v >= 0) && (w >= 0) && (u >= 0);
+}
+
+bool QuadF::Contains(const PointF& point) const {
+  return PointIsInTriangle(point, p1_, p2_, p3_)
+      || PointIsInTriangle(point, p1_, p3_, p4_);

[Peter Kasting, 2012/11/02 18:09:37]

Nit: operator goes on end of previous line

+}
+
+RectF QuadF::BoundingBox() const {
+  float rl = std::min(std::min(p1_.x(), p2_.x()), std::min(p3_.x(), p4_.x()));
+  float rr = std::max(std::max(p1_.x(), p2_.x()), std::max(p3_.x(), p4_.x()));
+  float rt = std::min(std::min(p1_.y(), p2_.y()), std::min(p3_.y(), p4_.y()));
+  float rb = std::max(std::max(p1_.y(), p2_.y()), std::max(p3_.y(), p4_.y()));
+  return RectF(rl, rt, rr - rl, rb - rt);
+}
+
+void QuadF::Scale(float x_scale, float y_scale) {
+  p1_ = p1_.Scale(x_scale, y_scale);
+  p2_ = p2_.Scale(x_scale, y_scale);
+  p3_ = p3_.Scale(x_scale, y_scale);
+  p4_ = p4_.Scale(x_scale, y_scale);
+}
+
+void QuadF::operator+=(const Vector2dF& rhs) {
+  p1_ += rhs;
+  p2_ += rhs;
+  p3_ += rhs;
+  p4_ += rhs;
+}
+
+void QuadF::operator-=(const Vector2dF& rhs) {
+  p1_ -= rhs;
+  p2_ -= rhs;
+  p3_ -= rhs;
+  p4_ -= rhs;
+}
+
+QuadF operator+(const QuadF& lhs, const Vector2dF& rhs) {
+  QuadF result = lhs;
+  result += rhs;
+  return result;
+}
+
+QuadF operator-(const QuadF& lhs, const Vector2dF& rhs) {
+  QuadF result = lhs;
+  result -= rhs;
+  return result;
+}
+
+}  // namespace gfx