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