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 #include "platform/geometry/FloatPolygon.h"
  32
  33 #include <gtest/gtest.h>
  34
  35 namespace blink {
  36
  37 class FloatPolygonTestValue {
  38 public:
  39     FloatPolygonTestValue(const float* coordinates, unsigned coordinatesLength, WindRule fillRule)
  40     {
  41         ASSERT(!(coordinatesLength % 2));
  42         OwnPtr<Vector<FloatPoint>> vertices = adoptPtr(new Vector<FloatPoint>(coordinatesLength / 2));
  43         for (unsigned i = 0; i < coordinatesLength; i += 2)
  44             (*vertices)[i / 2] = FloatPoint(coordinates[i], coordinates[i + 1]);
  45         m_polygon = adoptPtr(new FloatPolygon(vertices.release(), fillRule));
  46     }
  47
  48     const FloatPolygon& polygon() const { return *m_polygon; }
  49
  50 private:
  51     OwnPtr<FloatPolygon> m_polygon;
  52 };
  53
  54 namespace {
  55
  56 bool compareEdgeIndex(const FloatPolygonEdge* edge1, const FloatPolygonEdge* edge2)
  57 {
  58     return edge1->edgeIndex() < edge2->edgeIndex();
  59 }
  60
  61 Vector<const FloatPolygonEdge*> sortedOverlappingEdges(const FloatPolygon& polygon, float minY, float maxY)
  62 {
  63     Vector<const FloatPolygonEdge*> result;
  64     polygon.overlappingEdges(minY, maxY, result);
  65     std::sort(result.begin(), result.end(), compareEdgeIndex);
  66     return result;
  67 }
  68
  69 } // anonymous namespace
  70
  71 #define SIZEOF_ARRAY(p) (sizeof(p) / sizeof(p[0]))
  72
  73 /**
  74  * Checks a right triangle. This test covers all of the trivial FloatPolygon accessors.
  75  *
  76  *                        200,100
  77  *                          /|
  78  *                         / |
  79  *                        /  |
  80  *                       -----
  81  *                 100,200   200,200
  82  */
  83 TEST(FloatPolygonTest, basics)
  84 {
  85     const float triangleCoordinates[] = {200, 100, 200, 200, 100, 200};
  86     FloatPolygonTestValue triangleTestValue(triangleCoordinates, SIZEOF_ARRAY(triangleCoordinates), RULE_NONZERO);
  87     const FloatPolygon& triangle = triangleTestValue.polygon();
  88
  89     EXPECT_EQ(RULE_NONZERO, triangle.fillRule());
  90     EXPECT_FALSE(triangle.isEmpty());
  91
  92     EXPECT_EQ(3u, triangle.numberOfVertices());
  93     EXPECT_EQ(FloatPoint(200, 100), triangle.vertexAt(0));
  94     EXPECT_EQ(FloatPoint(200, 200), triangle.vertexAt(1));
  95     EXPECT_EQ(FloatPoint(100, 200), triangle.vertexAt(2));
  96
  97     EXPECT_EQ(3u, triangle.numberOfEdges());
  98     EXPECT_EQ(FloatPoint(200, 100), triangle.edgeAt(0).vertex1());
  99     EXPECT_EQ(FloatPoint(200, 200), triangle.edgeAt(0).vertex2());
 100     EXPECT_EQ(FloatPoint(200, 200), triangle.edgeAt(1).vertex1());
 101     EXPECT_EQ(FloatPoint(100, 200), triangle.edgeAt(1).vertex2());
 102     EXPECT_EQ(FloatPoint(100, 200), triangle.edgeAt(2).vertex1());
 103     EXPECT_EQ(FloatPoint(200, 100), triangle.edgeAt(2).vertex2());
 104
 105     EXPECT_EQ(0u, triangle.edgeAt(0).vertexIndex1());
 106     EXPECT_EQ(1u, triangle.edgeAt(0).vertexIndex2());
 107     EXPECT_EQ(1u, triangle.edgeAt(1).vertexIndex1());
 108     EXPECT_EQ(2u, triangle.edgeAt(1).vertexIndex2());
 109     EXPECT_EQ(2u, triangle.edgeAt(2).vertexIndex1());
 110     EXPECT_EQ(0u, triangle.edgeAt(2).vertexIndex2());
 111
 112     EXPECT_EQ(200, triangle.edgeAt(0).minX());
 113     EXPECT_EQ(200, triangle.edgeAt(0).maxX());
 114     EXPECT_EQ(100, triangle.edgeAt(1).minX());
 115     EXPECT_EQ(200, triangle.edgeAt(1).maxX());
 116     EXPECT_EQ(100, triangle.edgeAt(2).minX());
 117     EXPECT_EQ(200, triangle.edgeAt(2).maxX());
 118
 119     EXPECT_EQ(100, triangle.edgeAt(0).minY());
 120     EXPECT_EQ(200, triangle.edgeAt(0).maxY());
 121     EXPECT_EQ(200, triangle.edgeAt(1).minY());
 122     EXPECT_EQ(200, triangle.edgeAt(1).maxY());
 123     EXPECT_EQ(100, triangle.edgeAt(2).minY());
 124     EXPECT_EQ(200, triangle.edgeAt(2).maxY());
 125
 126     EXPECT_EQ(0u, triangle.edgeAt(0).edgeIndex());
 127     EXPECT_EQ(1u, triangle.edgeAt(1).edgeIndex());
 128     EXPECT_EQ(2u, triangle.edgeAt(2).edgeIndex());
 129
 130     EXPECT_EQ(2u, triangle.edgeAt(0).previousEdge().edgeIndex());
 131     EXPECT_EQ(1u, triangle.edgeAt(0).nextEdge().edgeIndex());
 132     EXPECT_EQ(0u, triangle.edgeAt(1).previousEdge().edgeIndex());
 133     EXPECT_EQ(2u, triangle.edgeAt(1).nextEdge().edgeIndex());
 134     EXPECT_EQ(1u, triangle.edgeAt(2).previousEdge().edgeIndex());
 135     EXPECT_EQ(0u, triangle.edgeAt(2).nextEdge().edgeIndex());
 136
 137     EXPECT_EQ(FloatRect(100, 100, 100, 100), triangle.boundingBox());
 138
 139     Vector<const FloatPolygonEdge*> resultA = sortedOverlappingEdges(triangle, 100, 200);
 140     EXPECT_EQ(3u, resultA.size());
 141     if (resultA.size() == 3) {
 142         EXPECT_EQ(0u, resultA[0]->edgeIndex());
 143         EXPECT_EQ(1u, resultA[1]->edgeIndex());
 144         EXPECT_EQ(2u, resultA[2]->edgeIndex());
 145     }
 146
 147     Vector<const FloatPolygonEdge*> resultB = sortedOverlappingEdges(triangle, 200, 200);
 148     EXPECT_EQ(3u, resultB.size());
 149     if (resultB.size() == 3) {
 150         EXPECT_EQ(0u, resultB[0]->edgeIndex());
 151         EXPECT_EQ(1u, resultB[1]->edgeIndex());
 152         EXPECT_EQ(2u, resultB[2]->edgeIndex());
 153     }
 154
 155     Vector<const FloatPolygonEdge*> resultC = sortedOverlappingEdges(triangle, 100, 150);
 156     EXPECT_EQ(2u, resultC.size());
 157     if (resultC.size() == 2) {
 158         EXPECT_EQ(0u, resultC[0]->edgeIndex());
 159         EXPECT_EQ(2u, resultC[1]->edgeIndex());
 160     }
 161
 162     Vector<const FloatPolygonEdge*> resultD = sortedOverlappingEdges(triangle, 201, 300);
 163     EXPECT_EQ(0u, resultD.size());
 164
 165     Vector<const FloatPolygonEdge*> resultE = sortedOverlappingEdges(triangle, 98, 99);
 166     EXPECT_EQ(0u, resultE.size());
 167 }
 168
 169 /**
 170  * Tests FloatPolygon::contains() with a right triangle, and fillRule = nonzero.
 171  *
 172  *                        200,100
 173  *                          /|
 174  *                         / |
 175  *                        /  |
 176  *                       -----
 177  *                 100,200   200,200
 178  */
 179 TEST(FloatPolygonTest, triangle_nonzero)
 180 {
 181     const float triangleCoordinates[] = {200, 100, 200, 200, 100, 200};
 182     FloatPolygonTestValue triangleTestValue(triangleCoordinates, SIZEOF_ARRAY(triangleCoordinates), RULE_NONZERO);
 183     const FloatPolygon& triangle = triangleTestValue.polygon();
 184
 185     EXPECT_EQ(RULE_NONZERO, triangle.fillRule());
 186     EXPECT_TRUE(triangle.contains(FloatPoint(200, 100)));
 187     EXPECT_TRUE(triangle.contains(FloatPoint(200, 200)));
 188     EXPECT_TRUE(triangle.contains(FloatPoint(100, 200)));
 189     EXPECT_TRUE(triangle.contains(FloatPoint(150, 150)));
 190     EXPECT_FALSE(triangle.contains(FloatPoint(100, 100)));
 191     EXPECT_FALSE(triangle.contains(FloatPoint(149, 149)));
 192     EXPECT_FALSE(triangle.contains(FloatPoint(150, 200.5)));
 193     EXPECT_FALSE(triangle.contains(FloatPoint(201, 200.5)));
 194 }
 195
 196 /**
 197  * Tests FloatPolygon::contains() with a right triangle, and fillRule = evenodd;
 198  *
 199  *                        200,100
 200  *                          /|
 201  *                         / |
 202  *                        /  |
 203  *                       -----
 204  *                 100,200   200,200
 205  */
 206 TEST(FloatPolygonTest, triangle_evenodd)
 207 {
 208     const float triangleCoordinates[] = {200, 100, 200, 200, 100, 200};
 209     FloatPolygonTestValue triangleTestValue(triangleCoordinates, SIZEOF_ARRAY(triangleCoordinates), RULE_EVENODD);
 210     const FloatPolygon& triangle = triangleTestValue.polygon();
 211
 212     EXPECT_EQ(RULE_EVENODD, triangle.fillRule());
 213     EXPECT_TRUE(triangle.contains(FloatPoint(200, 100)));
 214     EXPECT_TRUE(triangle.contains(FloatPoint(200, 200)));
 215     EXPECT_TRUE(triangle.contains(FloatPoint(100, 200)));
 216     EXPECT_TRUE(triangle.contains(FloatPoint(150, 150)));
 217     EXPECT_FALSE(triangle.contains(FloatPoint(100, 100)));
 218     EXPECT_FALSE(triangle.contains(FloatPoint(149, 149)));
 219     EXPECT_FALSE(triangle.contains(FloatPoint(150, 200.5)));
 220     EXPECT_FALSE(triangle.contains(FloatPoint(201, 200.5)));
 221 }
 222
 223 #define TEST_EMPTY(coordinates)                                                                        \
 224 {                                                                                                      \
 225     FloatPolygonTestValue emptyPolygonTestValue(coordinates, SIZEOF_ARRAY(coordinates), RULE_NONZERO); \
 226     const FloatPolygon& emptyPolygon = emptyPolygonTestValue.polygon();                                \
 227     EXPECT_TRUE(emptyPolygon.isEmpty());                                                               \
 228 }
 229
 230 TEST(FloatPolygonTest, emptyPolygons)
 231 {
 232     const float emptyCoordinates1[] = {0, 0};
 233     TEST_EMPTY(emptyCoordinates1);
 234
 235     const float emptyCoordinates2[] = {0, 0, 1, 1};
 236     TEST_EMPTY(emptyCoordinates2);
 237
 238     const float emptyCoordinates3[] = {0, 0, 1, 1, 2, 2, 3, 3};
 239     TEST_EMPTY(emptyCoordinates3);
 240
 241     const float emptyCoordinates4[] = {0, 0, 1, 1, 2, 2, 3, 3, 1, 1};
 242     TEST_EMPTY(emptyCoordinates4);
 243
 244     const float emptyCoordinates5[] = {0, 0, 0, 1, 0, 2, 0, 3, 0, 1};
 245     TEST_EMPTY(emptyCoordinates5);
 246
 247     const float emptyCoordinates6[] = {0, 0, 1, 0, 2, 0, 3, 0, 1, 0};
 248     TEST_EMPTY(emptyCoordinates6);
 249 }
 250
 251 /*
 252  * Test FloatPolygon::contains() with a trapezoid. The vertices are listed in counter-clockwise order.
 253  *
 254  *        150,100   250,100
 255  *          +----------+
 256  *         /            \
 257  *        /              \
 258  *       +----------------+
 259  *     100,150          300,150
 260  */
 261 TEST(FloatPolygonTest, trapezoid)
 262 {
 263     const float trapezoidCoordinates[] = {100, 150, 300, 150, 250, 100, 150, 100};
 264     FloatPolygonTestValue trapezoidTestValue(trapezoidCoordinates, SIZEOF_ARRAY(trapezoidCoordinates), RULE_EVENODD);
 265     const FloatPolygon& trapezoid = trapezoidTestValue.polygon();
 266
 267     EXPECT_FALSE(trapezoid.isEmpty());
 268     EXPECT_EQ(4u, trapezoid.numberOfVertices());
 269     EXPECT_EQ(FloatRect(100, 100, 200, 50), trapezoid.boundingBox());
 270
 271     EXPECT_TRUE(trapezoid.contains(FloatPoint(150, 100)));
 272     EXPECT_TRUE(trapezoid.contains(FloatPoint(150, 101)));
 273     EXPECT_TRUE(trapezoid.contains(FloatPoint(200, 125)));
 274     EXPECT_FALSE(trapezoid.contains(FloatPoint(149, 100)));
 275     EXPECT_FALSE(trapezoid.contains(FloatPoint(301, 150)));
 276 }
 277
 278
 279 /*
 280  * Test FloatPolygon::contains() with a non-convex rectilinear polygon. The polygon has the same shape
 281  * as the letter "H":
 282  *
 283  *    100,100  150,100   200,100   250,100
 284  *       +--------+        +--------+
 285  *       |        |        |        |
 286  *       |        |        |        |
 287  *       |        +--------+        |
 288  *       |     150,150   200,150    |
 289  *       |                          |
 290  *       |     150,200   200,200    |
 291  *       |        +--------+        |
 292  *       |        |        |        |
 293  *       |        |        |        |
 294  *       +--------+        +--------+
 295  *    100,250  150,250   200,250   250,250
 296  */
 297 TEST(FloatPolygonTest, rectilinear)
 298 {
 299     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};
 300     FloatPolygonTestValue hTestValue(hCoordinates, SIZEOF_ARRAY(hCoordinates), RULE_NONZERO);
 301     const FloatPolygon& h = hTestValue.polygon();
 302
 303     EXPECT_FALSE(h.isEmpty());
 304     EXPECT_EQ(12u, h.numberOfVertices());
 305     EXPECT_EQ(FloatRect(100, 100, 150, 150), h.boundingBox());
 306
 307     EXPECT_TRUE(h.contains(FloatPoint(100, 100)));
 308     EXPECT_TRUE(h.contains(FloatPoint(125, 100)));
 309     EXPECT_TRUE(h.contains(FloatPoint(125, 125)));
 310     EXPECT_TRUE(h.contains(FloatPoint(150, 100)));
 311     EXPECT_TRUE(h.contains(FloatPoint(200, 200)));
 312     EXPECT_TRUE(h.contains(FloatPoint(225, 225)));
 313     EXPECT_TRUE(h.contains(FloatPoint(250, 250)));
 314     EXPECT_TRUE(h.contains(FloatPoint(100, 250)));
 315     EXPECT_TRUE(h.contains(FloatPoint(125, 250)));
 316
 317     EXPECT_FALSE(h.contains(FloatPoint(99, 100)));
 318     EXPECT_FALSE(h.contains(FloatPoint(251, 100)));
 319     EXPECT_FALSE(h.contains(FloatPoint(151, 100)));
 320     EXPECT_FALSE(h.contains(FloatPoint(199, 100)));
 321     EXPECT_FALSE(h.contains(FloatPoint(175, 125)));
 322     EXPECT_FALSE(h.contains(FloatPoint(151, 250)));
 323     EXPECT_FALSE(h.contains(FloatPoint(199, 250)));
 324     EXPECT_FALSE(h.contains(FloatPoint(199, 250)));
 325     EXPECT_FALSE(h.contains(FloatPoint(175, 225)));
 326 }
 327
 328 } // namespace blink