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