1 files changed, 457 insertions, 0 deletions
diff --git a/src/3rdparty/2geom/tests/planar-graph-test.cpp b/src/3rdparty/2geom/tests/planar-graph-test.cpp
new file mode 100644
index 0000000..f19e2eb
--- /dev/null
+++ b/src/3rdparty/2geom/tests/planar-graph-test.cpp
@@ -0,0 +1,457 @@
+/** @file
+ * @brief Unit tests for PlanarGraph class template
+ */
+/*
+ * Authors:
+ *   Rafał Siejakowski <rs@rs-math.net>
+ *
+ * Copyright 2022 the 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 <gtest/gtest.h>
+#include <iostream>
+
+#include <2geom/point.h>
+#include <2geom/pathvector.h>
+#include <2geom/svg-path-parser.h>
+#include <2geom/svg-path-writer.h>
+
+#include "planar-graph.h"
+#include "testing.h"
+
+using namespace Geom;
+
+#define PV(d) (parse_svg_path(d))
+#define PTH(d) (std::move(PV(d)[0]))
+#define REV(d) ((PV(d)[0]).reversed())
+
+/** An edge label for the purpose of tests. */
+struct TestLabel
+{
+    unsigned reversal_count = 0, merge_count = 0, detachment_count = 0;
+    void onReverse() { reversal_count++; }
+    void onMergeWith(TestLabel const &) { merge_count++; }
+    void onDetach() { detachment_count++; }
+};
+
+using TestGraph = PlanarGraph<TestLabel>;
+
+static std::vector<TestLabel> extract_labels(TestGraph const &graph)
+{
+    // Find labels of edges remaining in the graph.
+    std::vector<TestLabel> result;
+    for (auto &e : graph.getEdges()) {
+        if (!e.detached) {
+            result.push_back(e.label);
+        }
+    }
+    return result;
+}
+
+class PlanarGraphTest : public ::testing::Test
+{
+};
+
+/** Test edge insertion and vertex clumping to within the tolerance. */
+TEST(PlanarGraphTest, EdgeInsertion)
+{
+    double const precision = 1e-3;
+    auto graph = TestGraph(precision);
+    graph.insertEdge(PTH("M 0, 0 L 1, 0"));
+    graph.insertEdge(PTH("M 0, 1 L 1, 1"));      // } Endpoints near
+    graph.insertEdge(PTH("M 1, 0 L 1, 1.0009")); // } but not exact.
+
+    auto vertices = graph.getVertices();
+
+    // Test vertex clumping within the given precision
+    EXPECT_EQ(vertices.size(), 4);
+    EXPECT_EQ(graph.numEdges(), 3);
+
+    // Test lexicographic vertex position sorting by X and then Y
+    EXPECT_EQ(vertices.front().point(), Point(0, 0));
+    auto after = std::next(vertices.begin());
+    EXPECT_EQ(after->point(), Point(0, 1));
+    ++after;
+    EXPECT_EQ(after->point(), Point(1, 0));
+    EXPECT_TRUE(are_near(vertices.back().point(), Point(1, 1), precision));
+
+    EXPECT_FALSE(graph.isRegularized());
+}
+
+/** Test PlanarGraph<T>::insertDetached(). */
+TEST(PlanarGraphTest, InsertDetached)
+{
+    TestGraph graph;
+    auto detached = graph.insertDetached(PTH("M 0,0 A 1,1 0,0,1 2,0 V -2 H 0 Z"));
+
+    auto const &edges = graph.getEdges();
+    EXPECT_EQ(edges.size(), 1);
+    EXPECT_TRUE(edges.at(detached).detached);
+    EXPECT_TRUE(edges.at(detached).inserted_as_detached);
+
+    EXPECT_EQ(graph.numVertices(), 0);
+    EXPECT_EQ(graph.numEdges(false), 0);
+    EXPECT_TRUE(graph.isRegularized());
+}
+
+/** Test signed area calculation. */
+TEST(PlanarGraphTest, ClosedPathArea)
+{
+    // Square with counter-clockwise oriented boundary, when imagining that the y-axis
+    // points up – expect the area to be +1.
+    auto square_positive = PTH("M 0,0 H 1 V 1 H 0 Z");
+    EXPECT_DOUBLE_EQ(TestGraph::closedPathArea(square_positive), 1.0);
+
+    // Expect negative area for a negatively oriented path.
+    auto triangle_negative = PTH("M 0,0 V 1 L 1,1 Z");
+    EXPECT_DOUBLE_EQ(TestGraph::closedPathArea(triangle_negative), -0.5);
+}
+
+/** Test the detection of direction of deviation of initially tangent paths. */
+TEST(PlanarGraphTest, Deviation)
+{
+    auto vertical_up = PTH("M 0,0 V 1");
+    auto arc_right1 = PTH("M 0,0 A 1,1 0,1,0 2,0");
+    auto arc_left1 = PTH("M 0,0 A 1,1 0,1,1 -2,0");
+    auto arc_right2 = PTH("M 0,0 A 2,2 0,1,0, 4,0");
+    auto arc_left2 = PTH("M 0,0 A 2,2 0,1,1 -4,0");
+    // A very "flat" Bézier curve deviating to the right but slower than the large arc
+    auto bezier_right = PTH("M 0,0 C 0,50 1,20 2,10");
+
+    EXPECT_TRUE(TestGraph::deviatesLeft(arc_left1, arc_left2));
+    EXPECT_TRUE(TestGraph::deviatesLeft(arc_left2, vertical_up));
+    EXPECT_TRUE(TestGraph::deviatesLeft(vertical_up, arc_right2));
+    EXPECT_TRUE(TestGraph::deviatesLeft(vertical_up, bezier_right));
+    EXPECT_TRUE(TestGraph::deviatesLeft(bezier_right, arc_right2));
+    EXPECT_TRUE(TestGraph::deviatesLeft(arc_right2, arc_right1));
+    EXPECT_TRUE(TestGraph::deviatesLeft(arc_left1, arc_right1));
+    EXPECT_TRUE(TestGraph::deviatesLeft(arc_left2, arc_right1));
+
+    EXPECT_FALSE(TestGraph::deviatesLeft(arc_right1, vertical_up));
+    EXPECT_FALSE(TestGraph::deviatesLeft(arc_right1, arc_right2));
+    EXPECT_FALSE(TestGraph::deviatesLeft(vertical_up, arc_left2));
+    EXPECT_FALSE(TestGraph::deviatesLeft(arc_left2, arc_left1));
+    EXPECT_FALSE(TestGraph::deviatesLeft(arc_right1, arc_left1));
+    EXPECT_FALSE(TestGraph::deviatesLeft(arc_right1, arc_left2));
+}
+
+/** Test sorting of incidences at a vertex by the outgoing heading. */
+TEST(PlanarGraphTest, BasicAzimuthalSort)
+{
+    TestGraph graph;
+
+    // Imagine the Y-axis pointing up (as in mathematics)!
+    bool const clockwise = true;
+    unsigned const num_rays = 9;
+    unsigned edges[num_rays];
+
+    // Insert the edges randomly but store them in what we know to be the
+    // clockwise order of outgoing azimuths from the vertex at the origin.
+    edges[7] = graph.insertEdge(PTH("M -0.2, -1 L 0, 0"));
+    edges[1] = graph.insertEdge(PTH("M -1, 0.2 L 0, 0"));
+    edges[4] = graph.insertEdge(PTH("M 0, 0 L 1, 0.2"));
+    edges[6] = graph.insertEdge(PTH("M 0.1, -1 L 0, 0"));
+    edges[2] = graph.insertEdge(PTH("M 0, 0 L -0.3, 1"));
+    edges[0] = graph.insertEdge(PTH("M -1, 0 H 0"));
+    edges[5] = graph.insertEdge(PTH("M 0, 0 L 1, -0.2"));
+    edges[3] = graph.insertEdge(PTH("M 0.2, 1 L 0, 0"));
+    edges[8] = graph.insertEdge(PTH("M -1, -0.1 L 0, 0"));
+
+    // We expect the incidence to edges[0] to be the last one
+    // in the sort order so it should appear first when going clockwise.
+    auto [origin, incidence] = graph.getIncidence(edges[0], TestGraph::Incidence::END);
+    ASSERT_TRUE(origin);
+    ASSERT_TRUE(incidence);
+
+    // Expect ±pi as the azimuth
+    EXPECT_DOUBLE_EQ(std::abs(incidence->azimuth), M_PI);
+
+    // Test sort order
+    for (unsigned i = 0; i < num_rays; i++) {
+        EXPECT_EQ(incidence->index, edges[i]);
+        incidence = (TestGraph::Incidence *)&graph.nextIncidence(*origin, *incidence, clockwise);
+    }
+}
+
+/** Test retrieval of a path inserted as an edge in both orientations. */
+TEST(PlanarGraphTest, PathRetrieval)
+{
+    TestGraph graph;
+
+    Path const path = PTH("M 0,0 L 1,1 C 2,2 4,2 5,1");
+    Path const htap = path.reversed();
+
+    auto edge = graph.insertEdge(path);
+
+    ASSERT_EQ(graph.numEdges(), 1);
+
+    auto [start_point, start_incidence] = graph.getIncidence(edge, TestGraph::Incidence::START);
+    ASSERT_TRUE(start_point);
+    ASSERT_TRUE(start_incidence);
+    EXPECT_EQ(graph.getOutgoingPath(start_incidence), path);
+    EXPECT_EQ(graph.getIncomingPath(start_incidence), htap);
+
+    auto [end_point, end_incidence] = graph.getIncidence(edge, TestGraph::Incidence::END);
+    ASSERT_TRUE(end_point);
+    ASSERT_TRUE(end_incidence);
+    EXPECT_EQ(graph.getIncomingPath(end_incidence), path);
+    EXPECT_EQ(graph.getOutgoingPath(end_incidence), htap);
+}
+
+/** Make sure the edge labels are correctly stored. */
+TEST(PlanarGraphTest, LabelRetrieval)
+{
+    TestGraph graph;
+    TestLabel label;
+
+    label.reversal_count = 420;
+    label.merge_count = 69;
+    label.detachment_count = 111;
+
+    auto edge = graph.insertEdge(PTH("M 0,0 L 1,1"), std::move(label));
+
+    auto retrieved = graph.getEdge(edge).label;
+    EXPECT_EQ(retrieved.reversal_count, 420);
+    EXPECT_EQ(retrieved.merge_count, 69);
+    EXPECT_EQ(retrieved.detachment_count, 111);
+}
+
+/** Regularization of duplicate edges. */
+TEST(PlanarGraphTest, MergeDuplicate)
+{
+    char const *const d =      "M 2,     3 H 0 C 1,4 1,5 0,6 H 10      L 8, 0";
+    char const *const near_d = "M 2.0009,3 H 0 C 1,4 1,5 0,6 H 10.0009 L 8, 0.0005";
+
+    // Test removal of perfect overlap:
+    TestGraph graph;
+    graph.insertEdge(PTH(d));
+    graph.insertEdge(PTH(d)); // exact duplicate
+    graph.regularize();
+
+    EXPECT_TRUE(graph.isRegularized());
+
+    auto remaining = extract_labels(graph);
+
+    // Expect there to be only 1 edge after regularization.
+    ASSERT_EQ(remaining.size(), 1);
+
+    EXPECT_EQ(remaining[0].merge_count, 1); // expect one merge,
+    EXPECT_EQ(remaining[0].reversal_count, 0); // no reversals,
+    EXPECT_EQ(remaining[0].detachment_count, 0); // no detachments.
+
+    // Test removal of imperfect overlaps within numerical precision
+    TestGraph fuzzy{1e-3};
+    fuzzy.insertEdge(PTH(d));
+    fuzzy.insertEdge(PTH(near_d));
+    fuzzy.regularize();
+
+    EXPECT_TRUE(fuzzy.isRegularized());
+
+    auto fuzmaining = extract_labels(fuzzy);
+    ASSERT_EQ(fuzmaining.size(), 1);
+
+    EXPECT_EQ(fuzmaining[0].merge_count, 1); // expect one merge,
+    EXPECT_EQ(fuzmaining[0].reversal_count, 0); // no reversals,
+    EXPECT_EQ(fuzmaining[0].detachment_count, 0); // no detachments.
+
+    // Test overlap of edges with oppositie orientations.
+    TestGraph twoway;
+    twoway.insertEdge(PTH(d));
+    twoway.insertEdge(REV(d));
+    twoway.regularize();
+
+    EXPECT_TRUE(twoway.isRegularized());
+
+    auto left = extract_labels(twoway);
+    ASSERT_EQ(left.size(), 1);
+
+    EXPECT_EQ(left[0].merge_count, 1); // expect one merge,
+    EXPECT_TRUE(left[0].reversal_count == 0 || left[0].reversal_count == 1); // 0 or 1 reversals
+    EXPECT_EQ(left[0].detachment_count, 0); // no detachments.
+}
+
+/** Regularization of a shorter edge overlapping a longer one. */
+TEST(PlanarGraphTest, MergePartial)
+{
+    TestGraph graph;
+    auto longer = graph.insertEdge(PTH("M 0, 0 L 10, 10"));
+    auto shorter = graph.insertEdge(PTH("M 0, 0 L 6, 6"));
+
+    EXPECT_EQ(graph.numVertices(), 3);
+
+    graph.regularize();
+
+    EXPECT_EQ(graph.numVertices(), 3);
+    EXPECT_TRUE(graph.isRegularized());
+
+    auto labels = extract_labels(graph);
+    ASSERT_EQ(labels.size(), 2);
+
+    EXPECT_EQ(labels[longer].merge_count, 0);
+    EXPECT_EQ(labels[longer].reversal_count, 0);
+    EXPECT_EQ(labels[longer].detachment_count, 0);
+
+    EXPECT_EQ(labels[shorter].merge_count, 1);
+    EXPECT_EQ(labels[shorter].reversal_count, 0);
+    EXPECT_EQ(labels[shorter].detachment_count, 0);
+
+    // Now the same thing but with edges of opposite orientations.
+    TestGraph graphopp;
+    longer = graphopp.insertEdge(PTH("M 0, 0 L 10, 0"));
+    shorter = graphopp.insertEdge(PTH("M 10, 0 L 5, 0"));
+
+    EXPECT_EQ(graphopp.numVertices(), 3);
+
+    graphopp.regularize();
+
+    EXPECT_EQ(graphopp.numVertices(), 3);
+    EXPECT_TRUE(graphopp.isRegularized());
+
+    labels = extract_labels(graphopp);
+    ASSERT_EQ(labels.size(), 2);
+
+    EXPECT_EQ(labels[longer].merge_count, 0);
+    EXPECT_EQ(labels[longer].reversal_count, 0);
+    EXPECT_EQ(labels[longer].detachment_count, 0);
+
+    EXPECT_EQ(labels[shorter].merge_count, 1);
+    EXPECT_EQ(labels[shorter].reversal_count, 0);
+    EXPECT_EQ(labels[shorter].detachment_count, 0);
+}
+
+/** Regularization of a Y-split. */
+TEST(PlanarGraphTest, MergeY)
+{
+    TestGraph graph;
+    auto left = graph.insertEdge(PTH("M 1 0 V 1 L 0, 2"));
+    auto right = graph.insertEdge(PTH("M 1,0 V 1 L 2, 2"));
+
+    EXPECT_EQ(graph.numVertices(), 3);
+    graph.regularize();
+    EXPECT_EQ(graph.numVertices(), 4);
+
+    auto edges = graph.getEdges();
+    EXPECT_EQ(edges.size(), 3);
+
+    EXPECT_TRUE(are_near(edges[right].start->point(), Point(1, 1)));
+}
+
+/** Test reversal of a wrongly oriented teardrop */
+TEST(PlanarGraphTest, Teardrop)
+{
+    TestGraph graph;
+    auto loop = graph.insertEdge(PTH("M 1,0 A 1,1, 0,0,1 0,1 L 2,2 V 1 H 1 V 0"));
+    // Insert a few unrelated edges
+    auto before = graph.insertEdge(PTH("M 1,0 H 10"));
+    auto after = graph.insertEdge(PTH("M 1,0 H -10"));
+
+    EXPECT_EQ(graph.numVertices(), 3);
+
+    graph.regularize();
+
+    EXPECT_EQ(graph.numVertices(), 3);
+    auto [start_vertex, start_incidence] = graph.getIncidence(loop, TestGraph::Incidence::START);
+    auto [end_vertex, end_incidence] = graph.getIncidence(loop, TestGraph::Incidence::END);
+
+    EXPECT_EQ(start_vertex, end_vertex);
+    ASSERT_NE(start_vertex, nullptr);
+
+    // Check that the incidences have been swapped
+    EXPECT_EQ(start_vertex->cyclicNextIncidence(end_incidence), start_incidence);
+    EXPECT_EQ(start_vertex->cyclicPrevIncidence(start_incidence), end_incidence);
+    auto [b, before_incidence] = graph.getIncidence(before, TestGraph::Incidence::START);
+    EXPECT_EQ(start_vertex->cyclicNextIncidence(before_incidence), end_incidence);
+    auto [a, after_incidence] = graph.getIncidence(after, TestGraph::Incidence::START);
+    EXPECT_EQ(start_vertex->cyclicPrevIncidence(after_incidence), start_incidence);
+}
+
+/** Test the regularization of a lasso-shaped path. */
+TEST(PlanarGraphTest, ReglueLasso)
+{
+    TestGraph graph;
+    // Insert a lasso-shaped path (a teardrop with initial self-overlap).
+    auto original_lasso = graph.insertEdge(PTH("M 0,0 V 1 C 0,2 1,3 1,4 "
+                                               "A 1,1 0,1,1 -1,4 C -1,3 0,2 0,1 V 0"));
+    EXPECT_EQ(graph.numVertices(), 1);
+
+    graph.regularize();
+    EXPECT_EQ(graph.numVertices(), 2);
+    EXPECT_EQ(graph.numEdges(false), 2);
+    EXPECT_TRUE(graph.getEdge(original_lasso).detached);
+
+    auto const &edges = graph.getEdges();
+    // Find the edge from origin and ensure it got glued.
+    auto from_origin = std::find_if(edges.begin(), edges.end(), [](auto const &edge) -> bool {
+        return !edge.detached && (edge.start->point() == Point(0, 0) ||
+                                    edge.end->point() == Point(0, 0));
+    });
+    ASSERT_NE(from_origin, edges.end());
+    ASSERT_EQ(from_origin->label.merge_count, 1);
+}
+
+/** Test the removal of a collapsed loop. */
+TEST(PlanarGraphTest, RemoveCollapsed)
+{
+    TestGraph graph;
+    // Insert a collapsed loop
+    auto collapsed = graph.insertEdge(PTH("M 0,0 L 1,1 L 0,0"));
+    ASSERT_EQ(graph.numEdges(), 1);
+    graph.regularize();
+    ASSERT_EQ(graph.numEdges(false), 0);
+    ASSERT_TRUE(graph.getEdge(collapsed).detached);
+
+    TestGraph fuzzy(1e-3);
+    // Insert a nearly collapsed loop
+    auto nearly = fuzzy.insertEdge(PTH("M 0,0 H 2 V 0.001 L 1,0 H 0"));
+    ASSERT_EQ(fuzzy.numEdges(), 1);
+    fuzzy.regularize();
+    ASSERT_EQ(fuzzy.numEdges(false), 0);
+    ASSERT_TRUE(fuzzy.getEdge(nearly).detached);
+}
+
+/** Test regularization of straddling runs. */
+TEST(PlanarGraphTest, RemoveWisp)
+{
+    TestGraph graph;
+    // Insert a horizontal segment at the origin towards positive X:
+    graph.insertEdge(PTH("M 0 0 H 1"));
+    // Insert a path with a collapsed Bézier curve towards negative X:
+    graph.insertEdge(PTH("M 0 0 C -1 0 -1 0 0 0"));
+    graph.regularize();
+
+    // Ensure that the folded Bézier is removed (and no segfault occurs).
+    EXPECT_EQ(graph.numEdges(false), 1);
+}
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :