| OLD | NEW |
|---|
| (Empty) |
| 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 blink { | |
| 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>(c
oordinatesLength / 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 blink | |
| 56 | |
| 57 namespace { | |
| 58 | |
| 59 using namespace blink; | |
| 60 | |
| 61 static bool compareEdgeIndex(const FloatPolygonEdge* edge1, const FloatPolygonEd
ge* 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 acc
essors. | |
| 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(tr
iangleCoordinates), 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, 1
00, 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, 2
00, 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, 1
00, 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, 2
01, 300); | |
| 166 EXPECT_EQ(0u, resultD.size()); | |
| 167 | |
| 168 Vector<const FloatPolygonEdge*> resultE = sortedOverlappingEdges(triangle, 9
8, 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(tr
iangleCoordinates), 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(tr
iangleCoordinates), 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(coordi
nates), 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 co
unter-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 poly
gon 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, 1
00, 250, 100, 250, 250, 200, 250, 200, 200, 150, 200, 150, 250, 100, 250}; | |
| 303 FloatPolygonTestValue hTestValue(hCoordinates, SIZEOF_ARRAY(hCoordinates), R
ULE_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 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 705373003:
Remove PODIntervalTree and machinery. (Closed)
Base URL: git@github.com:domokit/mojo.git@master