GCC Code Coverage Report

Directory: ./
File: src/2geom/parting-point.cpp
Date: 2024-03-18 17:01:34
Exec Total Coverage
Lines: 64 72 88.9%
Functions: 3 3 100.0%
Branches: 69 116 59.5%
Line Branch Exec Source
1 /** @file Implementation of parting_point(Path const&, Path const&, Coord)
2 */
3 /* An algorithm to find the first parting point of two paths.
4 *
5 * Authors:
6 * Rafał Siejakowski <rs@rs-math.net>
7 *
8 * Copyright 2022 the 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 <2geom/path.h>
35 #include <2geom/point.h>
36
37 namespace Geom
38 {
39
40 30 PathIntersection parting_point(Path const &first, Path const &second, Coord precision)
41 {
42 30 Path const *paths[2] = { &first, &second };
43
2/4
✓ Branch 2 taken 30 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 30 times.
✗ Branch 6 not taken.
 30 Point const starts[2] = { first.initialPoint(), second.initialPoint() };
44
45
3/4
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 29 times.
 30 if (!are_near(starts[0], starts[1], precision)) {
46 1 auto const invalid = PathTime(0, -1.0);
47
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 return PathIntersection(invalid, invalid, middle_point(starts[0], starts[1]));
48 }
49
50
5/10
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 29 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 29 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 29 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 29 times.
 29 if (first.empty() || second.empty()) {
51 ✗ auto const start_time = PathTime(0, 0.0);
52 ✗ return PathIntersection(start_time, start_time, middle_point(starts[0], starts[1]));
53 }
54
55
2/4
✓ Branch 2 taken 29 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 29 times.
✗ Branch 6 not taken.
 29 size_t const curve_count[2] = { first.size(), second.size() };
56
2/4
✓ Branch 3 taken 29 times.
✗ Branch 4 not taken.
✓ Branch 8 taken 29 times.
✗ Branch 9 not taken.
 29 Coord const max_time[2] = { first.timeRange().max(), second.timeRange().max() };
57
58 /// Curve indices up until which the paths are known to overlap
59 29 unsigned pos[2] = { 0, 0 };
60 /// Curve times on the curves with indices pos[] up until which the
61 /// curves are known to overlap ahead of the nodes.
62 29 Coord curve_times[2] = { 0.0, 0.0 };
63
64 29 bool leg = 0; ///< Flag indicating which leg is stepping on the ladder
65 29 bool just_changed_legs = false;
66
67 /* The ladder algorithm takes steps along the two paths, as if they the stiles of
68 * an imaginary ladder. Note that the nodes (X) on boths paths may not coincide:
69 *
70 * paths[0] START--------X-----------X-----------------------X---------X----> ...
71 * paths[1] START--------------X-----------------X-----------X--------------> ...
72 *
73 * The variables pos[0], pos[1] are the indices of the nodes we've cleared so far;
74 * i.e., we know that the portions before pos[] overlap.
75 *
76 * In each iteration of the loop, we move to the next node along one of the paths;
77 * the variable `leg` tells us which path. We find the point nearest to that node
78 * on the first unprocessed curve of the other path and check the curve time.
79 *
80 * Suppose the current node positions are denoted by P; one possible location of
81 * the nearest point (N) to the next node is:
82 *
83 * ----P------------------N--X---- paths[!leg]
84 * --------P--------------X------- paths[leg] (we've stepped forward from P to X)
85 *
86 * We detect this situation when we find that the curve time of N is < 1.0.
87 * We then create a trimmed version of the top curve so that it corresponds to
88 * the current bottom curve:
89 *
90 * ----P----------------------N--X---------- paths[!leg]
91 * [------------------] trimmed curve
92 * --------P------------------X------------- paths[leg]
93 *
94 * Using isNear(), we can compare the trimmed curve to the front curve (P--X) on
95 * paths[leg]; if they are indeed near, then pos[leg] can be incremented.
96 *
97 * Another possibility is that we overstep the end of the other curve:
98 *
99 * ----P-----------------X------------------ paths[!leg]
100 * N
101 * --------P------------------X------------- paths[leg]
102 *
103 * so the nearest point N now coincides with a node on the top path. We detect
104 * this situation by observing that the curve time of N is close to 1. In case
105 * of such overstep, we change legs by flipping the `leg` variable:
106 *
107 * ----P-----------------X------------------ paths[leg]
108 * --------P------------------X------------- paths[!leg]
109 *
110 * We can now continue the stepping procedure, but the next step will be taken on
111 * the path `paths[leg]`, so it should be a shorter step (if it isn't, the paths
112 * must have diverged and we're done):
113 *
114 * ----P-----------------X------------------ paths[leg]
115 * --------P-------------N----X------------- paths[!leg]
116 *
117 * Another piece of data we hold on to are the curve times on the current curves
118 * up until which the paths have been found to coincide. In other words, at every
119 * step of the algorithm we know that the curves agree up to the path-times
120 * PathTime(pos[i], curve_times[i]).
121 *
122 * In the situation mentioned just above, the times (T) will be as follows:
123 *
124 * ----P---T-------------X------------------ paths[leg]
125 *
126 * --------P-------------N----X------------- paths[!leg]
127 * T
128 *
129 * In this example, the time on top path is > 0.0, since the T mark is further
130 * ahead than P on that path. This value of the curve time is needed to correctly
131 * crop the top curve for the purpose of the isNear() comparison:
132 *
133 * ----P---T-------------X---------- paths[leg]
134 * [-------------] comparison curve (cropped from paths[leg])
135 * [-------------] comparison curve (cropped from paths[!leg])
136 * --------P-------------N----X----- paths[!leg]
137 * T
138 *
139 * In fact, the lower end of the curve time range for cropping is always
140 * given by curve_times[i].
141 *
142 * The iteration ends when we find that the two paths have diverged or when we
143 * reach the end. When that happens, the positions and curve times will be
144 * the PathTime components of the actual point of divergence on both paths.
145 */
146
147 /// A closure to crop and compare the curve pieces ([----] in the diagrams above).
148 29 auto const pieces_agree = [&](Coord time_on_other) -> bool {
149 65 Curve *pieces[2];
150 // The leg-side curve is always cropped to the end:
151
2/4
✓ Branch 1 taken 65 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 65 times.
✗ Branch 5 not taken.
 65 pieces[ leg] = paths[ leg]->at(pos[ leg]).portion(curve_times[ leg], 1.0);
152 // The other one is cropped to a variable curve time:
153
2/4
✓ Branch 1 taken 65 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 65 times.
✗ Branch 5 not taken.
 65 pieces[!leg] = paths[!leg]->at(pos[!leg]).portion(curve_times[!leg], time_on_other);
154
1/2
✓ Branch 1 taken 65 times.
✗ Branch 2 not taken.
 65 bool ret = pieces[0]->isNear(*pieces[1], precision);
155
1/2
✓ Branch 0 taken 65 times.
✗ Branch 1 not taken.
 65 delete pieces[0];
156
1/2
✓ Branch 0 taken 65 times.
✗ Branch 1 not taken.
 65 delete pieces[1];
157 65 return ret;
158 29 };
159
160 /// A closure to skip degenerate curves; returns true if we reached the end.
161 29 auto const skip_degenerates = [&](size_t which) -> bool {
162
2/2
✓ Branch 2 taken 10 times.
✓ Branch 3 taken 170 times.
 180 while (paths[which]->at(pos[which]).isDegenerate()) {
163 10 ++pos[which];
164 10 curve_times[which] = 0.0;
165
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 if (pos[which] == curve_count[which]) {
166 ✗ return true; // We've reached the end
167 }
168 }
169 170 return false;
170 29 };
171
172 // Main loop of the ladder algorithm.
173
4/4
✓ Branch 0 taken 89 times.
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 85 times.
✓ Branch 3 taken 4 times.
 103 while (pos[0] < curve_count[0] && pos[1] < curve_count[1]) {
174 // Skip degenerate curves if any.
175
2/4
✓ Branch 1 taken 85 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 85 times.
 85 if (skip_degenerates(0)) {
176 ✗ break;
177 }
178
2/4
✓ Branch 1 taken 85 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 85 times.
 85 if (skip_degenerates(1)) {
179 ✗ break;
180 }
181
182 // Try to step to the next node with the current leg and see what happens.
183 85 Coord forward_coord = (Coord)(pos[leg] + 1);
184
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 85 times.
 85 if (forward_coord > max_time[leg]) {
185 ✗ forward_coord = max_time[leg];
186 }
187
1/2
✓ Branch 2 taken 85 times.
✗ Branch 3 not taken.
 85 auto const step_point = paths[leg]->pointAt(forward_coord);
188
2/4
✓ Branch 1 taken 85 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 85 times.
✗ Branch 5 not taken.
 85 auto const time_on_other = paths[!leg]->at(pos[!leg]).nearestTime(step_point);
189
190
4/4
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 37 times.
✓ Branch 3 taken 28 times.
✓ Branch 4 taken 57 times.
 266 if (are_near(time_on_other, 1.0, precision) &&
191
6/10
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 48 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 28 times.
✓ Branch 8 taken 20 times.
✓ Branch 9 taken 37 times.
✓ Branch 10 taken 48 times.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 181 are_near(step_point, paths[!leg]->pointAt(pos[!leg] + 1), precision))
192 { // The step took us very near to the first uncertified node on the other path.
193 28 just_changed_legs = false;
194 //
195 // -------PT-----------------X---------- paths[!leg]
196 // --P-----T-----------------X---------- paths[leg]
197 // ^
198 // endpoints (almost) coincide
199 //
200 // We should compare the curves cropped to the end:
201 //
202 // --------T-----------------X---------- paths[!leg]
203 // [-----------------]
204 // [-----------------]
205 // --------T-----------------X---------- paths[leg]
206
3/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 27 times.
✓ Branch 4 taken 1 times.
 28 if (pieces_agree(1.0)) {
207 // The curves are nearly identical, so we advance both positions
208 // and zero out the forward curve times.
209
2/2
✓ Branch 0 taken 54 times.
✓ Branch 1 taken 27 times.
 81 for (size_t i = 0; i < 2; i++) {
210 54 pos[i]++;
211 54 curve_times[i] = 0.0;
212 }
213 } else { // We've diverged.
214 1 break;
215 }
216
2/2
✓ Branch 0 taken 37 times.
✓ Branch 1 taken 20 times.
 57 } else if (time_on_other < 1.0 - precision) {
217 37 just_changed_legs = false;
218
219 // The other curve is longer than our step! We trim the other curve to the point
220 // nearest to the step point and compare the resulting pieces.
221 //
222 // --------T-----------------N--------X---- paths[!leg]
223 // [-----------------]
224 // [-----------------]
225 // --------T-----------------X------------- paths[leg]
226 //
227
3/4
✓ Branch 1 taken 37 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 27 times.
✓ Branch 4 taken 10 times.
 37 if (pieces_agree(time_on_other)) { // The curve pieces are near to one another!
228 // We can advance our position and zero out the curve time:
229 27 pos[leg]++;
230 27 curve_times[leg] = 0.0;
231 // But on the other path, we can only advance the time, not the curve index:
232 27 curve_times[!leg] = time_on_other;
233 } else { // We've diverged.
234 10 break;
235 }
236 } else {
237 // The other curve is shorter than ours, which means that we've overstepped.
238 // We change legs and try to take a shorter step in the next iteration.
239
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if (just_changed_legs) {
240 // We already changed legs before and it didn't help, i.e., we've diverged.
241 ✗ break;
242 } else {
243 20 leg = !leg;
244 20 just_changed_legs = true;
245 }
246 }
247 }
248
249 // Compute the parting time on both paths
250
2/2
✓ Branch 2 taken 58 times.
✓ Branch 3 taken 29 times.
 87 PathTime path_times[2];
251
2/2
✓ Branch 0 taken 58 times.
✓ Branch 1 taken 29 times.
 87 for (size_t i = 0; i < 2; i++) {
252
2/2
✓ Branch 1 taken 31 times.
✓ Branch 2 taken 27 times.
 85 path_times[i] = (pos[i] == curve_count[i]) ? PathTime(curve_count[i] - 1, 1.0)
253 27 : PathTime(pos[i], curve_times[i]);
254 }
255
256 // Get the parting point from the numerically nicest source
257 29 Point parting_pt;
258
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 7 times.
 29 if (curve_times[0] == 0.0) {
259
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 parting_pt = paths[0]->pointAt(path_times[0]);
260
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 } else if (curve_times[1] == 0.0) {
261
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 parting_pt = paths[1]->pointAt(path_times[1]);
262 } else {
263 ✗ parting_pt = middle_point(first.pointAt(path_times[0]), second.pointAt(path_times[1]));
264 }
265
266 29 return PathIntersection(path_times[0], path_times[1], std::move(parting_pt));
267 }
268
269 } // namespace Geom
270
271 /*
272 Local Variables:
273 mode:c++
274 c-file-style:"stroustrup"
275 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
276 indent-tabs-mode:nil
277 fill-column:99
278 End:
279 */
280 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
281