third_party/blink/renderer/platform/geometry/float_polygon_test.cc - chromium/src - Git at Google

 /*
  * Copyright (C) 2013 Adobe Systems Incorporated. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  *
  * 1. Redistributions of source code must retain the above
  *    copyright notice, this list of conditions and the following
  *    disclaimer.
  * 2. Redistributions in binary form must reproduce the above
  *    copyright notice, this list of conditions and the following
  *    disclaimer in the documentation and/or other materials
  *    provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  * OF THE POSSIBILITY OF SUCH DAMAGE.
  */

 #include "third_party/blink/renderer/platform/geometry/float_polygon.h"

 #include <algorithm>
 #include <memory>
 #include <utility>

 #include "testing/gtest/include/gtest/gtest.h"

 namespace blink {

 class FloatPolygonTestValue {
  public:
   FloatPolygonTestValue(const float* coordinates, unsigned coordinates_length) {
     DCHECK(!(coordinates_length % 2));
     Vector<FloatPoint> vertices(coordinates_length / 2);
     for (unsigned i = 0; i < coordinates_length; i += 2)
       vertices[i / 2] = FloatPoint(coordinates[i], coordinates[i + 1]);
     polygon_ = std::make_unique<FloatPolygon>(std::move(vertices));
   }

   const FloatPolygon& Polygon() const { return *polygon_; }

  private:
   std::unique_ptr<FloatPolygon> polygon_;
 };

 namespace {

 bool CompareEdgeIndex(const FloatPolygonEdge* edge1,
                       const FloatPolygonEdge* edge2) {
   return edge1->EdgeIndex() < edge2->EdgeIndex();
 }

 Vector<const FloatPolygonEdge*>
 SortedOverlappingEdges(const FloatPolygon& polygon, float min_y, float max_y) {
   Vector<const FloatPolygonEdge*> result;
   polygon.OverlappingEdges(min_y, max_y, result);
   std::sort(result.begin(), result.end(), CompareEdgeIndex);
   return result;
 }

 }  // anonymous namespace

 #define SIZEOF_ARRAY(p) (sizeof(p) / sizeof(p[0]))

 /**
  * Checks a right triangle. This test covers all of the trivial FloatPolygon
  * accessors.
  *
  *                        200,100
  *                          /|
  *                         / |
  *                        /  |
  *                       -----
  *                 100,200   200,200
  */
 TEST(FloatPolygonTest, basics) {
   const float kTriangleCoordinates[] = {200, 100, 200, 200, 100, 200};
   FloatPolygonTestValue triangle_test_value(kTriangleCoordinates,
                                             SIZEOF_ARRAY(kTriangleCoordinates));
   const FloatPolygon& triangle = triangle_test_value.Polygon();

   EXPECT_FALSE(triangle.IsEmpty());

   EXPECT_EQ(3u, triangle.NumberOfVertices());
   EXPECT_EQ(FloatPoint(200, 100), triangle.VertexAt(0));
   EXPECT_EQ(FloatPoint(200, 200), triangle.VertexAt(1));
   EXPECT_EQ(FloatPoint(100, 200), triangle.VertexAt(2));

   EXPECT_EQ(3u, triangle.NumberOfEdges());
   EXPECT_EQ(FloatPoint(200, 100), triangle.EdgeAt(0).Vertex1());
   EXPECT_EQ(FloatPoint(200, 200), triangle.EdgeAt(0).Vertex2());
   EXPECT_EQ(FloatPoint(200, 200), triangle.EdgeAt(1).Vertex1());
   EXPECT_EQ(FloatPoint(100, 200), triangle.EdgeAt(1).Vertex2());
   EXPECT_EQ(FloatPoint(100, 200), triangle.EdgeAt(2).Vertex1());
   EXPECT_EQ(FloatPoint(200, 100), triangle.EdgeAt(2).Vertex2());

   EXPECT_EQ(0u, triangle.EdgeAt(0).VertexIndex1());
   EXPECT_EQ(1u, triangle.EdgeAt(0).VertexIndex2());
   EXPECT_EQ(1u, triangle.EdgeAt(1).VertexIndex1());
   EXPECT_EQ(2u, triangle.EdgeAt(1).VertexIndex2());
   EXPECT_EQ(2u, triangle.EdgeAt(2).VertexIndex1());
   EXPECT_EQ(0u, triangle.EdgeAt(2).VertexIndex2());

   EXPECT_EQ(200, triangle.EdgeAt(0).MinX());
   EXPECT_EQ(200, triangle.EdgeAt(0).MaxX());
   EXPECT_EQ(100, triangle.EdgeAt(1).MinX());
   EXPECT_EQ(200, triangle.EdgeAt(1).MaxX());
   EXPECT_EQ(100, triangle.EdgeAt(2).MinX());
   EXPECT_EQ(200, triangle.EdgeAt(2).MaxX());

   EXPECT_EQ(100, triangle.EdgeAt(0).MinY());
   EXPECT_EQ(200, triangle.EdgeAt(0).MaxY());
   EXPECT_EQ(200, triangle.EdgeAt(1).MinY());
   EXPECT_EQ(200, triangle.EdgeAt(1).MaxY());
   EXPECT_EQ(100, triangle.EdgeAt(2).MinY());
   EXPECT_EQ(200, triangle.EdgeAt(2).MaxY());

   EXPECT_EQ(0u, triangle.EdgeAt(0).EdgeIndex());
   EXPECT_EQ(1u, triangle.EdgeAt(1).EdgeIndex());
   EXPECT_EQ(2u, triangle.EdgeAt(2).EdgeIndex());

   EXPECT_EQ(2u, triangle.EdgeAt(0).PreviousEdge().EdgeIndex());
   EXPECT_EQ(1u, triangle.EdgeAt(0).NextEdge().EdgeIndex());
   EXPECT_EQ(0u, triangle.EdgeAt(1).PreviousEdge().EdgeIndex());
   EXPECT_EQ(2u, triangle.EdgeAt(1).NextEdge().EdgeIndex());
   EXPECT_EQ(1u, triangle.EdgeAt(2).PreviousEdge().EdgeIndex());
   EXPECT_EQ(0u, triangle.EdgeAt(2).NextEdge().EdgeIndex());

   EXPECT_EQ(FloatRect(100, 100, 100, 100), triangle.BoundingBox());

   Vector<const FloatPolygonEdge*> result_a =
       SortedOverlappingEdges(triangle, 100, 200);
   EXPECT_EQ(3u, result_a.size());
   if (result_a.size() == 3) {
     EXPECT_EQ(0u, result_a[0]->EdgeIndex());
     EXPECT_EQ(1u, result_a[1]->EdgeIndex());
     EXPECT_EQ(2u, result_a[2]->EdgeIndex());
   }

   Vector<const FloatPolygonEdge*> result_b =
       SortedOverlappingEdges(triangle, 200, 200);
   EXPECT_EQ(3u, result_b.size());
   if (result_b.size() == 3) {
     EXPECT_EQ(0u, result_b[0]->EdgeIndex());
     EXPECT_EQ(1u, result_b[1]->EdgeIndex());
     EXPECT_EQ(2u, result_b[2]->EdgeIndex());
   }

   Vector<const FloatPolygonEdge*> result_c =
       SortedOverlappingEdges(triangle, 100, 150);
   EXPECT_EQ(2u, result_c.size());
   if (result_c.size() == 2) {
     EXPECT_EQ(0u, result_c[0]->EdgeIndex());
     EXPECT_EQ(2u, result_c[1]->EdgeIndex());
   }

   Vector<const FloatPolygonEdge*> result_d =
       SortedOverlappingEdges(triangle, 201, 300);
   EXPECT_EQ(0u, result_d.size());

   Vector<const FloatPolygonEdge*> result_e =
       SortedOverlappingEdges(triangle, 98, 99);
   EXPECT_EQ(0u, result_e.size());
 }

 /**
  * Tests ContainsNonZero and ContainsEvenOdd with a right triangle.
  *
  *                        200,100
  *                          /|
  *                         / |
  *                        /  |
  *                       -----
  *                 100,200   200,200
  */
 TEST(FloatPolygonTest, triangle_nonzero) {
   const float kTriangleCoordinates[] = {200, 100, 200, 200, 100, 200};
   FloatPolygonTestValue triangle_test_value(kTriangleCoordinates,
                                             SIZEOF_ARRAY(kTriangleCoordinates));
   const FloatPolygon& triangle = triangle_test_value.Polygon();

   EXPECT_TRUE(triangle.ContainsNonZero(FloatPoint(200, 100)));
   EXPECT_TRUE(triangle.ContainsNonZero(FloatPoint(200, 200)));
   EXPECT_TRUE(triangle.ContainsNonZero(FloatPoint(100, 200)));
   EXPECT_TRUE(triangle.ContainsNonZero(FloatPoint(150, 150)));
   EXPECT_FALSE(triangle.ContainsNonZero(FloatPoint(100, 100)));
   EXPECT_FALSE(triangle.ContainsNonZero(FloatPoint(149, 149)));
   EXPECT_FALSE(triangle.ContainsNonZero(FloatPoint(150, 200.5)));
   EXPECT_FALSE(triangle.ContainsNonZero(FloatPoint(201, 200.5)));

   EXPECT_TRUE(triangle.ContainsEvenOdd(FloatPoint(200, 100)));
   EXPECT_TRUE(triangle.ContainsEvenOdd(FloatPoint(200, 200)));
   EXPECT_TRUE(triangle.ContainsEvenOdd(FloatPoint(100, 200)));
   EXPECT_TRUE(triangle.ContainsEvenOdd(FloatPoint(150, 150)));
   EXPECT_FALSE(triangle.ContainsEvenOdd(FloatPoint(100, 100)));
   EXPECT_FALSE(triangle.ContainsEvenOdd(FloatPoint(149, 149)));
   EXPECT_FALSE(triangle.ContainsEvenOdd(FloatPoint(150, 200.5)));
   EXPECT_FALSE(triangle.ContainsEvenOdd(FloatPoint(201, 200.5)));
 }

 #define TEST_EMPTY(coordinates)                                                \
   {                                                                            \
     FloatPolygonTestValue empty_polygon_test_value(coordinates,                \
                                                    SIZEOF_ARRAY(coordinates)); \
     const FloatPolygon& empty_polygon = empty_polygon_test_value.Polygon();    \
     EXPECT_TRUE(empty_polygon.IsEmpty());                                      \
   }

 TEST(FloatPolygonTest, emptyPolygons) {
   const float kEmptyCoordinates1[] = {0, 0};
   TEST_EMPTY(kEmptyCoordinates1);

   const float kEmptyCoordinates2[] = {0, 0, 1, 1};
   TEST_EMPTY(kEmptyCoordinates2);

   const float kEmptyCoordinates3[] = {0, 0, 1, 1, 2, 2, 3, 3};
   TEST_EMPTY(kEmptyCoordinates3);

   const float kEmptyCoordinates4[] = {0, 0, 1, 1, 2, 2, 3, 3, 1, 1};
   TEST_EMPTY(kEmptyCoordinates4);

   const float kEmptyCoordinates5[] = {0, 0, 0, 1, 0, 2, 0, 3, 0, 1};
   TEST_EMPTY(kEmptyCoordinates5);

   const float kEmptyCoordinates6[] = {0, 0, 1, 0, 2, 0, 3, 0, 1, 0};
   TEST_EMPTY(kEmptyCoordinates6);
 }

 /*
  * Test FloatPolygon::ContainsEvenOdd() with a trapezoid. The vertices are
  * listed in counter-clockwise order.
  *
  *        150,100   250,100
  *          +----------+
  *         /            \
  *        /              \
  *       +----------------+
  *     100,150          300,150
  */
 TEST(FloatPolygonTest, trapezoid) {
   const float kTrapezoidCoordinates[] = {100, 150, 300, 150,
                                          250, 100, 150, 100};
   FloatPolygonTestValue trapezoid_test_value(
       kTrapezoidCoordinates, SIZEOF_ARRAY(kTrapezoidCoordinates));
   const FloatPolygon& trapezoid = trapezoid_test_value.Polygon();

   EXPECT_FALSE(trapezoid.IsEmpty());
   EXPECT_EQ(4u, trapezoid.NumberOfVertices());
   EXPECT_EQ(FloatRect(100, 100, 200, 50), trapezoid.BoundingBox());

   EXPECT_TRUE(trapezoid.ContainsEvenOdd(FloatPoint(150, 100)));
   EXPECT_TRUE(trapezoid.ContainsEvenOdd(FloatPoint(150, 101)));
   EXPECT_TRUE(trapezoid.ContainsEvenOdd(FloatPoint(200, 125)));
   EXPECT_FALSE(trapezoid.ContainsEvenOdd(FloatPoint(149, 100)));
   EXPECT_FALSE(trapezoid.ContainsEvenOdd(FloatPoint(301, 150)));
 }

 /*
  * Test FloatPolygon::ContainsNonZero() with a non-convex rectilinear polygon.
  * The polygon has the same shape as the letter "H":
  *
  *    100,100  150,100   200,100   250,100
  *       +--------+        +--------+
  *       |        |        |        |
  *       |        |        |        |
  *       |        +--------+        |
  *       |     150,150   200,150    |
  *       |                          |
  *       |     150,200   200,200    |
  *       |        +--------+        |
  *       |        |        |        |
  *       |        |        |        |
  *       +--------+        +--------+
  *    100,250  150,250   200,250   250,250
  */
 TEST(FloatPolygonTest, rectilinear) {
   const float kHCoordinates[] = {100, 100, 150, 100, 150, 150, 200, 150,
                                  200, 100, 250, 100, 250, 250, 200, 250,
                                  200, 200, 150, 200, 150, 250, 100, 250};
   FloatPolygonTestValue h_test_value(kHCoordinates,
                                      SIZEOF_ARRAY(kHCoordinates));
   const FloatPolygon& h = h_test_value.Polygon();

   EXPECT_FALSE(h.IsEmpty());
   EXPECT_EQ(12u, h.NumberOfVertices());
   EXPECT_EQ(FloatRect(100, 100, 150, 150), h.BoundingBox());

   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(100, 100)));
   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(125, 100)));
   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(125, 125)));
   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(150, 100)));
   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(200, 200)));
   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(225, 225)));
   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(250, 250)));
   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(100, 250)));
   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(125, 250)));

   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(99, 100)));
   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(251, 100)));
   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(151, 100)));
   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(199, 100)));
   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(175, 125)));
   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(151, 250)));
   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(199, 250)));
   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(199, 250)));
   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(175, 225)));
 }

 }  // namespace blink
	/*
	* Copyright (C) 2013 Adobe Systems Incorporated. All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	*
	* 1. Redistributions of source code must retain the above
	* copyright notice, this list of conditions and the following
	* disclaimer.
	* 2. Redistributions in binary form must reproduce the above
	* copyright notice, this list of conditions and the following
	* disclaimer in the documentation and/or other materials
	* provided with the distribution.
	*
	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
	* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
	* COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
	* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
	* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
	* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
	* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
	* OF THE POSSIBILITY OF SUCH DAMAGE.
	*/

	#include "third_party/blink/renderer/platform/geometry/float_polygon.h"

	#include <algorithm>
	#include <memory>
	#include <utility>

	#include "testing/gtest/include/gtest/gtest.h"

	namespace blink {

	class FloatPolygonTestValue {
	public:
	FloatPolygonTestValue(const float* coordinates, unsigned coordinates_length) {
	DCHECK(!(coordinates_length % 2));
	Vector<FloatPoint> vertices(coordinates_length / 2);
	for (unsigned i = 0; i < coordinates_length; i += 2)
	vertices[i / 2] = FloatPoint(coordinates[i], coordinates[i + 1]);
	polygon_ = std::make_unique<FloatPolygon>(std::move(vertices));
	}

	const FloatPolygon& Polygon() const { return *polygon_; }

	private:
	std::unique_ptr<FloatPolygon> polygon_;
	};

	namespace {

	bool CompareEdgeIndex(const FloatPolygonEdge* edge1,
	const FloatPolygonEdge* edge2) {
	return edge1->EdgeIndex() < edge2->EdgeIndex();
	}

	Vector<const FloatPolygonEdge*>
	SortedOverlappingEdges(const FloatPolygon& polygon, float min_y, float max_y) {
	Vector<const FloatPolygonEdge*> result;
	polygon.OverlappingEdges(min_y, max_y, result);
	std::sort(result.begin(), result.end(), CompareEdgeIndex);
	return result;
	}

	} // anonymous namespace

	#define SIZEOF_ARRAY(p) (sizeof(p) / sizeof(p[0]))

	/**
	* Checks a right triangle. This test covers all of the trivial FloatPolygon
	* accessors.
	*
	* 200,100
	* /\|
	* / \|
	* / \|
	* -----
	* 100,200 200,200
	*/
	TEST(FloatPolygonTest, basics) {
	const float kTriangleCoordinates[] = {200, 100, 200, 200, 100, 200};
	FloatPolygonTestValue triangle_test_value(kTriangleCoordinates,
	SIZEOF_ARRAY(kTriangleCoordinates));
	const FloatPolygon& triangle = triangle_test_value.Polygon();

	EXPECT_FALSE(triangle.IsEmpty());

	EXPECT_EQ(3u, triangle.NumberOfVertices());
	EXPECT_EQ(FloatPoint(200, 100), triangle.VertexAt(0));
	EXPECT_EQ(FloatPoint(200, 200), triangle.VertexAt(1));
	EXPECT_EQ(FloatPoint(100, 200), triangle.VertexAt(2));

	EXPECT_EQ(3u, triangle.NumberOfEdges());
	EXPECT_EQ(FloatPoint(200, 100), triangle.EdgeAt(0).Vertex1());
	EXPECT_EQ(FloatPoint(200, 200), triangle.EdgeAt(0).Vertex2());
	EXPECT_EQ(FloatPoint(200, 200), triangle.EdgeAt(1).Vertex1());
	EXPECT_EQ(FloatPoint(100, 200), triangle.EdgeAt(1).Vertex2());
	EXPECT_EQ(FloatPoint(100, 200), triangle.EdgeAt(2).Vertex1());
	EXPECT_EQ(FloatPoint(200, 100), triangle.EdgeAt(2).Vertex2());

	EXPECT_EQ(0u, triangle.EdgeAt(0).VertexIndex1());
	EXPECT_EQ(1u, triangle.EdgeAt(0).VertexIndex2());
	EXPECT_EQ(1u, triangle.EdgeAt(1).VertexIndex1());
	EXPECT_EQ(2u, triangle.EdgeAt(1).VertexIndex2());
	EXPECT_EQ(2u, triangle.EdgeAt(2).VertexIndex1());
	EXPECT_EQ(0u, triangle.EdgeAt(2).VertexIndex2());

	EXPECT_EQ(200, triangle.EdgeAt(0).MinX());
	EXPECT_EQ(200, triangle.EdgeAt(0).MaxX());
	EXPECT_EQ(100, triangle.EdgeAt(1).MinX());
	EXPECT_EQ(200, triangle.EdgeAt(1).MaxX());
	EXPECT_EQ(100, triangle.EdgeAt(2).MinX());
	EXPECT_EQ(200, triangle.EdgeAt(2).MaxX());

	EXPECT_EQ(100, triangle.EdgeAt(0).MinY());
	EXPECT_EQ(200, triangle.EdgeAt(0).MaxY());
	EXPECT_EQ(200, triangle.EdgeAt(1).MinY());
	EXPECT_EQ(200, triangle.EdgeAt(1).MaxY());
	EXPECT_EQ(100, triangle.EdgeAt(2).MinY());
	EXPECT_EQ(200, triangle.EdgeAt(2).MaxY());

	EXPECT_EQ(0u, triangle.EdgeAt(0).EdgeIndex());
	EXPECT_EQ(1u, triangle.EdgeAt(1).EdgeIndex());
	EXPECT_EQ(2u, triangle.EdgeAt(2).EdgeIndex());

	EXPECT_EQ(2u, triangle.EdgeAt(0).PreviousEdge().EdgeIndex());
	EXPECT_EQ(1u, triangle.EdgeAt(0).NextEdge().EdgeIndex());
	EXPECT_EQ(0u, triangle.EdgeAt(1).PreviousEdge().EdgeIndex());
	EXPECT_EQ(2u, triangle.EdgeAt(1).NextEdge().EdgeIndex());
	EXPECT_EQ(1u, triangle.EdgeAt(2).PreviousEdge().EdgeIndex());
	EXPECT_EQ(0u, triangle.EdgeAt(2).NextEdge().EdgeIndex());

	EXPECT_EQ(FloatRect(100, 100, 100, 100), triangle.BoundingBox());

	Vector<const FloatPolygonEdge*> result_a =
	SortedOverlappingEdges(triangle, 100, 200);
	EXPECT_EQ(3u, result_a.size());
	if (result_a.size() == 3) {
	EXPECT_EQ(0u, result_a[0]->EdgeIndex());
	EXPECT_EQ(1u, result_a[1]->EdgeIndex());
	EXPECT_EQ(2u, result_a[2]->EdgeIndex());
	}

	Vector<const FloatPolygonEdge*> result_b =
	SortedOverlappingEdges(triangle, 200, 200);
	EXPECT_EQ(3u, result_b.size());
	if (result_b.size() == 3) {
	EXPECT_EQ(0u, result_b[0]->EdgeIndex());
	EXPECT_EQ(1u, result_b[1]->EdgeIndex());
	EXPECT_EQ(2u, result_b[2]->EdgeIndex());
	}

	Vector<const FloatPolygonEdge*> result_c =
	SortedOverlappingEdges(triangle, 100, 150);
	EXPECT_EQ(2u, result_c.size());
	if (result_c.size() == 2) {
	EXPECT_EQ(0u, result_c[0]->EdgeIndex());
	EXPECT_EQ(2u, result_c[1]->EdgeIndex());
	}

	Vector<const FloatPolygonEdge*> result_d =
	SortedOverlappingEdges(triangle, 201, 300);
	EXPECT_EQ(0u, result_d.size());

	Vector<const FloatPolygonEdge*> result_e =
	SortedOverlappingEdges(triangle, 98, 99);
	EXPECT_EQ(0u, result_e.size());
	}

	/**
	* Tests ContainsNonZero and ContainsEvenOdd with a right triangle.
	*
	* 200,100
	* /\|
	* / \|
	* / \|
	* -----
	* 100,200 200,200
	*/
	TEST(FloatPolygonTest, triangle_nonzero) {
	const float kTriangleCoordinates[] = {200, 100, 200, 200, 100, 200};
	FloatPolygonTestValue triangle_test_value(kTriangleCoordinates,
	SIZEOF_ARRAY(kTriangleCoordinates));
	const FloatPolygon& triangle = triangle_test_value.Polygon();

	EXPECT_TRUE(triangle.ContainsNonZero(FloatPoint(200, 100)));
	EXPECT_TRUE(triangle.ContainsNonZero(FloatPoint(200, 200)));
	EXPECT_TRUE(triangle.ContainsNonZero(FloatPoint(100, 200)));
	EXPECT_TRUE(triangle.ContainsNonZero(FloatPoint(150, 150)));
	EXPECT_FALSE(triangle.ContainsNonZero(FloatPoint(100, 100)));
	EXPECT_FALSE(triangle.ContainsNonZero(FloatPoint(149, 149)));
	EXPECT_FALSE(triangle.ContainsNonZero(FloatPoint(150, 200.5)));
	EXPECT_FALSE(triangle.ContainsNonZero(FloatPoint(201, 200.5)));

	EXPECT_TRUE(triangle.ContainsEvenOdd(FloatPoint(200, 100)));
	EXPECT_TRUE(triangle.ContainsEvenOdd(FloatPoint(200, 200)));
	EXPECT_TRUE(triangle.ContainsEvenOdd(FloatPoint(100, 200)));
	EXPECT_TRUE(triangle.ContainsEvenOdd(FloatPoint(150, 150)));
	EXPECT_FALSE(triangle.ContainsEvenOdd(FloatPoint(100, 100)));
	EXPECT_FALSE(triangle.ContainsEvenOdd(FloatPoint(149, 149)));
	EXPECT_FALSE(triangle.ContainsEvenOdd(FloatPoint(150, 200.5)));
	EXPECT_FALSE(triangle.ContainsEvenOdd(FloatPoint(201, 200.5)));
	}

	#define TEST_EMPTY(coordinates) \
	{ \
	FloatPolygonTestValue empty_polygon_test_value(coordinates, \
	SIZEOF_ARRAY(coordinates)); \
	const FloatPolygon& empty_polygon = empty_polygon_test_value.Polygon(); \
	EXPECT_TRUE(empty_polygon.IsEmpty()); \
	}

	TEST(FloatPolygonTest, emptyPolygons) {
	const float kEmptyCoordinates1[] = {0, 0};
	TEST_EMPTY(kEmptyCoordinates1);

	const float kEmptyCoordinates2[] = {0, 0, 1, 1};
	TEST_EMPTY(kEmptyCoordinates2);

	const float kEmptyCoordinates3[] = {0, 0, 1, 1, 2, 2, 3, 3};
	TEST_EMPTY(kEmptyCoordinates3);

	const float kEmptyCoordinates4[] = {0, 0, 1, 1, 2, 2, 3, 3, 1, 1};
	TEST_EMPTY(kEmptyCoordinates4);

	const float kEmptyCoordinates5[] = {0, 0, 0, 1, 0, 2, 0, 3, 0, 1};
	TEST_EMPTY(kEmptyCoordinates5);

	const float kEmptyCoordinates6[] = {0, 0, 1, 0, 2, 0, 3, 0, 1, 0};
	TEST_EMPTY(kEmptyCoordinates6);
	}

	/*
	* Test FloatPolygon::ContainsEvenOdd() with a trapezoid. The vertices are
	* listed in counter-clockwise order.
	*
	* 150,100 250,100
	* +----------+
	* / \
	* / \
	* +----------------+
	* 100,150 300,150
	*/
	TEST(FloatPolygonTest, trapezoid) {
	const float kTrapezoidCoordinates[] = {100, 150, 300, 150,
	250, 100, 150, 100};
	FloatPolygonTestValue trapezoid_test_value(
	kTrapezoidCoordinates, SIZEOF_ARRAY(kTrapezoidCoordinates));
	const FloatPolygon& trapezoid = trapezoid_test_value.Polygon();

	EXPECT_FALSE(trapezoid.IsEmpty());
	EXPECT_EQ(4u, trapezoid.NumberOfVertices());
	EXPECT_EQ(FloatRect(100, 100, 200, 50), trapezoid.BoundingBox());

	EXPECT_TRUE(trapezoid.ContainsEvenOdd(FloatPoint(150, 100)));
	EXPECT_TRUE(trapezoid.ContainsEvenOdd(FloatPoint(150, 101)));
	EXPECT_TRUE(trapezoid.ContainsEvenOdd(FloatPoint(200, 125)));
	EXPECT_FALSE(trapezoid.ContainsEvenOdd(FloatPoint(149, 100)));
	EXPECT_FALSE(trapezoid.ContainsEvenOdd(FloatPoint(301, 150)));
	}

	/*
	* Test FloatPolygon::ContainsNonZero() with a non-convex rectilinear polygon.
	* The polygon has the same shape as the letter "H":
	*
	* 100,100 150,100 200,100 250,100
	* +--------+ +--------+
	* \| \| \| \|
	* \| \| \| \|
	* \| +--------+ \|
	* \| 150,150 200,150 \|
	* \| \|
	* \| 150,200 200,200 \|
	* \| +--------+ \|
	* \| \| \| \|
	* \| \| \| \|
	* +--------+ +--------+
	* 100,250 150,250 200,250 250,250
	*/
	TEST(FloatPolygonTest, rectilinear) {
	const float kHCoordinates[] = {100, 100, 150, 100, 150, 150, 200, 150,
	200, 100, 250, 100, 250, 250, 200, 250,
	200, 200, 150, 200, 150, 250, 100, 250};
	FloatPolygonTestValue h_test_value(kHCoordinates,
	SIZEOF_ARRAY(kHCoordinates));
	const FloatPolygon& h = h_test_value.Polygon();

	EXPECT_FALSE(h.IsEmpty());
	EXPECT_EQ(12u, h.NumberOfVertices());
	EXPECT_EQ(FloatRect(100, 100, 150, 150), h.BoundingBox());

	EXPECT_TRUE(h.ContainsNonZero(FloatPoint(100, 100)));
	EXPECT_TRUE(h.ContainsNonZero(FloatPoint(125, 100)));
	EXPECT_TRUE(h.ContainsNonZero(FloatPoint(125, 125)));
	EXPECT_TRUE(h.ContainsNonZero(FloatPoint(150, 100)));
	EXPECT_TRUE(h.ContainsNonZero(FloatPoint(200, 200)));
	EXPECT_TRUE(h.ContainsNonZero(FloatPoint(225, 225)));
	EXPECT_TRUE(h.ContainsNonZero(FloatPoint(250, 250)));
	EXPECT_TRUE(h.ContainsNonZero(FloatPoint(100, 250)));
	EXPECT_TRUE(h.ContainsNonZero(FloatPoint(125, 250)));

	EXPECT_FALSE(h.ContainsNonZero(FloatPoint(99, 100)));
	EXPECT_FALSE(h.ContainsNonZero(FloatPoint(251, 100)));
	EXPECT_FALSE(h.ContainsNonZero(FloatPoint(151, 100)));
	EXPECT_FALSE(h.ContainsNonZero(FloatPoint(199, 100)));
	EXPECT_FALSE(h.ContainsNonZero(FloatPoint(175, 125)));
	EXPECT_FALSE(h.ContainsNonZero(FloatPoint(151, 250)));
	EXPECT_FALSE(h.ContainsNonZero(FloatPoint(199, 250)));
	EXPECT_FALSE(h.ContainsNonZero(FloatPoint(199, 250)));
	EXPECT_FALSE(h.ContainsNonZero(FloatPoint(175, 225)));
	}

	} // namespace blink