GCC Code Coverage Report

Directory: ./
File: src/2geom/path-extrema.cpp
Date: 2024-03-18 17:01:34
Exec Total Coverage
Lines: 45 48 93.8%
Functions: 4 4 100.0%
Branches: 44 74 59.5%
Line Branch Exec Source
1 /** @file Implementation of Path::extrema()
2 */
3 /* An algorithm to find the points on a path where a given coordinate
4 * attains its minimum and maximum values.
5 *
6 * Authors:
7 * Rafał Siejakowski <rs@rs-math.net>
8 *
9 * Copyright 2022 the Authors.
10 *
11 * This library is free software; you can redistribute it and/or
12 * modify it either under the terms of the GNU Lesser General Public
13 * License version 2.1 as published by the Free Software Foundation
14 * (the "LGPL") or, at your option, under the terms of the Mozilla
15 * Public License Version 1.1 (the "MPL"). If you do not alter this
16 * notice, a recipient may use your version of this file under either
17 * the MPL or the LGPL.
18 *
19 * You should have received a copy of the LGPL along with this library
20 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 * You should have received a copy of the MPL along with this library
23 * in the file COPYING-MPL-1.1
24 *
25 * The contents of this file are subject to the Mozilla Public License
26 * Version 1.1 (the "License"); you may not use this file except in
27 * compliance with the License. You may obtain a copy of the License at
28 * http://www.mozilla.org/MPL/
29 *
30 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
31 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
32 * the specific language governing rights and limitations.
33 */
34
35 #include <2geom/curve.h>
36 #include <2geom/path.h>
37 #include <2geom/point.h>
38
39 namespace Geom {
40
41 /** Returns +1 for positive numbers, -1 for negative numbers, and 0 otherwise. */
42 30 inline static float sign(double number)
43 {
44
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 20 times.
 30 if (number > 0.0) {
45 10 return 1.0;
46
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 7 times.
 20 } else if (number < 0.0) {
47 13 return -1.0;
48 }
49 7 return 0.0;
50 }
51
52 /** @brief Determine whether the d-coordinate increases or decreases at the given path time.
53 *
54 * @param path A path.
55 * @param time A forward-normalized time on the given path.
56 * @param d The coordinate about which we want to know whether it increases.
57 * @return +1.0 if the coordinate increases, -1.0 if it decreases, 0.0 if it remains constant.
58 */
59 30 static float find_direction_of_travel(Path const &path, PathTime const &time, Dim2 d)
60 {
61
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 5 times.
 30 if (time.t == 0.0) { // We're at a node point
62
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 11 times.
 25 if (time.curve_index == 0) { // Starting point of the path.
63
2/2
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 9 times.
 14 if (path.closed()) {
64
2/4
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
✓ Branch 7 taken 5 times.
✗ Branch 8 not taken.
 5 return sign(path.initialUnitTangent()[d] + path.finalUnitTangent()[d]);
65 } else {
66
1/2
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
 9 return sign(path.initialUnitTangent()[d]);
67 }
68
3/4
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 8 times.
 11 } else if (time.curve_index == path.size()) { // End point of the path.
69
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
 3 if (path.closed()) {
70 ✗ return sign(path.initialUnitTangent()[d] + path.finalUnitTangent()[d]);
71 } else {
72
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 return sign(path.finalUnitTangent()[d]);
73 }
74 }
75
76 // Otherwise, check the average of the two unit tangent vectors.
77
2/4
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 8 times.
✗ Branch 6 not taken.
 8 auto const outgoing_tangent = path.curveAt(time.curve_index).unitTangentAt(0.0);
78
2/4
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 8 times.
✗ Branch 6 not taken.
 8 auto const incoming_tangent = path.curveAt(time.curve_index - 1).unitTangentAt(1.0);
79 8 return sign(outgoing_tangent[d] + incoming_tangent[d]);
80 }
81 // We're in the middle of a curve
82
2/4
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 5 times.
✗ Branch 6 not taken.
 5 return sign(path.curveAt(time.curve_index).unitTangentAt(time.t)[d]);
83 }
84
85 /* Find information about the points on the path where the specified
86 * coordinate attains its minimum and maximum values.
87 */
88 15 PathExtrema Path::extrema(Dim2 d) const
89 {
90 15 auto const ZERO_TIME = PathTime(0, 0);
91
92 // Handle the trivial case of an empty path.
93
2/4
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 15 times.
 15 if (empty()) {
94 ✗ auto const origin = initialPoint();
95 return PathExtrema{
96 .min_point = origin,
97 .max_point = origin,
98 .glance_direction_at_min = 0.0,
99 .glance_direction_at_max = 0.0,
100 .min_time = ZERO_TIME,
101 .max_time = ZERO_TIME
102 ✗ };
103 }
104
105 // Set up the simultaneous min-max search
106
1/2
✓ Branch 2 taken 15 times.
✗ Branch 3 not taken.
 15 Point min_point = initialPoint(), max_point = min_point;
107 15 auto min_time = ZERO_TIME, max_time = ZERO_TIME;
108 15 unsigned curve_counter = 0;
109
110 /// A closure to update the current minimum and maximum values.
111 15 auto const update_minmax = [&](Point const &new_point, Coord t) {
112
2/2
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 51 times.
 58 if (new_point[d] < min_point[d]) {
113 7 min_point = new_point;
114 7 min_time = PathTime(curve_counter, t);
115
2/2
✓ Branch 2 taken 11 times.
✓ Branch 3 taken 40 times.
 51 } else if (new_point[d] > max_point[d]) {
116 11 max_point = new_point;
117 11 max_time = PathTime(curve_counter, t);
118 }
119 73 };
120
121 // Iterate through the curves, searching for min and max.
122
5/8
✓ Branch 3 taken 15 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 15 times.
✗ Branch 8 not taken.
✓ Branch 12 taken 65 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 50 times.
✓ Branch 15 taken 15 times.
 65 for (auto const &curve : _data->curves) {
123 // Check the starting node first
124
1/2
✓ Branch 2 taken 50 times.
✗ Branch 3 not taken.
 50 update_minmax(curve.initialPoint(), 0.0);
125
126 // Check the critical points (zeroes of the derivative).
127
1/2
✓ Branch 2 taken 50 times.
✗ Branch 3 not taken.
 50 std::unique_ptr<Curve> const derivative{curve.derivative()};
128
3/4
✓ Branch 3 taken 50 times.
✗ Branch 4 not taken.
✓ Branch 12 taken 8 times.
✓ Branch 13 taken 50 times.
 58 for (auto root : derivative->roots(0.0, d)) {
129
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 update_minmax(curve.pointAt(root), root);
130 50 }
131 50 curve_counter++;
132 50 }
133
134 15 auto const other = other_dimension(d);
135 return PathExtrema{
136 .min_point = min_point,
137 .max_point = max_point,
138 30 .glance_direction_at_min = find_direction_of_travel(*this, min_time, other),
139 30 .glance_direction_at_max = find_direction_of_travel(*this, max_time, other),
140 .min_time = min_time,
141 .max_time = max_time
142
2/4
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 15 times.
✗ Branch 5 not taken.
 15 };
143 }
144
145 } // namespace Geom
146
147 /*
148 Local Variables:
149 mode:c++
150 c-file-style:"stroustrup"
151 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
152 indent-tabs-mode:nil
153 fill-column:99
154 End:
155 */
156 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
157