src/third_party/WebKit/Source/platform/geometry/FloatPolygonTest.cpp

   1 /*
   2  * Copyright (C) 2013 Adobe Systems Incorporated. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * 1. Redistributions of source code must retain the above
   9  *    copyright notice, this list of conditions and the following
  10  *    disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above
  12  *    copyright notice, this list of conditions and the following
  13  *    disclaimer in the documentation and/or other materials
  14  *    provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  19  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  20  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
  21  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  23  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  25  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  27  * OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 #include "config.h"
  31
  32 #include "platform/geometry/FloatPolygon.h"
  33
  34 #include <gtest/gtest.h>
  35
  36 namespace WebCore {
  37
  38 class FloatPolygonTestValue {
  39 public:
  40     FloatPolygonTestValue(const float* coordinates, unsigned coordinatesLength, WindRule fillRule)
  41     {
  42         ASSERT(!(coordinatesLength % 2));
  43         OwnPtr<Vector<FloatPoint> > vertices = adoptPtr(new Vector<FloatPoint>(coordinatesLength / 2));
  44         for (unsigned i = 0; i < coordinatesLength; i += 2)
  45             (*vertices)[i / 2] = FloatPoint(coordinates[i], coordinates[i + 1]);
  46         m_polygon = adoptPtr(new FloatPolygon(vertices.release(), fillRule));
  47     }
  48
  49     const FloatPolygon& polygon() const { return *m_polygon; }
  50
  51 private:
  52     OwnPtr<FloatPolygon> m_polygon;
  53 };
  54
  55 } // namespace WebCore
  56
  57 namespace {
  58
  59 using namespace WebCore;
  60
  61 static bool compareEdgeIndex(const FloatPolygonEdge* edge1, const FloatPolygonEdge* edge2)
  62 {
  63     return edge1->edgeIndex() < edge2->edgeIndex();
  64 }
  65
  66 static Vector<const FloatPolygonEdge*> sortedOverlappingEdges(const FloatPolygon& polygon, float minY, float maxY)
  67 {
  68     Vector<const FloatPolygonEdge*> result;
  69     polygon.overlappingEdges(minY, maxY, result);
  70     std::sort(result.begin(), result.end(), compareEdgeIndex);
  71     return result;
  72 }
  73
  74 #define SIZEOF_ARRAY(p) (sizeof(p) / sizeof(p[0]))
  75
  76 /**
  77  * Checks a right triangle. This test covers all of the trivial FloatPolygon accessors.
  78  *
  79  *                        200,100
  80  *                          /|
  81  *                         / |
  82  *                        /  |
  83  *                       -----
  84  *                 100,200   200,200
  85  */
  86 TEST(FloatPolygonTest, basics)
  87 {
  88     const float triangleCoordinates[] = {200, 100, 200, 200, 100, 200};
  89     FloatPolygonTestValue triangleTestValue(triangleCoordinates, SIZEOF_ARRAY(triangleCoordinates), RULE_NONZERO);
  90     const FloatPolygon& triangle = triangleTestValue.polygon();
  91
  92     EXPECT_EQ(RULE_NONZERO, triangle.fillRule());
  93     EXPECT_FALSE(triangle.isEmpty());
  94
  95     EXPECT_EQ(3u, triangle.numberOfVertices());
  96     EXPECT_EQ(FloatPoint(200, 100), triangle.vertexAt(0));
  97     EXPECT_EQ(FloatPoint(200, 200), triangle.vertexAt(1));
  98     EXPECT_EQ(FloatPoint(100, 200), triangle.vertexAt(2));
  99
 100     EXPECT_EQ(3u, triangle.numberOfEdges());
 101     EXPECT_EQ(FloatPoint(200, 100), triangle.edgeAt(0).vertex1());
 102     EXPECT_EQ(FloatPoint(200, 200), triangle.edgeAt(0).vertex2());
 103     EXPECT_EQ(FloatPoint(200, 200), triangle.edgeAt(1).vertex1());
 104     EXPECT_EQ(FloatPoint(100, 200), triangle.edgeAt(1).vertex2());
 105     EXPECT_EQ(FloatPoint(100, 200), triangle.edgeAt(2).vertex1());
 106     EXPECT_EQ(FloatPoint(200, 100), triangle.edgeAt(2).vertex2());
 107
 108     EXPECT_EQ(0u, triangle.edgeAt(0).vertexIndex1());
 109     EXPECT_EQ(1u, triangle.edgeAt(0).vertexIndex2());
 110     EXPECT_EQ(1u, triangle.edgeAt(1).vertexIndex1());
 111     EXPECT_EQ(2u, triangle.edgeAt(1).vertexIndex2());
 112     EXPECT_EQ(2u, triangle.edgeAt(2).vertexIndex1());
 113     EXPECT_EQ(0u, triangle.edgeAt(2).vertexIndex2());
 114
 115     EXPECT_EQ(200, triangle.edgeAt(0).minX());
 116     EXPECT_EQ(200, triangle.edgeAt(0).maxX());
 117     EXPECT_EQ(100, triangle.edgeAt(1).minX());
 118     EXPECT_EQ(200, triangle.edgeAt(1).maxX());
 119     EXPECT_EQ(100, triangle.edgeAt(2).minX());
 120     EXPECT_EQ(200, triangle.edgeAt(2).maxX());
 121
 122     EXPECT_EQ(100, triangle.edgeAt(0).minY());
 123     EXPECT_EQ(200, triangle.edgeAt(0).maxY());
 124     EXPECT_EQ(200, triangle.edgeAt(1).minY());
 125     EXPECT_EQ(200, triangle.edgeAt(1).maxY());
 126     EXPECT_EQ(100, triangle.edgeAt(2).minY());
 127     EXPECT_EQ(200, triangle.edgeAt(2).maxY());
 128
 129     EXPECT_EQ(0u, triangle.edgeAt(0).edgeIndex());
 130     EXPECT_EQ(1u, triangle.edgeAt(1).edgeIndex());
 131     EXPECT_EQ(2u, triangle.edgeAt(2).edgeIndex());
 132
 133     EXPECT_EQ(2u, triangle.edgeAt(0).previousEdge().edgeIndex());
 134     EXPECT_EQ(1u, triangle.edgeAt(0).nextEdge().edgeIndex());
 135     EXPECT_EQ(0u, triangle.edgeAt(1).previousEdge().edgeIndex());
 136     EXPECT_EQ(2u, triangle.edgeAt(1).nextEdge().edgeIndex());
 137     EXPECT_EQ(1u, triangle.edgeAt(2).previousEdge().edgeIndex());
 138     EXPECT_EQ(0u, triangle.edgeAt(2).nextEdge().edgeIndex());
 139
 140     EXPECT_EQ(FloatRect(100, 100, 100, 100), triangle.boundingBox());
 141
 142     Vector<const FloatPolygonEdge*> resultA = sortedOverlappingEdges(triangle, 100, 200);
 143     EXPECT_EQ(3u, resultA.size());
 144     if (resultA.size() == 3) {
 145         EXPECT_EQ(0u, resultA[0]->edgeIndex());
 146         EXPECT_EQ(1u, resultA[1]->edgeIndex());
 147         EXPECT_EQ(2u, resultA[2]->edgeIndex());
 148     }
 149
 150     Vector<const FloatPolygonEdge*> resultB = sortedOverlappingEdges(triangle, 200, 200);
 151     EXPECT_EQ(3u, resultB.size());
 152     if (resultB.size() == 3) {
 153         EXPECT_EQ(0u, resultB[0]->edgeIndex());
 154         EXPECT_EQ(1u, resultB[1]->edgeIndex());
 155         EXPECT_EQ(2u, resultB[2]->edgeIndex());
 156     }
 157
 158     Vector<const FloatPolygonEdge*> resultC = sortedOverlappingEdges(triangle, 100, 150);
 159     EXPECT_EQ(2u, resultC.size());
 160     if (resultC.size() == 2) {
 161         EXPECT_EQ(0u, resultC[0]->edgeIndex());
 162         EXPECT_EQ(2u, resultC[1]->edgeIndex());
 163     }
 164
 165     Vector<const FloatPolygonEdge*> resultD = sortedOverlappingEdges(triangle, 201, 300);
 166     EXPECT_EQ(0u, resultD.size());
 167
 168     Vector<const FloatPolygonEdge*> resultE = sortedOverlappingEdges(triangle, 98, 99);
 169     EXPECT_EQ(0u, resultE.size());
 170 }
 171
 172 /**
 173  * Tests FloatPolygon::contains() with a right triangle, and fillRule = nonzero.
 174  *
 175  *                        200,100
 176  *                          /|
 177  *                         / |
 178  *                        /  |
 179  *                       -----
 180  *                 100,200   200,200
 181  */
 182 TEST(FloatPolygonTest, triangle_nonzero)
 183 {
 184     const float triangleCoordinates[] = {200, 100, 200, 200, 100, 200};
 185     FloatPolygonTestValue triangleTestValue(triangleCoordinates, SIZEOF_ARRAY(triangleCoordinates), RULE_NONZERO);
 186     const FloatPolygon& triangle = triangleTestValue.polygon();
 187
 188     EXPECT_EQ(RULE_NONZERO, triangle.fillRule());
 189     EXPECT_TRUE(triangle.contains(FloatPoint(200, 100)));
 190     EXPECT_TRUE(triangle.contains(FloatPoint(200, 200)));
 191     EXPECT_TRUE(triangle.contains(FloatPoint(100, 200)));
 192     EXPECT_TRUE(triangle.contains(FloatPoint(150, 150)));
 193     EXPECT_FALSE(triangle.contains(FloatPoint(100, 100)));
 194     EXPECT_FALSE(triangle.contains(FloatPoint(149, 149)));
 195     EXPECT_FALSE(triangle.contains(FloatPoint(150, 200.5)));
 196     EXPECT_FALSE(triangle.contains(FloatPoint(201, 200.5)));
 197 }
 198
 199 /**
 200  * Tests FloatPolygon::contains() with a right triangle, and fillRule = evenodd;
 201  *
 202  *                        200,100
 203  *                          /|
 204  *                         / |
 205  *                        /  |
 206  *                       -----
 207  *                 100,200   200,200
 208  */
 209 TEST(FloatPolygonTest, triangle_evenodd)
 210 {
 211     const float triangleCoordinates[] = {200, 100, 200, 200, 100, 200};
 212     FloatPolygonTestValue triangleTestValue(triangleCoordinates, SIZEOF_ARRAY(triangleCoordinates), RULE_EVENODD);
 213     const FloatPolygon& triangle = triangleTestValue.polygon();
 214
 215     EXPECT_EQ(RULE_EVENODD, triangle.fillRule());
 216     EXPECT_TRUE(triangle.contains(FloatPoint(200, 100)));
 217     EXPECT_TRUE(triangle.contains(FloatPoint(200, 200)));
 218     EXPECT_TRUE(triangle.contains(FloatPoint(100, 200)));
 219     EXPECT_TRUE(triangle.contains(FloatPoint(150, 150)));
 220     EXPECT_FALSE(triangle.contains(FloatPoint(100, 100)));
 221     EXPECT_FALSE(triangle.contains(FloatPoint(149, 149)));
 222     EXPECT_FALSE(triangle.contains(FloatPoint(150, 200.5)));
 223     EXPECT_FALSE(triangle.contains(FloatPoint(201, 200.5)));
 224 }
 225
 226 #define TEST_EMPTY(coordinates)                                                                        \
 227 {                                                                                                      \
 228     FloatPolygonTestValue emptyPolygonTestValue(coordinates, SIZEOF_ARRAY(coordinates), RULE_NONZERO); \
 229     const FloatPolygon& emptyPolygon = emptyPolygonTestValue.polygon();                                \
 230     EXPECT_TRUE(emptyPolygon.isEmpty());                                                               \
 231 }
 232
 233 TEST(FloatPolygonTest, emptyPolygons)
 234 {
 235     const float emptyCoordinates1[] = {0, 0};
 236     TEST_EMPTY(emptyCoordinates1);
 237
 238     const float emptyCoordinates2[] = {0, 0, 1, 1};
 239     TEST_EMPTY(emptyCoordinates2);
 240
 241     const float emptyCoordinates3[] = {0, 0, 1, 1, 2, 2, 3, 3};
 242     TEST_EMPTY(emptyCoordinates3);
 243
 244     const float emptyCoordinates4[] = {0, 0, 1, 1, 2, 2, 3, 3, 1, 1};
 245     TEST_EMPTY(emptyCoordinates4);
 246
 247     const float emptyCoordinates5[] = {0, 0, 0, 1, 0, 2, 0, 3, 0, 1};
 248     TEST_EMPTY(emptyCoordinates5);
 249
 250     const float emptyCoordinates6[] = {0, 0, 1, 0, 2, 0, 3, 0, 1, 0};
 251     TEST_EMPTY(emptyCoordinates6);
 252 }
 253
 254 /*
 255  * Test FloatPolygon::contains() with a trapezoid. The vertices are listed in counter-clockwise order.
 256  *
 257  *        150,100   250,100
 258  *          +----------+
 259  *         /            \
 260  *        /              \
 261  *       +----------------+
 262  *     100,150          300,150
 263  */
 264 TEST(FloatPolygonTest, trapezoid)
 265 {
 266     const float trapezoidCoordinates[] = {100, 150, 300, 150, 250, 100, 150, 100};
 267     FloatPolygonTestValue trapezoidTestValue(trapezoidCoordinates, SIZEOF_ARRAY(trapezoidCoordinates), RULE_EVENODD);
 268     const FloatPolygon& trapezoid = trapezoidTestValue.polygon();
 269
 270     EXPECT_FALSE(trapezoid.isEmpty());
 271     EXPECT_EQ(4u, trapezoid.numberOfVertices());
 272     EXPECT_EQ(FloatRect(100, 100, 200, 50), trapezoid.boundingBox());
 273
 274     EXPECT_TRUE(trapezoid.contains(FloatPoint(150, 100)));
 275     EXPECT_TRUE(trapezoid.contains(FloatPoint(150, 101)));
 276     EXPECT_TRUE(trapezoid.contains(FloatPoint(200, 125)));
 277     EXPECT_FALSE(trapezoid.contains(FloatPoint(149, 100)));
 278     EXPECT_FALSE(trapezoid.contains(FloatPoint(301, 150)));
 279 }
 280
 281
 282 /*
 283  * Test FloatPolygon::contains() with a non-convex rectilinear polygon. The polygon has the same shape
 284  * as the letter "H":
 285  *
 286  *    100,100  150,100   200,100   250,100
 287  *       +--------+        +--------+
 288  *       |        |        |        |
 289  *       |        |        |        |
 290  *       |        +--------+        |
 291  *       |     150,150   200,150    |
 292  *       |                          |
 293  *       |     150,200   200,200    |
 294  *       |        +--------+        |
 295  *       |        |        |        |
 296  *       |        |        |        |
 297  *       +--------+        +--------+
 298  *    100,250  150,250   200,250   250,250
 299  */
 300 TEST(FloatPolygonTest, rectilinear)
 301 {
 302     const float hCoordinates[] = {100, 100, 150, 100, 150, 150, 200, 150, 200, 100, 250, 100, 250, 250, 200, 250, 200, 200, 150, 200, 150, 250, 100, 250};
 303     FloatPolygonTestValue hTestValue(hCoordinates, SIZEOF_ARRAY(hCoordinates), RULE_NONZERO);
 304     const FloatPolygon& h = hTestValue.polygon();
 305
 306     EXPECT_FALSE(h.isEmpty());
 307     EXPECT_EQ(12u, h.numberOfVertices());
 308     EXPECT_EQ(FloatRect(100, 100, 150, 150), h.boundingBox());
 309
 310     EXPECT_TRUE(h.contains(FloatPoint(100, 100)));
 311     EXPECT_TRUE(h.contains(FloatPoint(125, 100)));
 312     EXPECT_TRUE(h.contains(FloatPoint(125, 125)));
 313     EXPECT_TRUE(h.contains(FloatPoint(150, 100)));
 314     EXPECT_TRUE(h.contains(FloatPoint(200, 200)));
 315     EXPECT_TRUE(h.contains(FloatPoint(225, 225)));
 316     EXPECT_TRUE(h.contains(FloatPoint(250, 250)));
 317     EXPECT_TRUE(h.contains(FloatPoint(100, 250)));
 318     EXPECT_TRUE(h.contains(FloatPoint(125, 250)));
 319
 320     EXPECT_FALSE(h.contains(FloatPoint(99, 100)));
 321     EXPECT_FALSE(h.contains(FloatPoint(251, 100)));
 322     EXPECT_FALSE(h.contains(FloatPoint(151, 100)));
 323     EXPECT_FALSE(h.contains(FloatPoint(199, 100)));
 324     EXPECT_FALSE(h.contains(FloatPoint(175, 125)));
 325     EXPECT_FALSE(h.contains(FloatPoint(151, 250)));
 326     EXPECT_FALSE(h.contains(FloatPoint(199, 250)));
 327     EXPECT_FALSE(h.contains(FloatPoint(199, 250)));
 328     EXPECT_FALSE(h.contains(FloatPoint(175, 225)));
 329 }
 330
 331 } // namespace