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 "third_party/blink/renderer/platform/geometry/float_polygon.h"
31 
32 #include <algorithm>
33 #include <memory>
34 #include <utility>
35 
36 #include "testing/gtest/include/gtest/gtest.h"
37 #include "third_party/blink/renderer/platform/wtf/allocator/allocator.h"
38 
39 namespace blink {
40 
41 class FloatPolygonTestValue {
42   STACK_ALLOCATED();
43 
44  public:
FloatPolygonTestValue(const float * coordinates,unsigned coordinates_length)45   FloatPolygonTestValue(const float* coordinates, unsigned coordinates_length) {
46     DCHECK(!(coordinates_length % 2));
47     Vector<FloatPoint> vertices(coordinates_length / 2);
48     for (unsigned i = 0; i < coordinates_length; i += 2)
49       vertices[i / 2] = FloatPoint(coordinates[i], coordinates[i + 1]);
50     polygon_ = std::make_unique<FloatPolygon>(std::move(vertices));
51   }
52 
Polygon() const53   const FloatPolygon& Polygon() const { return *polygon_; }
54 
55  private:
56   std::unique_ptr<FloatPolygon> polygon_;
57 };
58 
59 namespace {
60 
CompareEdgeIndex(const FloatPolygonEdge * edge1,const FloatPolygonEdge * edge2)61 bool CompareEdgeIndex(const FloatPolygonEdge* edge1,
62                       const FloatPolygonEdge* edge2) {
63   return edge1->EdgeIndex() < edge2->EdgeIndex();
64 }
65 
66 Vector<const FloatPolygonEdge*>
SortedOverlappingEdges(const FloatPolygon & polygon,float min_y,float max_y)67 SortedOverlappingEdges(const FloatPolygon& polygon, float min_y, float max_y) {
68   Vector<const FloatPolygonEdge*> result;
69   polygon.OverlappingEdges(min_y, max_y, result);
70   std::sort(result.begin(), result.end(), CompareEdgeIndex);
71   return result;
72 }
73 
74 }  // anonymous namespace
75 
76 #define SIZEOF_ARRAY(p) (sizeof(p) / sizeof(p[0]))
77 
78 /**
79  * Checks a right triangle. This test covers all of the trivial FloatPolygon
80  * accessors.
81  *
82  *                        200,100
83  *                          /|
84  *                         / |
85  *                        /  |
86  *                       -----
87  *                 100,200   200,200
88  */
TEST(FloatPolygonTest,basics)89 TEST(FloatPolygonTest, basics) {
90   const float kTriangleCoordinates[] = {200, 100, 200, 200, 100, 200};
91   FloatPolygonTestValue triangle_test_value(kTriangleCoordinates,
92                                             SIZEOF_ARRAY(kTriangleCoordinates));
93   const FloatPolygon& triangle = triangle_test_value.Polygon();
94 
95   EXPECT_FALSE(triangle.IsEmpty());
96 
97   EXPECT_EQ(3u, triangle.NumberOfVertices());
98   EXPECT_EQ(FloatPoint(200, 100), triangle.VertexAt(0));
99   EXPECT_EQ(FloatPoint(200, 200), triangle.VertexAt(1));
100   EXPECT_EQ(FloatPoint(100, 200), triangle.VertexAt(2));
101 
102   EXPECT_EQ(3u, triangle.NumberOfEdges());
103   EXPECT_EQ(FloatPoint(200, 100), triangle.EdgeAt(0).Vertex1());
104   EXPECT_EQ(FloatPoint(200, 200), triangle.EdgeAt(0).Vertex2());
105   EXPECT_EQ(FloatPoint(200, 200), triangle.EdgeAt(1).Vertex1());
106   EXPECT_EQ(FloatPoint(100, 200), triangle.EdgeAt(1).Vertex2());
107   EXPECT_EQ(FloatPoint(100, 200), triangle.EdgeAt(2).Vertex1());
108   EXPECT_EQ(FloatPoint(200, 100), triangle.EdgeAt(2).Vertex2());
109 
110   EXPECT_EQ(0u, triangle.EdgeAt(0).VertexIndex1());
111   EXPECT_EQ(1u, triangle.EdgeAt(0).VertexIndex2());
112   EXPECT_EQ(1u, triangle.EdgeAt(1).VertexIndex1());
113   EXPECT_EQ(2u, triangle.EdgeAt(1).VertexIndex2());
114   EXPECT_EQ(2u, triangle.EdgeAt(2).VertexIndex1());
115   EXPECT_EQ(0u, triangle.EdgeAt(2).VertexIndex2());
116 
117   EXPECT_EQ(200, triangle.EdgeAt(0).MinX());
118   EXPECT_EQ(200, triangle.EdgeAt(0).MaxX());
119   EXPECT_EQ(100, triangle.EdgeAt(1).MinX());
120   EXPECT_EQ(200, triangle.EdgeAt(1).MaxX());
121   EXPECT_EQ(100, triangle.EdgeAt(2).MinX());
122   EXPECT_EQ(200, triangle.EdgeAt(2).MaxX());
123 
124   EXPECT_EQ(100, triangle.EdgeAt(0).MinY());
125   EXPECT_EQ(200, triangle.EdgeAt(0).MaxY());
126   EXPECT_EQ(200, triangle.EdgeAt(1).MinY());
127   EXPECT_EQ(200, triangle.EdgeAt(1).MaxY());
128   EXPECT_EQ(100, triangle.EdgeAt(2).MinY());
129   EXPECT_EQ(200, triangle.EdgeAt(2).MaxY());
130 
131   EXPECT_EQ(0u, triangle.EdgeAt(0).EdgeIndex());
132   EXPECT_EQ(1u, triangle.EdgeAt(1).EdgeIndex());
133   EXPECT_EQ(2u, triangle.EdgeAt(2).EdgeIndex());
134 
135   EXPECT_EQ(2u, triangle.EdgeAt(0).PreviousEdge().EdgeIndex());
136   EXPECT_EQ(1u, triangle.EdgeAt(0).NextEdge().EdgeIndex());
137   EXPECT_EQ(0u, triangle.EdgeAt(1).PreviousEdge().EdgeIndex());
138   EXPECT_EQ(2u, triangle.EdgeAt(1).NextEdge().EdgeIndex());
139   EXPECT_EQ(1u, triangle.EdgeAt(2).PreviousEdge().EdgeIndex());
140   EXPECT_EQ(0u, triangle.EdgeAt(2).NextEdge().EdgeIndex());
141 
142   EXPECT_EQ(FloatRect(100, 100, 100, 100), triangle.BoundingBox());
143 
144   Vector<const FloatPolygonEdge*> result_a =
145       SortedOverlappingEdges(triangle, 100, 200);
146   EXPECT_EQ(3u, result_a.size());
147   if (result_a.size() == 3) {
148     EXPECT_EQ(0u, result_a[0]->EdgeIndex());
149     EXPECT_EQ(1u, result_a[1]->EdgeIndex());
150     EXPECT_EQ(2u, result_a[2]->EdgeIndex());
151   }
152 
153   Vector<const FloatPolygonEdge*> result_b =
154       SortedOverlappingEdges(triangle, 200, 200);
155   EXPECT_EQ(3u, result_b.size());
156   if (result_b.size() == 3) {
157     EXPECT_EQ(0u, result_b[0]->EdgeIndex());
158     EXPECT_EQ(1u, result_b[1]->EdgeIndex());
159     EXPECT_EQ(2u, result_b[2]->EdgeIndex());
160   }
161 
162   Vector<const FloatPolygonEdge*> result_c =
163       SortedOverlappingEdges(triangle, 100, 150);
164   EXPECT_EQ(2u, result_c.size());
165   if (result_c.size() == 2) {
166     EXPECT_EQ(0u, result_c[0]->EdgeIndex());
167     EXPECT_EQ(2u, result_c[1]->EdgeIndex());
168   }
169 
170   Vector<const FloatPolygonEdge*> result_d =
171       SortedOverlappingEdges(triangle, 201, 300);
172   EXPECT_EQ(0u, result_d.size());
173 
174   Vector<const FloatPolygonEdge*> result_e =
175       SortedOverlappingEdges(triangle, 98, 99);
176   EXPECT_EQ(0u, result_e.size());
177 }
178 
179 /**
180  * Tests ContainsNonZero and ContainsEvenOdd with a right triangle.
181  *
182  *                        200,100
183  *                          /|
184  *                         / |
185  *                        /  |
186  *                       -----
187  *                 100,200   200,200
188  */
TEST(FloatPolygonTest,triangle_nonzero)189 TEST(FloatPolygonTest, triangle_nonzero) {
190   const float kTriangleCoordinates[] = {200, 100, 200, 200, 100, 200};
191   FloatPolygonTestValue triangle_test_value(kTriangleCoordinates,
192                                             SIZEOF_ARRAY(kTriangleCoordinates));
193   const FloatPolygon& triangle = triangle_test_value.Polygon();
194 
195   EXPECT_TRUE(triangle.ContainsNonZero(FloatPoint(200, 100)));
196   EXPECT_TRUE(triangle.ContainsNonZero(FloatPoint(200, 200)));
197   EXPECT_TRUE(triangle.ContainsNonZero(FloatPoint(100, 200)));
198   EXPECT_TRUE(triangle.ContainsNonZero(FloatPoint(150, 150)));
199   EXPECT_FALSE(triangle.ContainsNonZero(FloatPoint(100, 100)));
200   EXPECT_FALSE(triangle.ContainsNonZero(FloatPoint(149, 149)));
201   EXPECT_FALSE(triangle.ContainsNonZero(FloatPoint(150, 200.5)));
202   EXPECT_FALSE(triangle.ContainsNonZero(FloatPoint(201, 200.5)));
203 
204   EXPECT_TRUE(triangle.ContainsEvenOdd(FloatPoint(200, 100)));
205   EXPECT_TRUE(triangle.ContainsEvenOdd(FloatPoint(200, 200)));
206   EXPECT_TRUE(triangle.ContainsEvenOdd(FloatPoint(100, 200)));
207   EXPECT_TRUE(triangle.ContainsEvenOdd(FloatPoint(150, 150)));
208   EXPECT_FALSE(triangle.ContainsEvenOdd(FloatPoint(100, 100)));
209   EXPECT_FALSE(triangle.ContainsEvenOdd(FloatPoint(149, 149)));
210   EXPECT_FALSE(triangle.ContainsEvenOdd(FloatPoint(150, 200.5)));
211   EXPECT_FALSE(triangle.ContainsEvenOdd(FloatPoint(201, 200.5)));
212 }
213 
214 #define TEST_EMPTY(coordinates)                                                \
215   {                                                                            \
216     FloatPolygonTestValue empty_polygon_test_value(coordinates,                \
217                                                    SIZEOF_ARRAY(coordinates)); \
218     const FloatPolygon& empty_polygon = empty_polygon_test_value.Polygon();    \
219     EXPECT_TRUE(empty_polygon.IsEmpty());                                      \
220   }
221 
TEST(FloatPolygonTest,emptyPolygons)222 TEST(FloatPolygonTest, emptyPolygons) {
223   const float kEmptyCoordinates1[] = {0, 0};
224   TEST_EMPTY(kEmptyCoordinates1);
225 
226   const float kEmptyCoordinates2[] = {0, 0, 1, 1};
227   TEST_EMPTY(kEmptyCoordinates2);
228 
229   const float kEmptyCoordinates3[] = {0, 0, 1, 1, 2, 2, 3, 3};
230   TEST_EMPTY(kEmptyCoordinates3);
231 
232   const float kEmptyCoordinates4[] = {0, 0, 1, 1, 2, 2, 3, 3, 1, 1};
233   TEST_EMPTY(kEmptyCoordinates4);
234 
235   const float kEmptyCoordinates5[] = {0, 0, 0, 1, 0, 2, 0, 3, 0, 1};
236   TEST_EMPTY(kEmptyCoordinates5);
237 
238   const float kEmptyCoordinates6[] = {0, 0, 1, 0, 2, 0, 3, 0, 1, 0};
239   TEST_EMPTY(kEmptyCoordinates6);
240 }
241 
242 /*
243  * Test FloatPolygon::ContainsEvenOdd() with a trapezoid. The vertices are
244  * listed in counter-clockwise order.
245  *
246  *        150,100   250,100
247  *          +----------+
248  *         /            \
249  *        /              \
250  *       +----------------+
251  *     100,150          300,150
252  */
TEST(FloatPolygonTest,trapezoid)253 TEST(FloatPolygonTest, trapezoid) {
254   const float kTrapezoidCoordinates[] = {100, 150, 300, 150,
255                                          250, 100, 150, 100};
256   FloatPolygonTestValue trapezoid_test_value(
257       kTrapezoidCoordinates, SIZEOF_ARRAY(kTrapezoidCoordinates));
258   const FloatPolygon& trapezoid = trapezoid_test_value.Polygon();
259 
260   EXPECT_FALSE(trapezoid.IsEmpty());
261   EXPECT_EQ(4u, trapezoid.NumberOfVertices());
262   EXPECT_EQ(FloatRect(100, 100, 200, 50), trapezoid.BoundingBox());
263 
264   EXPECT_TRUE(trapezoid.ContainsEvenOdd(FloatPoint(150, 100)));
265   EXPECT_TRUE(trapezoid.ContainsEvenOdd(FloatPoint(150, 101)));
266   EXPECT_TRUE(trapezoid.ContainsEvenOdd(FloatPoint(200, 125)));
267   EXPECT_FALSE(trapezoid.ContainsEvenOdd(FloatPoint(149, 100)));
268   EXPECT_FALSE(trapezoid.ContainsEvenOdd(FloatPoint(301, 150)));
269 }
270 
271 /*
272  * Test FloatPolygon::ContainsNonZero() with a non-convex rectilinear polygon.
273  * The polygon has the same shape as the letter "H":
274  *
275  *    100,100  150,100   200,100   250,100
276  *       +--------+        +--------+
277  *       |        |        |        |
278  *       |        |        |        |
279  *       |        +--------+        |
280  *       |     150,150   200,150    |
281  *       |                          |
282  *       |     150,200   200,200    |
283  *       |        +--------+        |
284  *       |        |        |        |
285  *       |        |        |        |
286  *       +--------+        +--------+
287  *    100,250  150,250   200,250   250,250
288  */
TEST(FloatPolygonTest,rectilinear)289 TEST(FloatPolygonTest, rectilinear) {
290   const float kHCoordinates[] = {100, 100, 150, 100, 150, 150, 200, 150,
291                                  200, 100, 250, 100, 250, 250, 200, 250,
292                                  200, 200, 150, 200, 150, 250, 100, 250};
293   FloatPolygonTestValue h_test_value(kHCoordinates,
294                                      SIZEOF_ARRAY(kHCoordinates));
295   const FloatPolygon& h = h_test_value.Polygon();
296 
297   EXPECT_FALSE(h.IsEmpty());
298   EXPECT_EQ(12u, h.NumberOfVertices());
299   EXPECT_EQ(FloatRect(100, 100, 150, 150), h.BoundingBox());
300 
301   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(100, 100)));
302   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(125, 100)));
303   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(125, 125)));
304   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(150, 100)));
305   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(200, 200)));
306   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(225, 225)));
307   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(250, 250)));
308   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(100, 250)));
309   EXPECT_TRUE(h.ContainsNonZero(FloatPoint(125, 250)));
310 
311   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(99, 100)));
312   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(251, 100)));
313   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(151, 100)));
314   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(199, 100)));
315   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(175, 125)));
316   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(151, 250)));
317   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(199, 250)));
318   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(199, 250)));
319   EXPECT_FALSE(h.ContainsNonZero(FloatPoint(175, 225)));
320 }
321 
322 }  // namespace blink
323