ui: Create the gfx::QuadF class.

ui: Create the gfx::QuadF class.

This class is composed of four points representing its corners. It does not
have to be axis-aligned, unlike a rectangle. The class supports the following
operations:

IsRectilinear()
- True if the quad is an axis-aligned rectangle.
IsCounterClockwise()
- True if the points of the quad are in counter-clockwise order.
Contains(Point)
- True if Point is inside the quad or on its boundary.
BoundingBox()
- A Rectangle whose edges are defined by the four points of the quad.
Scale()
- Scales each point on the quad by the given scale factors.
operator+/-
- Moves each point in the quad by the given offset.

The operations on this class are inspired by, but not copied from, the
FloatQuad class in WebCore. I've written my own implementation to match those
in WebCore for each of them, with exception of IsRectilinear() as I also
wrote the current method in WebCore.

Tests:
ui_unittests:QuadTest.Construction
ui_unittests:QuadTest.AddingVectors
ui_unittests:QuadTest.IsRectilinear
ui_unittests:QuadTest.IsCounterClockwise
ui_unittests:QuadTest.BoundingBox
ui_unittests:QuadTest.ContainsPoint
ui_unittests:QuadTest.Scale

BUG=147395
R=sky,pkasting

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=165689

[danakj, 2012-11-02 04:55:08]

Context: I made use of this for https://codereview.chromium.org/11364044/

[sky, 2012-11-02 15:49:43]

Just nits, LGTM

https://codereview.chromium.org/11369043/diff/4012/ui/gfx/quad_f.cc
File ui/gfx/quad_f.cc (right):

https://codereview.chromium.org/11369043/diff/4012/ui/gfx/quad_f.cc#newcode60
ui/gfx/quad_f.cc:60: {
{ on previous line.

https://codereview.chromium.org/11369043/diff/4012/ui/gfx/quad_f.cc#newcode67
ui/gfx/quad_f.cc:67: || (WithinEpsilon(p1_.y(), p2_.y()) &&
WithinEpsilon(p2_.x(), p3_.x()) &&
|| on previous line (wrap if you need to).

https://codereview.chromium.org/11369043/diff/4012/ui/gfx/quad_f.h
File ui/gfx/quad_f.h (right):

https://codereview.chromium.org/11369043/diff/4012/ui/gfx/quad_f.h#newcode33
ui/gfx/quad_f.h:33: PointF p1() const { return p1_; }
const PointF&

https://codereview.chromium.org/11369043/diff/4012/ui/gfx/quad_f.h#newcode78
ui/gfx/quad_f.h:78: && lhs.p3() == rhs.p3() && lhs.p4() == rhs.p4();
&& on previous side.

[tfarina, 2012-11-02 15:53:30]

https://codereview.chromium.org/11369043/diff/4012/ui/gfx/quad_f.h
File ui/gfx/quad_f.h (right):

https://codereview.chromium.org/11369043/diff/4012/ui/gfx/quad_f.h#newcode33
ui/gfx/quad_f.h:33: PointF p1() const { return p1_; }
On 2012/11/02 15:49:43, sky wrote:
> const PointF&

See my email to Peter about this.

The subject is: 'gfx::Size type const-refs'

I guess I haven't copied Dana on it though.

[danakj, 2012-11-02 15:54:59]

Thanks :)

https://codereview.chromium.org/11369043/diff/4012/ui/gfx/quad_f.cc
File ui/gfx/quad_f.cc (right):

https://codereview.chromium.org/11369043/diff/4012/ui/gfx/quad_f.cc#newcode60
ui/gfx/quad_f.cc:60: {
On 2012/11/02 15:49:43, sky wrote:
> { on previous line.

Done.

https://codereview.chromium.org/11369043/diff/4012/ui/gfx/quad_f.cc#newcode67
ui/gfx/quad_f.cc:67: || (WithinEpsilon(p1_.y(), p2_.y()) &&
WithinEpsilon(p2_.x(), p3_.x()) &&
On 2012/11/02 15:49:43, sky wrote:
> || on previous line (wrap if you need to).

Done.

https://codereview.chromium.org/11369043/diff/4012/ui/gfx/quad_f.h
File ui/gfx/quad_f.h (right):

https://codereview.chromium.org/11369043/diff/4012/ui/gfx/quad_f.h#newcode33
ui/gfx/quad_f.h:33: PointF p1() const { return p1_; }
On 2012/11/02 15:49:43, sky wrote:
> const PointF&

Done.

https://codereview.chromium.org/11369043/diff/4012/ui/gfx/quad_f.h#newcode78
ui/gfx/quad_f.h:78: && lhs.p3() == rhs.p3() && lhs.p4() == rhs.p4();
On 2012/11/02 15:49:43, sky wrote:
> && on previous side.

Done.

[tfarina, 2012-11-02 15:59:10]

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.h
File ui/gfx/quad_f.h (right):

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.h#newcode78
ui/gfx/quad_f.h:78: lhs.p1() == rhs.p1() && lhs.p2() == rhs.p2() &&
nit: it fits in the previous line, you don't need to wrap and indent 4 spaces.

[Peter Kasting, 2012-11-02 17:54:34]

When you give multiple reviewers, always list what you want each to look at.

Given sky's review, do you still need my review, and if so, what would you like
reviewed, all of it?

[danakj, 2012-11-02 17:58:19]

On 2012/11/02 17:54:34, Peter Kasting wrote:
> When you give multiple reviewers, always list what you want each to look at.
> 
> Given sky's review, do you still need my review, and if so, what would you
like
> reviewed, all of it?

Oh, okay! I figured you'd want to see it at least. I didn't have anything in
particular to look at, but I welcome your input.

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

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.cc
File ui/gfx/quad_f.cc (right):

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.cc#newcode28
ui/gfx/quad_f.cc:28: : p1_(rect.x(), rect.y()),
Nit: could be rect.origin() (2 places)

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.cc#newcode56
ui/gfx/quad_f.cc:56: p4_.ToString().c_str());
Nit: simpler:

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

(Allows killing stringprintf include)

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.cc#newcode59
ui/gfx/quad_f.cc:59: static inline bool WithinEpsilon(float a, float b) {
Nit: Prefer to place in an anonymous namespace atop the file(2 places)

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.cc#newcode60
ui/gfx/quad_f.cc:60: return std::abs(a - b) <
std::numeric_limits<float>::epsilon();
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.

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.cc#newcode73
ui/gfx/quad_f.cc:73: // convex, this will match the result for all other triples
of points as well.
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.

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.cc#newcode107
ui/gfx/quad_f.cc:107: || PointIsInTriangle(point, p1_, p3_, p4_);
Nit: operator goes on end of previous line

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/vector2d_f.h
File ui/gfx/vector2d_f.h (right):

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/vector2d_f.h#newco...
ui/gfx/vector2d_f.h:80: UI_EXPORT double CrossProduct(const Vector2dF& lhs,
const Vector2dF& rhs);
Isn't the cross product a vector?

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

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.cc
File ui/gfx/quad_f.cc (right):

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.cc#newcode28
ui/gfx/quad_f.cc:28: : p1_(rect.x(), rect.y()),
On 2012/11/02 18:09:37, Peter Kasting wrote:
> Nit: could be rect.origin() (2 places)

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

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.cc#newcode60
ui/gfx/quad_f.cc:60: return std::abs(a - b) <
std::numeric_limits<float>::epsilon();
On 2012/11/02 18:09:37, Peter Kasting wrote:
> 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.

#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

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.cc#newcode73
ui/gfx/quad_f.cc:73: // convex, this will match the result for all other triples
of points as well.
On 2012/11/02 18:09:37, Peter Kasting wrote:
> 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.

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.

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/vector2d_f.h
File ui/gfx/vector2d_f.h (right):

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/vector2d_f.h#newco...
ui/gfx/vector2d_f.h:80: UI_EXPORT double CrossProduct(const Vector2dF& lhs,
const Vector2dF& rhs);
On 2012/11/02 18:09:37, Peter Kasting wrote:
> Isn't the cross product a vector?

http://mathworld.wolfram.com/CrossProduct.html

See: "In two dimensions, the analog of the cross product..."

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

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.cc
File ui/gfx/quad_f.cc (right):

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/quad_f.cc#newcode60
ui/gfx/quad_f.cc:60: return std::abs(a - b) <
std::numeric_limits<float>::epsilon();
On 2012/11/02 18:34:10, danakj wrote:
> On 2012/11/02 18:09:37, Peter Kasting wrote:
> > 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.
> 
> #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

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.

[Peter Kasting, 2012-11-02 20:41:46]

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/vector2d_f.h
File ui/gfx/vector2d_f.h (right):

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/vector2d_f.h#newco...
ui/gfx/vector2d_f.h:80: UI_EXPORT double CrossProduct(const Vector2dF& lhs,
const Vector2dF& rhs);
On 2012/11/02 18:34:10, danakj wrote:
> On 2012/11/02 18:09:37, Peter Kasting wrote:
> > Isn't the cross product a vector?
> 
> http://mathworld.wolfram.com/CrossProduct.html
> 
> See: "In two dimensions, the analog of the cross product..."

Maybe we should name the 2d "cross product" "Determinant"?  That might be
clearer, since a 2d "cross product" is just surprising.

[danakj, 2012-11-02 20:44:00]

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/vector2d_f.h
File ui/gfx/vector2d_f.h (right):

https://codereview.chromium.org/11369043/diff/13002/ui/gfx/vector2d_f.h#newco...
ui/gfx/vector2d_f.h:80: UI_EXPORT double CrossProduct(const Vector2dF& lhs,
const Vector2dF& rhs);
On 2012/11/02 20:41:46, Peter Kasting wrote:
> On 2012/11/02 18:34:10, danakj wrote:
> > On 2012/11/02 18:09:37, Peter Kasting wrote:
> > > Isn't the cross product a vector?
> > 
> > http://mathworld.wolfram.com/CrossProduct.html
> > 
> > See: "In two dimensions, the analog of the cross product..."
> 
> Maybe we should name the 2d "cross product" "Determinant"?  That might be
> clearer, since a 2d "cross product" is just surprising.

Well, determinant is only an operation on matrices. If you search for two
dimension cross product you find a few references to this. In particular, in the
description of the Graham Scan algorithm, you also find it. It's a bit of a toss
up, but I do like this one a bit more for these reasons.

[Peter Kasting, 2012-11-02 20:44:54]

On 2012/11/02 20:44:00, danakj wrote:
> https://codereview.chromium.org/11369043/diff/13002/ui/gfx/vector2d_f.h
> File ui/gfx/vector2d_f.h (right):
> 
>
https://codereview.chromium.org/11369043/diff/13002/ui/gfx/vector2d_f.h#newco...
> ui/gfx/vector2d_f.h:80: UI_EXPORT double CrossProduct(const Vector2dF& lhs,
> const Vector2dF& rhs);
> On 2012/11/02 20:41:46, Peter Kasting wrote:
> > On 2012/11/02 18:34:10, danakj wrote:
> > > On 2012/11/02 18:09:37, Peter Kasting wrote:
> > > > Isn't the cross product a vector?
> > > 
> > > http://mathworld.wolfram.com/CrossProduct.html
> > > 
> > > See: "In two dimensions, the analog of the cross product..."
> > 
> > Maybe we should name the 2d "cross product" "Determinant"?  That might be
> > clearer, since a 2d "cross product" is just surprising.
> 
> Well, determinant is only an operation on matrices. If you search for two
> dimension cross product you find a few references to this. In particular, in
the
> description of the Graham Scan algorithm, you also find it. It's a bit of a
toss
> up, but I do like this one a bit more for these reasons.

Yeah, on reflection I agree, leave it.