1 /** @file
2  * @brief Unit tests for Ellipse and related functions
3  * Uses the Google Testing Framework
4  *//*
5  * Authors:
6  *   Krzysztof Kosiński <tweenk.pl@gmail.com>
7  *
8  * Copyright 2015 Authors
9  *
10  * This library is free software; you can redistribute it and/or
11  * modify it either under the terms of the GNU Lesser General Public
12  * License version 2.1 as published by the Free Software Foundation
13  * (the "LGPL") or, at your option, under the terms of the Mozilla
14  * Public License Version 1.1 (the "MPL"). If you do not alter this
15  * notice, a recipient may use your version of this file under either
16  * the MPL or the LGPL.
17  *
18  * You should have received a copy of the LGPL along with this library
19  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21  * You should have received a copy of the MPL along with this library
22  * in the file COPYING-MPL-1.1
23  *
24  * The contents of this file are subject to the Mozilla Public License
25  * Version 1.1 (the "License"); you may not use this file except in
26  * compliance with the License. You may obtain a copy of the License at
27  * http://www.mozilla.org/MPL/
28  *
29  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
30  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
31  * the specific language governing rights and limitations.
32  */
33 
34 #include <iostream>
35 #include <glib.h>
36 
37 #include <2geom/angle.h>
38 #include <2geom/ellipse.h>
39 #include <2geom/elliptical-arc.h>
40 #include <memory>
41 
42 #include "testing.h"
43 
44 #ifndef M_SQRT2
45 #  define M_SQRT2 1.41421356237309504880
46 #endif
47 
48 using namespace Geom;
49 
TEST(EllipseTest,Arcs)50 TEST(EllipseTest, Arcs) {
51     Ellipse e(Point(5,10), Point(5, 10), 0);
52 
53     std::unique_ptr<EllipticalArc> arc1(e.arc(Point(5,0), Point(0,0), Point(0,10)));
54 
55     EXPECT_EQ(arc1->initialPoint(), Point(5,0));
56     EXPECT_EQ(arc1->finalPoint(), Point(0,10));
57     EXPECT_EQ(arc1->boundsExact(), Rect::from_xywh(0,0,5,10));
58     EXPECT_EQ(arc1->center(), e.center());
59     EXPECT_EQ(arc1->largeArc(), false);
60     EXPECT_EQ(arc1->sweep(), false);
61 
62     std::unique_ptr<EllipticalArc> arc1r(e.arc(Point(0,10), Point(0,0), Point(5,0)));
63 
64     EXPECT_EQ(arc1r->boundsExact(), arc1->boundsExact());
65     EXPECT_EQ(arc1r->sweep(), true);
66     EXPECT_EQ(arc1r->largeArc(), false);
67 
68     std::unique_ptr<EllipticalArc> arc2(e.arc(Point(5,0), Point(10,20), Point(0,10)));
69 
70     EXPECT_EQ(arc2->boundsExact(), Rect::from_xywh(0,0,10,20));
71     EXPECT_EQ(arc2->largeArc(), true);
72     EXPECT_EQ(arc2->sweep(), true);
73 
74     std::unique_ptr<EllipticalArc> arc2r(e.arc(Point(0,10), Point(10,20), Point(5,0)));
75 
76     EXPECT_EQ(arc2r->boundsExact(), arc2->boundsExact());
77     EXPECT_EQ(arc2r->largeArc(), true);
78     EXPECT_EQ(arc2r->sweep(), false);
79 
80     // exactly half arc
81     std::unique_ptr<EllipticalArc> arc3(e.arc(Point(5,0), Point(0,10), Point(5,20)));
82 
83     EXPECT_EQ(arc3->boundsExact(), Rect::from_xywh(0,0,5,20));
84     EXPECT_EQ(arc3->largeArc(), false);
85     EXPECT_EQ(arc3->sweep(), false);
86 
87     // inner point exactly at midpoint between endpoints
88     std::unique_ptr<EllipticalArc> arc4(e.arc(Point(5,0), Point(2.5,5), Point(0,10)));
89 
90     EXPECT_EQ(arc4->initialPoint(), Point(5,0));
91     EXPECT_EQ(arc4->finalPoint(), Point(0,10));
92     EXPECT_EQ(arc4->boundsExact(), Rect::from_xywh(0,0,5,10));
93     EXPECT_EQ(arc4->largeArc(), false);
94     EXPECT_EQ(arc4->sweep(), false);
95 
96     std::unique_ptr<EllipticalArc> arc4r(e.arc(Point(0,10), Point(2.5,5), Point(5,0)));
97 
98     EXPECT_EQ(arc4r->initialPoint(), Point(0,10));
99     EXPECT_EQ(arc4r->finalPoint(), Point(5,0));
100     EXPECT_EQ(arc4r->boundsExact(), Rect::from_xywh(0,0,5,10));
101     EXPECT_EQ(arc4r->largeArc(), false);
102     EXPECT_EQ(arc4r->sweep(), true);
103 }
104 
TEST(EllipseTest,AreNear)105 TEST(EllipseTest, AreNear) {
106     Ellipse e1(Point(5.000001,10), Point(5,10), Angle::from_degrees(45));
107     Ellipse e2(Point(5.000000,10), Point(5,10), Angle::from_degrees(225));
108     Ellipse e3(Point(4.999999,10), Point(10,5), Angle::from_degrees(135));
109     Ellipse e4(Point(5.000001,10), Point(10,5), Angle::from_degrees(315));
110 
111     EXPECT_TRUE(are_near(e1, e2, 1e-5));
112     EXPECT_TRUE(are_near(e1, e3, 1e-5));
113     EXPECT_TRUE(are_near(e1, e4, 1e-5));
114 
115     Ellipse c1(Point(20.000001,35.000001), Point(5.000001,4.999999), Angle::from_degrees(180.00001));
116     Ellipse c2(Point(19.999999,34.999999), Point(4.999999,5.000001), Angle::from_degrees(179.99999));
117     //std::cout << c1 << "\n" << c2 << std::endl;
118     EXPECT_TRUE(are_near(c1, c2, 2e-5));
119 
120     EXPECT_FALSE(are_near(c1, e1, 1e-5));
121     EXPECT_FALSE(are_near(c2, e1, 1e-5));
122     EXPECT_FALSE(are_near(c1, e2, 1e-5));
123     EXPECT_FALSE(are_near(c2, e2, 1e-5));
124     EXPECT_FALSE(are_near(c1, e3, 1e-5));
125     EXPECT_FALSE(are_near(c2, e3, 1e-5));
126     EXPECT_FALSE(are_near(c1, e4, 1e-5));
127     EXPECT_FALSE(are_near(c2, e4, 1e-5));
128 }
129 
TEST(EllipseTest,Transformations)130 TEST(EllipseTest, Transformations) {
131     Ellipse e(Point(5,10), Point(5,10), Angle::from_degrees(45));
132 
133     Ellipse er = e * Rotate::around(Point(5,10), Angle::from_degrees(45));
134     Ellipse ercmp(Point(5,10), Point(5,10), Angle::from_degrees(90));
135     //std::cout << e << "\n" << er << "\n" << ercmp << std::endl;
136     EXPECT_TRUE(are_near(er, ercmp, 1e-12));
137 
138     Ellipse eflip = e * Affine(Scale(-1,1));
139     Ellipse eflipcmp(Point(-5, 10), Point(5,10), Angle::from_degrees(135));
140     EXPECT_TRUE(are_near(eflip, eflipcmp, 1e-12));
141 }
142 
TEST(EllipseTest,TimeAt)143 TEST(EllipseTest, TimeAt) {
144     Ellipse e(Point(4, 17), Point(22, 34), 2);
145 
146     for (unsigned i = 0; i < 100; ++i) {
147         Coord t = g_random_double_range(0, 2*M_PI);
148         Point p = e.pointAt(t);
149         Coord t2 = e.timeAt(p);
150         EXPECT_FLOAT_EQ(t, t2);
151     }
152 }
153 
TEST(EllipseTest,LineIntersection)154 TEST(EllipseTest, LineIntersection) {
155     Ellipse e(Point(0, 0), Point(3, 2), 0);
156     Line l(Point(0, -2), Point(1, 0));
157 
158     std::vector<ShapeIntersection> xs = e.intersect(l);
159 
160     ASSERT_EQ(xs.size(), 2ul);
161 
162     // due to numeric imprecision when evaluating Ellipse,
163     // the points may deviate by around 2e-16
164     EXPECT_NEAR(xs[0].point()[X], 0, 1e-15);
165     EXPECT_NEAR(xs[0].point()[Y], -2, 1e-15);
166     EXPECT_NEAR(xs[1].point()[X], 9./5, 1e-15);
167     EXPECT_NEAR(xs[1].point()[Y], 8./5, 1e-15);
168 
169     EXPECT_intersections_valid(e, l, xs, 1e-15);
170 }
171 
TEST(EllipseTest,EllipseIntersection)172 TEST(EllipseTest, EllipseIntersection) {
173     Ellipse e1;
174     Ellipse e2;
175     std::vector<ShapeIntersection> xs;
176 
177     e1.set(Point(300, 300), Point(212, 70), -0.785);
178     e2.set(Point(250, 300), Point(230, 90), 1.321);
179     xs = e1.intersect(e2);
180     EXPECT_EQ(xs.size(), 4ul);
181     EXPECT_intersections_valid(e1, e2, xs, 1e-10);
182 
183     e1.set(Point(0, 0), Point(1, 1), 0);
184     e2.set(Point(0, 1), Point(1, 1), 0);
185     xs = e1.intersect(e2);
186     EXPECT_EQ(xs.size(), 2ul);
187     EXPECT_intersections_valid(e1, e2, xs, 1e-10);
188 
189     e1.set(Point(0, 0), Point(1, 1), 0);
190     e2.set(Point(1, 0), Point(1, 1), 0);
191     xs = e1.intersect(e2);
192     EXPECT_EQ(xs.size(), 2ul);
193     EXPECT_intersections_valid(e1, e2, xs, 1e-10);
194 }
195 
TEST(EllipseTest,BezierIntersection)196 TEST(EllipseTest, BezierIntersection) {
197     Ellipse e(Point(300, 300), Point(212, 70), -3.926);
198     D2<Bezier> b(Bezier(100, 300, 100, 500), Bezier(100, 100, 500, 500));
199 
200     std::vector<ShapeIntersection> xs = e.intersect(b);
201 
202     EXPECT_EQ(xs.size(), 2ul);
203     EXPECT_intersections_valid(e, b, xs, 6e-12);
204 }
205 
TEST(EllipseTest,Coefficients)206 TEST(EllipseTest, Coefficients) {
207     std::vector<Ellipse> es;
208     es.emplace_back(Point(-15,25), Point(10,15), Angle::from_degrees(45).radians0());
209     es.emplace_back(Point(-10,33), Point(40,20), M_PI);
210     es.emplace_back(Point(10,-33), Point(40,20), Angle::from_degrees(135).radians0());
211     es.emplace_back(Point(-10,-33), Point(50,10), Angle::from_degrees(330).radians0());
212 
213     for (auto & i : es) {
214         Coord a, b, c, d, e, f;
215         i.coefficients(a, b, c, d, e, f);
216         Ellipse te(a, b, c, d, e, f);
217         EXPECT_near(i, te, 1e-10);
218         for (Coord t = -5; t < 5; t += 0.125) {
219             Point p = i.pointAt(t);
220             Coord eq = a*p[X]*p[X] + b*p[X]*p[Y] + c*p[Y]*p[Y]
221               + d*p[X] + e*p[Y] + f;
222             EXPECT_NEAR(eq, 0, 1e-10);
223         }
224     }
225 }
226 
TEST(EllipseTest,UnitCircleTransform)227 TEST(EllipseTest, UnitCircleTransform) {
228     std::vector<Ellipse> es;
229     es.emplace_back(Point(-15,25), Point(10,15), Angle::from_degrees(45));
230     es.emplace_back(Point(-10,33), Point(40,20), M_PI);
231     es.emplace_back(Point(10,-33), Point(40,20), Angle::from_degrees(135));
232     es.emplace_back(Point(-10,-33), Point(50,10), Angle::from_degrees(330));
233 
234     for (auto & e : es) {
235         EXPECT_near(e.unitCircleTransform() * e.inverseUnitCircleTransform(), Affine::identity(), 1e-8);
236 
237         for (Coord t = -1; t < 10; t += 0.25) {
238             Point p = e.pointAt(t);
239             p *= e.inverseUnitCircleTransform();
240             EXPECT_near(p.length(), 1., 1e-10);
241             p *= e.unitCircleTransform();
242             EXPECT_near(e.pointAt(t), p, 1e-10);
243         }
244     }
245 }
246 
TEST(EllipseTest,PointAt)247 TEST(EllipseTest, PointAt) {
248     Ellipse a(Point(0,0), Point(10,20), 0);
249     EXPECT_near(a.pointAt(0), Point(10,0), 1e-10);
250     EXPECT_near(a.pointAt(M_PI/2), Point(0,20), 1e-10);
251     EXPECT_near(a.pointAt(M_PI), Point(-10,0), 1e-10);
252     EXPECT_near(a.pointAt(3*M_PI/2), Point(0,-20), 1e-10);
253 
254     Ellipse b(Point(0,0), Point(10,20), M_PI/2);
255     EXPECT_near(b.pointAt(0), Point(0,10), 1e-10);
256     EXPECT_near(b.pointAt(M_PI/2), Point(-20,0), 1e-10);
257     EXPECT_near(b.pointAt(M_PI), Point(0,-10), 1e-10);
258     EXPECT_near(b.pointAt(3*M_PI/2), Point(20,0), 1e-10);
259 }
260 
TEST(EllipseTest,UnitTangentAt)261 TEST(EllipseTest, UnitTangentAt) {
262     Ellipse a(Point(14,-7), Point(20,10), 0);
263     Ellipse b(Point(-77,23), Point(40,10), Angle::from_degrees(45));
264 
265     EXPECT_near(a.unitTangentAt(0), Point(0,1), 1e-12);
266     EXPECT_near(a.unitTangentAt(M_PI/2), Point(-1,0), 1e-12);
267     EXPECT_near(a.unitTangentAt(M_PI), Point(0,-1), 1e-12);
268     EXPECT_near(a.unitTangentAt(3*M_PI/2), Point(1,0), 1e-12);
269 
270     EXPECT_near(b.unitTangentAt(0), Point(-M_SQRT2/2, M_SQRT2/2), 1e-12);
271     EXPECT_near(b.unitTangentAt(M_PI/2), Point(-M_SQRT2/2, -M_SQRT2/2), 1e-12);
272     EXPECT_near(b.unitTangentAt(M_PI), Point(M_SQRT2/2, -M_SQRT2/2), 1e-12);
273     EXPECT_near(b.unitTangentAt(3*M_PI/2), Point(M_SQRT2/2, M_SQRT2/2), 1e-12);
274 }
275 
TEST(EllipseTest,BoundsExact)276 TEST(EllipseTest, BoundsExact) {
277     std::vector<Ellipse> es;
278     es.emplace_back(Point(-15,25), Point(10,15), Angle::from_degrees(45));
279     es.emplace_back(Point(-10,33), Point(40,20), M_PI);
280     es.emplace_back(Point(10,-33), Point(40,20), Angle::from_degrees(111));
281     es.emplace_back(Point(-10,-33), Point(50,10), Angle::from_degrees(222));
282 
283     // for reproducibility
284     g_random_set_seed(1234);
285 
286     for (auto & e : es) {
287         Rect r = e.boundsExact();
288         for (unsigned j = 0; j < 10000; ++j) {
289             Coord t = g_random_double_range(-M_PI, M_PI);
290             EXPECT_TRUE(r.contains(e.pointAt(t)));
291         }
292     }
293 
294     Ellipse e(Point(0,0), Point(10, 10), M_PI);
295     Rect bounds = e.boundsExact();
296     EXPECT_EQ(bounds, Rect(Point(-10,-10), Point(10,10)));
297     EXPECT_TRUE(bounds.contains(e.pointAt(0)));
298     EXPECT_TRUE(bounds.contains(e.pointAt(M_PI/2)));
299     EXPECT_TRUE(bounds.contains(e.pointAt(M_PI)));
300     EXPECT_TRUE(bounds.contains(e.pointAt(3*M_PI/2)));
301     EXPECT_TRUE(bounds.contains(e.pointAt(2*M_PI)));
302 
303     e = Ellipse(Point(0,0), Point(10, 10), M_PI/2);
304     bounds = e.boundsExact();
305     EXPECT_EQ(bounds, Rect(Point(-10,-10), Point(10,10)));
306     EXPECT_TRUE(bounds.contains(e.pointAt(0)));
307     EXPECT_TRUE(bounds.contains(e.pointAt(M_PI/2)));
308     EXPECT_TRUE(bounds.contains(e.pointAt(M_PI)));
309     EXPECT_TRUE(bounds.contains(e.pointAt(3*M_PI/2)));
310     EXPECT_TRUE(bounds.contains(e.pointAt(2*M_PI)));
311 }
312