Adding upstream version 1.3.upstream/1.3upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 275 insertions, 0 deletions

diff --git a/tests/elliptical-arc-test.cpp b/tests/elliptical-arc-test.cpp
new file mode 100644
index 0000000..1f6eff7
--- /dev/null
+++ b/tests/elliptical-arc-test.cpp
@@ -0,0 +1,275 @@
+/** @file
+ * @brief Unit tests for EllipticalArc.
+ * Uses the Google Testing Framework
+ *//*
+ * Authors:
+ *   Krzysztof Kosiński <tweenk.pl@gmail.com>
+ *
+ * Copyright 2015 Authors
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ */
+
+#include "testing.h"
+#include <2geom/elliptical-arc.h>
+#include <glib.h>
+
+using namespace Geom;
+
+TEST(EllipticalArcTest, PointAt) {
+    EllipticalArc a(Point(0,0), Point(10,20), M_PI/2, false, true, Point(-40,0));
+    EXPECT_near(a.pointAt(0), a.initialPoint(), 1e-14);
+    EXPECT_near(a.pointAt(1), a.finalPoint(), 1e-14);
+    EXPECT_near(a.pointAt(0.5), Point(-20,10), 1e-14);
+
+    EllipticalArc b(Point(0,0), Point(10,20), 0, false, true, Point(-40,0));
+    EXPECT_near(b.pointAt(0), b.initialPoint(), 1e-14);
+    EXPECT_near(b.pointAt(1), b.finalPoint(), 1e-14);
+    EXPECT_near(b.pointAt(0.5), Point(-20,40), 1e-14);
+
+    EllipticalArc c(Point(200,0), Point(40,20), Angle::from_degrees(90), false, false, Point(200,100));
+    EXPECT_near(c.pointAt(0), c.initialPoint(), 1e-13);
+    EXPECT_near(c.pointAt(1), c.finalPoint(), 1e-13);
+    EXPECT_near(c.pointAt(0.5), Point(175, 50), 1e-13);
+}
+
+TEST(EllipticalArc, Transform) {
+    EllipticalArc a(Point(0,0), Point(10,20), M_PI/2, false, true, Point(-40,0));
+    EllipticalArc b(Point(-40,0), Point(10,20), M_PI/2, false, true, Point(0,0));
+    EllipticalArc c = a;
+    Affine m = Rotate::around(Point(-20,0), M_PI);
+    c.transform(m);
+
+    for (unsigned i = 0; i <= 100; ++i) {
+        Coord t = i/100.;
+        EXPECT_near(c.pointAt(t), b.pointAt(t), 1e-12);
+        EXPECT_near(a.pointAt(t)*m, c.pointAt(t), 1e-12);
+    }
+}
+
+TEST(EllipticalArcTest, Duplicate) {
+    EllipticalArc a(Point(0,0), Point(10,20), M_PI/2, true, false, Point(-40,0));
+    EllipticalArc *b = static_cast<EllipticalArc*>(a.duplicate());
+    EXPECT_EQ(a, *b);
+    delete b;
+}
+
+TEST(EllipticalArcTest, LineSegmentIntersection) {
+    std::vector<CurveIntersection> r1;
+    EllipticalArc a3(Point(0,0), Point(5,1.5), 0, true, true, Point(0,2));
+    LineSegment ls(Point(0,5), Point(7,-3));
+    r1 = a3.intersect(ls);
+    EXPECT_EQ(r1.size(), 2u);
+    EXPECT_intersections_valid(a3, ls, r1, 1e-10);
+
+    g_random_set_seed(0xB747A380);
+    // Test with randomized arcs and segments.
+    for (size_t _ = 0; _ < 10'000; _++) {
+        auto arc = EllipticalArc({g_random_double_range(1.0, 5.0), 0.0},
+                                 {g_random_double_range(6.0, 8.0), g_random_double_range(2.0, 7.0)},
+                                  g_random_double_range(-0.5, 0.5), true, g_random_boolean(),
+                                 {g_random_double_range(-5.0, -1.0), 0.0});
+        Coord x = g_random_double_range(15, 30);
+        Coord y = g_random_double_range(10, 20);
+        auto seg = LineSegment(Point(-x, y), Point(x, -y));
+        auto xings = arc.intersect(seg);
+        EXPECT_EQ(xings.size(), 1u);
+        EXPECT_intersections_valid(arc, seg, xings, 1e-12);
+    }
+
+    // Test with degenerate arcs
+    EllipticalArc x_squash_pos{{3.0, 0.0}, {3.0, 2.0}, 0, true, true, {-3.0, 0.0}};
+    EllipticalArc x_squash_neg{{3.0, 0.0}, {3.0, 2.0}, 0, true, false, {-3.0, 0.0}};
+    auto const squash_to_x = Scale(1.0, 0.0);
+    x_squash_pos *= squash_to_x; // squash to X axis interval [-3, 3].
+    x_squash_neg *= squash_to_x;
+
+    for (size_t _ = 0; _ < 10'000; _++) {
+        auto seg = LineSegment(Point(g_random_double_range(-3.0, 3.0), g_random_double_range(-3.0, -1.0)),
+                               Point(g_random_double_range(-3.0, 3.0), g_random_double_range(1.0, 3.0)));
+        auto xings = x_squash_pos.intersect(seg);
+        EXPECT_EQ(xings.size(), 1u);
+        EXPECT_intersections_valid(x_squash_pos, seg, xings, 1e-12);
+
+        std::unique_ptr<Curve> rev{x_squash_pos.reverse()};
+        xings = rev->intersect(seg);
+        EXPECT_EQ(xings.size(), 1u);
+        EXPECT_intersections_valid(*rev, seg, xings, 1e-12);
+
+        xings = x_squash_neg.intersect(seg);
+        EXPECT_EQ(xings.size(), 1u);
+        EXPECT_intersections_valid(x_squash_neg, seg, xings, 1e-12);
+
+        rev.reset(x_squash_neg.reverse());
+        xings = rev->intersect(seg);
+        EXPECT_EQ(xings.size(), 1u);
+        EXPECT_intersections_valid(*rev, seg, xings, 1e-12);
+    }
+
+    // Now test with an arc squashed to the Y-axis.
+    EllipticalArc y_squash_pos{{0.0, -2.0}, {3.0, 2.0}, 0, true, true, {0.0, 2.0}};
+    EllipticalArc y_squash_neg{{0.0, -2.0}, {3.0, 2.0}, 0, true, false, {0.0, 2.0}};
+    auto const squash_to_y = Scale(0.0, 1.0);
+    y_squash_pos *= squash_to_y; // Y-axis interval [-2, 2].
+    y_squash_neg *= squash_to_y;
+
+    for (size_t _ = 0; _ < 10'000; _++) {
+        auto seg = LineSegment(Point(g_random_double_range(-3.0, -1.0), g_random_double_range(-2.0, 2.0)),
+                               Point(g_random_double_range(1.0, 3.0),   g_random_double_range(-2.0, 2.0)));
+        auto xings = y_squash_pos.intersect(seg, 1e-10);
+        EXPECT_EQ(xings.size(), 1u);
+        EXPECT_intersections_valid(y_squash_pos, seg, xings, 1e-12);
+
+        std::unique_ptr<Curve> rev{y_squash_pos.reverse()};
+        xings = rev->intersect(seg, 1e-12);
+        EXPECT_EQ(xings.size(), 1u);
+        EXPECT_intersections_valid(*rev, seg, xings, 1e-12);
+
+        xings = y_squash_neg.intersect(seg, 1e-12);
+        EXPECT_EQ(xings.size(), 1u);
+        EXPECT_intersections_valid(y_squash_neg, seg, xings, 1e-12);
+
+        rev.reset(y_squash_neg.reverse());
+        xings = rev->intersect(seg, 1e-12);
+        EXPECT_EQ(xings.size(), 1u);
+        EXPECT_intersections_valid(*rev, seg, xings, 1e-12);
+    }
+
+    // Test whether the coincidence between the common endpoints of an
+    // arc and a segment is correctly detected as an intersection.
+    {
+        Point const from{1, 0};
+        Point const to{0.30901699437494745, 0.9510565162951535};
+        auto arc = EllipticalArc(from, {1, 1}, 0, false, true, to);
+        auto seg = LineSegment({0, 0}, to);
+        auto xings = arc.intersect(seg);
+        ASSERT_EQ(xings.size(), 1);
+        EXPECT_TRUE(are_near(xings[0].point(), to, 1e-12));
+        EXPECT_TRUE(are_near(xings[0].first, 1.0, 1e-24));
+        EXPECT_TRUE(are_near(xings[0].second, 1.0, 1e-24));
+
+        auto seg2 = LineSegment(Point{1, 1}, from);
+        xings = arc.intersect(seg2);
+        ASSERT_EQ(xings.size(), 1);
+        EXPECT_TRUE(are_near(xings[0].point(), from, 1e-12));
+        EXPECT_TRUE(are_near(xings[0].first, 0.0, 1e-24));
+        EXPECT_TRUE(are_near(xings[0].second, 1.0, 1e-24));
+    }
+}
+
+TEST(EllipticalArcTest, ArcIntersection) {
+    std::vector<CurveIntersection> r1, r2;
+
+    EllipticalArc a1(Point(0,0), Point(6,3), 0.1, false, false, Point(10,0));
+    EllipticalArc a2(Point(0,2), Point(6,3), -0.1, false, true, Point(10,2));
+    r1 = a1.intersect(a2);
+    EXPECT_EQ(r1.size(), 2u);
+    EXPECT_intersections_valid(a1, a2, r1, 1e-10);
+
+    EllipticalArc a3(Point(0,0), Point(5,1.5), 0, true, true, Point(0,2));
+    EllipticalArc a4(Point(3,5), Point(5,1.5), M_PI/2, true, true, Point(5,0));
+    r2 = a3.intersect(a4);
+    EXPECT_EQ(r2.size(), 3u);
+    EXPECT_intersections_valid(a3, a4, r2, 1e-10);
+
+    // Make sure intersections are found between two identical arcs on the unit circle.
+    EllipticalArc const upper(Point(1, 0), Point(1, 1), 0, true, true, Point(-1, 0));
+    auto self_intersect = upper.intersect(upper);
+    EXPECT_EQ(self_intersect.size(), 2u);
+
+    // Make sure intersections are found between overlapping arcs.
+    EllipticalArc const right(Point(0, -1), Point(1, 1), 0, true, true, Point(0, 1));
+    auto quartering_overlap_xings = right.intersect(upper);
+    EXPECT_EQ(quartering_overlap_xings.size(), 2u);
+
+    // Make sure intersecections are found between an arc and its sub-arc.
+    EllipticalArc const middle(upper.pointAtAngle(0.25 * M_PI), Point(1, 1), 0, true, true, upper.pointAtAngle(-0.25 * M_PI));
+    EXPECT_EQ(middle.intersect(upper).size(), 2u);
+
+    // Make sure intersections are NOT found between non-overlapping sub-arcs of the same circle.
+    EllipticalArc const arc1{Point(1, 0), Point(1, 1), 0, true, true, Point(0, 1)};
+    EllipticalArc const arc2{Point(-1, 0), Point(1, 1), 0, true, true, Point(0, -1)};
+    EXPECT_EQ(arc1.intersect(arc2).size(), 0u);
+
+    // Overlapping sub-arcs but on an Ellipse with different rays.
+    EllipticalArc const eccentric{Point(2, 0), Point(2, 1), 0, true, true, Point(-2, 0)};
+    EllipticalArc const subarc{eccentric.pointAtAngle(0.8), Point(2, 1), 0, true, true, eccentric.pointAtAngle(2)};
+    EXPECT_EQ(eccentric.intersect(subarc).size(), 2u);
+
+    // Check intersection times for two touching arcs.
+    EllipticalArc const lower{Point(-1, 0), Point(1, 1), 0, false, true, Point(0, -1)};
+    auto expected_neg_x = upper.intersect(lower);
+    ASSERT_EQ(expected_neg_x.size(), 1);
+    auto const &left_pt = expected_neg_x[0];
+    EXPECT_EQ(left_pt.point(), Point(-1, 0));
+    EXPECT_DOUBLE_EQ(left_pt.first, 1.0); // Expect (-1, 0) reached at the end of upper
+    EXPECT_DOUBLE_EQ(left_pt.second, 0.0); // Expect (-1, 0) passed at the start of lower
+}
+
+TEST(EllipticalArcTest, BezierIntersection) {
+    std::vector<CurveIntersection> r1, r2;
+
+    EllipticalArc a3(Point(0,0), Point(1.5,5), M_PI/2, true, true, Point(0,2));
+    CubicBezier bez1(Point(0,3), Point(7,3), Point(0,-1), Point(7,-1));
+    r1 = a3.intersect(bez1);
+    EXPECT_EQ(r1.size(), 2u);
+    EXPECT_intersections_valid(a3, bez1, r1, 1e-10);
+
+    EllipticalArc a4(Point(3,5), Point(5,1.5), 3*M_PI/2, true, true, Point(5,5));
+    CubicBezier bez2(Point(0,5), Point(10,-4), Point(10,5), Point(0,-4));
+    r2 = a4.intersect(bez2);
+    EXPECT_EQ(r2.size(), 4u);
+    EXPECT_intersections_valid(a4, bez2, r2, 1e-10);
+}
+
+TEST(EllipticalArcTest, ExpandToTransformedTest)
+{
+    auto test_curve = [] (EllipticalArc const &c) {
+        constexpr int N = 50;
+        for (int i = 0; i < N; i++) {
+            auto angle = 2 * M_PI * i / N;
+            auto transform = Affine(Rotate(angle)) * Scale(0.9, 1.2);
+
+            auto copy = std::unique_ptr<Curve>(c.duplicate());
+            *copy *= transform;
+            auto box1 = copy->boundsExact();
+
+            auto pt = c.initialPoint() * transform;
+            auto box2 = Rect(pt, pt);
+            c.expandToTransformed(box2, transform);
+
+            for (auto i : { X, Y }) {
+                EXPECT_NEAR(box1[i].min(), box2[i].min(), 2e-15);
+                EXPECT_NEAR(box1[i].max(), box2[i].max(), 2e-15);
+            }
+        }
+    };
+
+    test_curve(EllipticalArc(Point(0, 0), 1.0, 2.0, 0.0, false, false, Point(1, 1)));
+    test_curve(EllipticalArc(Point(0, 0), 3.0, 2.0, M_PI / 6, false, false, Point(1, 1)));
+    test_curve(EllipticalArc(Point(0, 0), 1.0, 2.0, M_PI / 5, true, true, Point(1, 1)));
+    test_curve(EllipticalArc(Point(1, 0), 1.0, 0.0, M_PI / 5, false, false, Point(1, 1)));
+    test_curve(EllipticalArc(Point(1, 0), 0.0, 0.0, 0.0, false, false, Point(2, 0)));
+    test_curve(EllipticalArc(Point(1, 0), 0.0, 0.0, 0.0, false, false, Point(1, 0)));
+}