pool/lib2geom
SHA256
2
0
Fork 1
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity

add 96.patch to fix instable intersection tests

Browse Source 
OBS-URL: https://build.opensuse.org/package/show/graphics/lib2geom?expand=0&rev=8
This commit is contained in:
Dirk Stoecker 2023-07-27 20:42:30 +00:00 committed by Git OBS Bridge
parent 380499f80a
commit 50a1db61c1
3 changed files with 420 additions and 0 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

413
96.patch Normal file
View File

@ -0,0 +1,413 @@
From 3e58f8591506622a06ec958a2bd6503ed0ee1a98 Mon Sep 17 00:00:00 2001
From: Rafael Siejakowski <rs@rs-math.net>
Date: Thu, 12 Jan 2023 20:23:52 +0100
Subject: [PATCH] Report overlapping segments as intersecting
Ensure that when two line segments overlap completely (because they are
either identical or one is a reversed copy of the other), both of their
endpoints are returned as intersections between them. Furthermore, make
sure that when segments overlap only partially, they are still reported
as intersecting (either at both endpoints of the overlapping portion or
at a single point, in case numerical errors prevent the exact detection
of their collinearity).
Co-authored-by: Thomas Holder <thomas@thomas-holder.de>
---
src/2geom/bezier-curve.cpp | 116 ++++++++++++++++++---
tests/line-test.cpp | 205 ++++++++++++++++++++++++++++++++++++-
2 files changed, 304 insertions(+), 17 deletions(-)
diff --git a/src/2geom/bezier-curve.cpp b/src/2geom/bezier-curve.cpp
index ca0f7877..5cf4e96e 100644
--- a/src/2geom/bezier-curve.cpp
+++ b/src/2geom/bezier-curve.cpp
@@ -4,7 +4,7 @@
* MenTaLguY <mental@rydia.net>
* Marco Cecchetti <mrcekets at gmail.com>
* Krzysztof Kosiński <tweenk.pl@gmail.com>
- *
+ *
* Copyright 2007-2009 Authors
*
* This library is free software; you can redistribute it and/or
@@ -37,7 +37,7 @@
#include <2geom/nearest-time.h>
#include <2geom/polynomial.h>
-namespace Geom
+namespace Geom
{
/**
@@ -102,8 +102,8 @@ namespace Geom
* @brief Bezier curve with compile-time specified order.
*
* @tparam degree unsigned value indicating the order of the Bezier curve
- *
- * @relates BezierCurve
+ *
+ * @relates BezierCurve
* @ingroup Curves
*/
@@ -349,25 +349,109 @@ Coord BezierCurveN<1>::nearestTime(Point const& p, Coord from, Coord to) const
else return from + t*(to-from);
}
-/* Specialized intersection routine for line segments. */
+/* Specialized intersection routine for line segments.
+ *
+ * NOTE: if the segments overlap in part or in full, the function returns the start and end
+ * of the overlapping subsegment as intersections. This behavior is more useful than throwing
+ * Geom::InfinitelyManySolutions.
+ */
template <>
std::vector<CurveIntersection> BezierCurveN<1>::intersect(Curve const &other, Coord eps) const
{
std::vector<CurveIntersection> result;
// only handle intersections with other LineSegments here
- if (other.isLineSegment()) {
- Line this_line(initialPoint(), finalPoint());
- Line other_line(other.initialPoint(), other.finalPoint());
- result = this_line.intersect(other_line);
- filter_line_segment_intersections(result, true, true);
+ if (!other.isLineSegment()) {
+ // pass all other types to the other curve
+ result = other.intersect(*this, eps);
+ transpose_in_place(result);
return result;
}
- // pass all other types to the other curve
- result = other.intersect(*this, eps);
- transpose_in_place(result);
- return result;
+ Point const u = finalPoint() - initialPoint();
+ Point const v = other.initialPoint() - other.finalPoint();
+ if (u.isZero() || v.isZero()) {
+ return {};
+ }
+ Coord const uv = u.length() * v.length();
+ Coord const u_cross_v = cross(u, v);
+ bool const segments_are_parallel = std::abs(u_cross_v) < eps * uv;
+
+ if (segments_are_parallel) {
+ // We check if the segments lie on the same line.
+ Coord const distance_between_lines = std::abs(cross(u.normalized(),
+ other.initialPoint() - initialPoint()));
+ if (distance_between_lines > eps) {
+ // Segments are parallel but aren't part of the same line => no intersections.
+ return {};
+ }
+ // The segments are on the same line, so they may overlap in part or in full.
+ // Look for the times on this segment's line at which the line passes through
+ // the initial and final points of the other segment.
+ Coord const ulen_inverse = 1.0 / u.length();
+ auto const time_of_passage = [&](Point const &point_on_line) -> Coord {
+ return dot(u.normalized(), point_on_line - initialPoint()) * ulen_inverse;
+ };
+ // Find the range of times on our segment where we travel through the other segment.
+ auto time_in_other = Interval(time_of_passage(other.initialPoint()),
+ time_of_passage(other.finalPoint()));
+ Coord const eps_utime = eps * ulen_inverse;
+ if (time_in_other.min() > 1 + eps_utime || time_in_other.max() < -eps_utime) {
+ return {};
+ }
+
+ // Create two intersections, one at each end of the overlap interval.
+ Coord last_time = infinity();
+ for (Coord t : {time_in_other.min(), time_in_other.max()}) {
+ t = std::clamp(t, 0.0, 1.0);
+ if (t == last_time) {
+ continue;
+ }
+ last_time = t;
+ auto const point = pointAt(t);
+ Coord const other_t = std::clamp(dot(v.normalized(), other.initialPoint() - point) / v.length(), 0.0, 1.0);
+ auto const other_pt = other.pointAt(other_t);
+ if (distance(point, other_pt) > eps) {
+ continue;
+ }
+ result.emplace_back(t, other_t, middle_point(point, other_pt));
+ }
+ return result;
+ } else {
+ // Segments are not collinear - there is 0 or 1 intersection.
+ // This is the typical case so it's important for it to be fast.
+ Point const w = other.initialPoint() - initialPoint();
+ Coord candidate_time_this = cross(w, v) / u_cross_v;
+
+ /// Filter out candidate times outside of the interval [0, 1] fuzzed so as to accommodate
+ /// for epsilon.
+ auto const is_outside_seg = [eps](Coord t, Coord len) -> bool {
+ Coord const arclen_coord = t * len;
+ return arclen_coord < -eps || arclen_coord > len + eps;
+ };
+
+ if (is_outside_seg(candidate_time_this, u.length())) {
+ return {};
+ }
+
+ Coord candidate_time_othr = cross(u, w) / u_cross_v;
+ if (is_outside_seg(candidate_time_othr, v.length())) {
+ return {};
+ }
+
+ // Even if there was some fuzz in the interval, we must now restrict to [0, 1] and verify
+ // that the intersection found is still within epsilon precision (the fuzz may have been too
+ // large, depending on the angle between the intervals).
+ candidate_time_this = std::clamp(candidate_time_this, 0.0, 1.0);
+ candidate_time_othr = std::clamp(candidate_time_othr, 0.0, 1.0);
+
+ auto const pt_this = pointAt(candidate_time_this);
+ auto const pt_othr = other.pointAt(candidate_time_othr);
+ if (distance(pt_this, pt_othr) > eps) {
+ return {};
+ }
+ return { CurveIntersection(candidate_time_this, candidate_time_othr, middle_point(pt_this, pt_othr)) };
+ }
}
/** @brief Find intersections of a low-degree Bézier curve with a line segment.
@@ -547,7 +631,7 @@ static Coord bezier_length_internal(std::vector<Point> &v1, Coord tolerance, int
* error tolerance, we can be sure that the true value is no further than
* 0.5 * tolerance from their arithmetic mean. When it's larger, we recursively
* subdivide the Bezier curve into two parts and add their lengths.
- *
+ *
* We cap the maximum number of subdivisions at 256, which corresponds to 8 levels.
*/
Coord lower = distance(v1.front(), v1.back());
@@ -558,7 +642,7 @@ static Coord bezier_length_internal(std::vector<Point> &v1, Coord tolerance, int
if (upper - lower <= 2*tolerance || level >= 8) {
return (lower + upper) / 2;
}
-
+
std::vector<Point> v2 = v1;
diff --git a/tests/line-test.cpp b/tests/line-test.cpp
index 0625566d..b4b76c71 100644
--- a/tests/line-test.cpp
+++ b/tests/line-test.cpp
@@ -4,7 +4,7 @@
*//*
* Authors:
* Krzysztof Kosiński <tweenk.pl@gmail.com>
- *
+ *
* Copyright 2015 Authors
*
* This library is free software; you can redistribute it and/or
@@ -183,3 +183,206 @@ TEST(LineTest, Intersection) {
EXPECT_TRUE(a.intersect(lsb).empty());
EXPECT_TRUE(b.intersect(lsa).empty());
}
+
+#define RAND10 g_random_double_range(-10.0, 10.0)
+
+/** Ensure that intersections are reported at endpoints of
+ * identical (overlapping) segments (reversed or not).
+ */
+TEST(LineTest, CoincidingIntersect)
+{
+ auto const eps = 1e-14;
+ auto const check_endpoint_intersections = [=](LineSegment const &s1, LineSegment const &s2) {
+ auto xings = s1.intersect(s2, eps);
+ ASSERT_EQ(xings.size(), 2);
+ EXPECT_TRUE(are_near(xings[0], s1.initialPoint()));
+ EXPECT_TRUE(are_near(xings[1], s1.finalPoint()));
+ EXPECT_intersections_valid(s1, s2, xings, eps);
+ };
+
+ // This fails on 6f7dfdc0317362bf294fed54ad06d14ac14ad809
+ check_endpoint_intersections(LineSegment(Point{1, 0}, Point{0, 0}),
+ LineSegment(Point{0, 0}, Point{1, 0}));
+
+ g_random_set_seed(0x13370AFA);
+ for (size_t _ = 0; _ < 10'000; _++) {
+ auto const a = Point(RAND10, RAND10);
+ auto const b = Point(RAND10, RAND10);
+ auto const ab = LineSegment(a, b);
+ auto const ba = LineSegment(b, a);
+ check_endpoint_intersections(ab, ab);
+ check_endpoint_intersections(ba, ba);
+ check_endpoint_intersections(ab, ba);
+ }
+}
+
+/** Test whether at least one intersection is detected
+ * when segments have an overlapping portion (due to numerics,
+ * parallel segments may not be exactly detected as parallel).
+*/
+TEST(LineTest, OverlappingIntersect)
+{
+ g_random_set_seed(0xCAFECAFE);
+ // Suppose the segments are [A, B] and [C, D].
+ // Case 1: A=C, B halfway between A and D
+ for (size_t _ = 0; _ < 10'000; _++)
+ {
+ auto const a = Point(RAND10, RAND10);
+ auto const d = Point(RAND10, RAND10);
+ auto const b = middle_point(a, d);
+ auto const ab = LineSegment(a, b);
+ auto const cd = LineSegment(a, d);
+ auto xings = ab.intersect(cd);
+ ASSERT_FALSE(xings.empty());
+ EXPECT_TRUE(are_near(xings[0], ab.initialPoint()));
+ EXPECT_intersections_valid(ab, cd, xings, 1e-12);
+ }
+
+ // Case 2: AB wholly contained inside CD
+ for (size_t _ = 0; _ < 10'000; _++)
+ {
+ auto const c = Point(RAND10, RAND10);
+ auto const d = Point(RAND10, RAND10);
+ auto const a = lerp(0.25, c, d);
+ auto const b = lerp(0.75, c, d);
+ auto const ab = LineSegment(a, b);
+ auto const cd = LineSegment(a, d);
+ auto xings = ab.intersect(cd);
+ ASSERT_FALSE(xings.empty());
+ EXPECT_TRUE(are_near(xings[0], ab.initialPoint()));
+ EXPECT_intersections_valid(ab, cd, xings, 1e-12);
+ }
+}
+
+/** Ensure that intersections are reported when the segments are separated
+ * from one another by less than the passed epsilon.
+ */
+TEST(LineTest, AlmostIntersect)
+{
+ for (double eps : {1e-12, 1e-11, 1e-10, 1e-9, 1e-8, 1e-7, 1e-6, 1e-3, 1.0}) {
+ auto const vertical = LineSegment(Point(0.0, 0.5 * eps), Point(0.0, 1.0));
+ auto const horizontal = LineSegment(Point(0.5 * eps, 0.0), Point(1.0, 0.0));
+ auto const butt = LineSegment(Point(0.0, -0.49 * eps), Point(0.0, -1.0));
+ auto const too_far = LineSegment(Point(0.0, -0.51 * eps), Point(0.0, -1.0));
+ auto xings = vertical.intersect(horizontal, eps);
+ ASSERT_FALSE(xings.empty());
+ EXPECT_intersections_valid(vertical, horizontal, xings, eps);
+ xings = vertical.intersect(butt, eps);
+ ASSERT_FALSE(xings.empty());
+ EXPECT_intersections_valid(vertical, butt, xings, eps);
+ xings = vertical.intersect(too_far, eps);
+ ASSERT_TRUE(xings.empty());
+ }
+}
+
+/** Ensure that overlaps are found as precisely as possible even when epsilon is large. */
+TEST(LineTest, FuzzyOverlap)
+{
+ auto const ab = LineSegment(Point(0, 0), Point(0, 20));
+ auto const cd = LineSegment(Point(0, 10), Point(0, 30));
+ auto xings = ab.intersect(cd, 4); // extra large eps
+ ASSERT_EQ(xings.size(), 2);
+ EXPECT_DOUBLE_EQ(xings[0].point()[1], 10);
+ EXPECT_DOUBLE_EQ(xings[0].first, 0.5);
+ EXPECT_DOUBLE_EQ(xings[0].second, 0.0);
+ EXPECT_DOUBLE_EQ(xings[1].point()[1], 20);
+ EXPECT_DOUBLE_EQ(xings[1].first, 1.0);
+ EXPECT_DOUBLE_EQ(xings[1].second, 0.5);
+}
+
+/** Ensure that adjacent collinear segments are still detected as intersecting at
+ * their exact common endpoint even when epsilon is large. */
+TEST(LineTest, FuzzyEndToEnd)
+{
+ auto const ab = LineSegment(Point(0, 0), Point(0, 10));
+ auto const cd = LineSegment(Point(0, 10), Point(0, 30));
+ auto xings = ab.intersect(cd, 4); // extra large eps
+ ASSERT_EQ(xings.size(), 1);
+ EXPECT_DOUBLE_EQ(xings[0].point()[1], 10);
+ EXPECT_DOUBLE_EQ(xings[0].first, 1.0);
+ EXPECT_DOUBLE_EQ(xings[0].second, 0.0);
+}
+
+/** Ensure that a single intersection is found when the end-to-end
+ * juncture contains a gap smaller than epsilon.
+ */
+TEST(LineTest, AlmostTouch)
+{
+ auto const ab = LineSegment(Point(0, 0), Point(0, 99));
+ auto const cd = LineSegment(Point(0, 101), Point(0, 200));
+ auto xings = ab.intersect(cd, 12); // extra large eps
+ ASSERT_EQ(xings.size(), 1);
+ auto &x = xings[0];
+ EXPECT_DOUBLE_EQ(x.point()[X], 0);
+ EXPECT_DOUBLE_EQ(x.point()[Y], 100);
+ EXPECT_DOUBLE_EQ(x.first, 1.0);
+ EXPECT_DOUBLE_EQ(x.second, 0.0);
+}
+
+/** Ensure that a T-arrangement of segments has a single intersection
+ * detected if and only if the gap between the vertical part and the
+ * horizontal part is less than epsilon.
+ */
+TEST(LineTest, TBone)
+{
+ auto const horizontal = LineSegment(Point(-1, 1), Point(1, 1));
+ g_random_set_seed(0x01234567);
+
+ for (int exponent = -2; exponent > -13; exponent--) {
+ double const eps = std::pow(10, exponent);
+ for (size_t _ = 0; _ < 10'000; _++) {
+ auto const distance = g_random_double_range(0.0, 2.0 * eps);
+ size_t const expected_crossing_count = (size_t)(distance <= eps);
+ auto const xings = horizontal.intersect(LineSegment(Point(0, 0), Point(0, 1.0 - distance)), eps);
+ ASSERT_EQ(xings.size(), expected_crossing_count);
+ if (expected_crossing_count) {
+ auto const &x = xings[0];
+ EXPECT_DOUBLE_EQ(x.point()[X], 0.0);
+ EXPECT_DOUBLE_EQ(x.point()[Y], 1.0 - (0.5 * distance));
+ EXPECT_DOUBLE_EQ(x.first, 0.5);
+ EXPECT_DOUBLE_EQ(x.second, 1.0);
+ }
+ }
+ }
+}
+
+/** Ensure that the normal pushoff is detected as intersecting the original
+ * segment if and only if the push off distance is less than epsilon.
+ */
+TEST(LineTest, PushOff)
+{
+ auto const seg = LineSegment(Point(0, 0), Point(5, 3));
+ auto const normal = (seg.finalPoint() - seg.initialPoint()).cw().normalized();
+ g_random_set_seed(0xB787A350);
+
+ for (int exponent = 1; exponent > -13; exponent--) {
+ double const eps = std::pow(10, exponent);
+ for (size_t _ = 0; _ < 10'000; _++) {
+ auto const pushoff_distance = g_random_double_range(0.0, 2.0 * eps);
+ std::unique_ptr<LineSegment> pushed_off{
+ dynamic_cast<LineSegment *>(
+ seg.transformed(
+ Geom::Translate(pushoff_distance * normal)
+ )
+ ) };
+ auto const xings = seg.intersect(*pushed_off, eps);
+ bool const too_far = pushoff_distance > eps;
+ EXPECT_EQ(xings.empty(), too_far);
+ for (auto const &x : xings) {
+ EXPECT_TRUE(are_near(x.first, 0.0, eps) or are_near(x.first, 1.0, eps));
+ EXPECT_TRUE(are_near(x.second, 0.0, eps) or are_near(x.second, 1.0, eps));
+ }
+ }
+ }
+}
+
+/*
+ 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 :
--
GitLab

5
lib2geom.changes
View File

@ -1,3 +1,8 @@
-------------------------------------------------------------------
Thu Jul 27 20:40:32 UTC 2023 - Dirk Stoecker <opensuse@dstoecker.de>
- add 96.patch to fix instable intersection tests
-------------------------------------------------------------------
Mon Jul 24 21:11:01 UTC 2023 - thod_@gmx.de

2
lib2geom.spec
View File

@ -32,6 +32,8 @@ Group: System/Libraries
Source0: %{url}/-/archive/%{short_version}/%{name}-%{short_version}.tar.gz
# PATCH-FIX-OPENSUSE
Patch1: fix-pkgconfig-libdir-path.patch
# PATCH-FIX-UPSTREAM fix instable tests
Patch2: https://gitlab.com/inkscape/lib2geom/-/merge_requests/96.patch
BuildRequires: cmake >= 2.6
BuildRequires: gcc-c++
BuildRequires: glib2