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 36namespace blink { 37 38class FloatPolygonTestValue { 39public: 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 51private: 52 OwnPtr<FloatPolygon> m_polygon; 53}; 54 55} // namespace blink 56 57namespace { 58 59using namespace blink; 60 61static bool compareEdgeIndex(const FloatPolygonEdge* edge1, const FloatPolygonEdge* edge2) 62{ 63 return edge1->edgeIndex() < edge2->edgeIndex(); 64} 65 66static 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 */ 86TEST(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 */ 182TEST(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 */ 209TEST(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 233TEST(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 */ 264TEST(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 */ 300TEST(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 332