MailJDTourDownloadDocsQualityTestsCoverage

Which source lines and branches the tests execute. Lines 91.5 %, branches 75.0 % (minimum 85 % and 72 %). main @ 399ffe3d · 21 October 2026 · pipeline 7238.

GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 85.4% 543 / 0 / 636
Functions: 87.2% 41 / 0 / 47
Branches: 77.4% 503 / 0 / 650
presentation/GraphGeometry.cpp
Line Branch Exec Source
1 #include "GraphGeometry.h"
2
3 #include <QLineF>
4
5 #include <algorithm>
6 #include <limits>
7 #include <cmath>
8
9 namespace GraphGeometry {
10
11 namespace {
12
13 371338 double smoothstep(double edge0, double edge1, double x) {
14
1/1
✓ Branch 2 → 3 taken 371338 times.
 371338 const double t = std::clamp((x - edge0) / (edge1 - edge0), 0.0, 1.0);
15 371338 return t * t * (3 - 2 * t);
16 }
17
18 639121 double cross(QPointF a, QPointF b) { return a.x() * b.y() - a.y() * b.x(); }
19 829964 double dot(QPointF a, QPointF b) { return a.x() * b.x() + a.y() * b.y(); }
20 2094544 double length(QPointF a) { return std::hypot(a.x(), a.y()); }
21
22 722307 QPointF normalOf(QPointF a, QPointF b) {
23 722307 const QPointF d = b - a;
24 722307 const double l = length(d);
25
2/2
✓ Branch 4 → 5 taken 722153 times.
✓ Branch 4 → 8 taken 154 times.
 722307 return l > 1e-9 ? QPointF(-d.y() / l, d.x() / l) : QPointF(0, 0);
26 }
27
28 // Consecutive points closer than 0.01 px say nothing about a direction.
29 982 QList<QPointF> withoutRepeats(const QList<QPointF> &points) {
30 982 QList<QPointF> out;
31
1/1
✓ Branch 3 → 4 taken 982 times.
 982 out.reserve(points.size());
32
2/2
✓ Branch 19 → 6 taken 12652 times.
✓ Branch 19 → 20 taken 982 times.
 13634 for (const QPointF &point : points)
33
7/7
✓ Branch 8 → 9 taken 11670 times.
✓ Branch 8 → 13 taken 982 times.
✓ Branch 9 → 10 taken 11670 times.
✓ Branch 12 → 13 taken 11636 times.
✓ Branch 12 → 14 taken 34 times.
✓ Branch 15 → 16 taken 12618 times.
✓ Branch 15 → 17 taken 34 times.
 12652 if (out.isEmpty() || length(point - out.last()) > 0.01)
34
1/1
✓ Branch 16 → 17 taken 12618 times.
 12618 out.append(point);
35 982 return out;
36 ✗ }
37
38 1 QRectF boundsOf(const QList<QPointF> &points) {
39
1/2
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 1 time.
 1 if (points.isEmpty())
40 ✗ return {};
41 1 double left = points.first().x(), right = left, top = points.first().y(), bottom = top;
42
2/2
✓ Branch 22 → 11 taken 3 times.
✓ Branch 22 → 23 taken 1 time.
 4 for (const QPointF &p : points) {
43 3 left = std::min(left, p.x());
44 3 right = std::max(right, p.x());
45 3 top = std::min(top, p.y());
46 3 bottom = std::max(bottom, p.y());
47 }
48 1 return QRectF(QPointF(left, top), QPointF(right, bottom));
49 }
50
51 } // namespace
52
53 ✗ void Cutouts::clear() {
54 ✗ m_boxes.clear();
55 ✗ m_cells.clear();
56 ✗ m_indexed = false;
57 ✗ }
58
59 1644 void Cutouts::add(const QRectF &box) {
60
3/6
✓ Branch 3 → 4 taken 1644 times.
✗ Branch 3 → 7 not taken.
✓ Branch 5 → 6 taken 1644 times.
✗ Branch 5 → 7 not taken.
✓ Branch 8 → 9 taken 1644 times.
✗ Branch 8 → 11 not taken.
 1644 if (box.width() > 0 && box.height() > 0) {
61 1644 m_boxes.append(box);
62 1644 m_indexed = false;
63 }
64 1644 }
65
66 24706 void Cutouts::index() const {
67
2/2
✓ Branch 2 → 3 taken 24703 times.
✓ Branch 2 → 4 taken 3 times.
 24706 if (m_indexed)
68 24703 return;
69 3 m_cells.clear();
70
2/2
✓ Branch 23 → 6 taken 302 times.
✓ Branch 23 → 24 taken 3 times.
 305 for (int i = 0; i < m_boxes.size(); ++i) {
71 302 const QRectF reach = m_boxes.at(i).adjusted(-Fade, -Fade, Fade, Fade);
72 302 const int left = int(std::floor(reach.left() / Cell)), right = int(std::floor(reach.right() / Cell));
73 302 const int top = int(std::floor(reach.top() / Cell)), bottom = int(std::floor(reach.bottom() / Cell));
74
2/2
✓ Branch 20 → 13 taken 847 times.
✓ Branch 20 → 21 taken 302 times.
 1149 for (int column = left; column <= right; ++column)
75
2/2
✓ Branch 18 → 14 taken 1514 times.
✓ Branch 18 → 19 taken 847 times.
 2361 for (int row = top; row <= bottom; ++row)
76
2/2
✓ Branch 15 → 16 taken 1514 times.
✓ Branch 16 → 17 taken 1514 times.
 1514 m_cells[keyOf(column, row)].append(i);
77 }
78 3 m_indexed = true;
79 }
80
81 5 double Cutouts::alphaAt(QPointF point) const {
82
1/1
✓ Branch 2 → 3 taken 5 times.
 5 index();
83 5 const auto cell = m_cells.constFind(keyOf(int(std::floor(point.x() / Cell)), int(std::floor(point.y() / Cell))));
84
1/2
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 5 times.
 5 if (cell == m_cells.cend())
85 ✗ return 1;
86 5 double nearest = Fade;
87
2/2
✓ Branch 35 → 14 taken 5 times.
✓ Branch 35 → 36 taken 3 times.
 8 for (int i : *cell) {
88 5 const QRectF &box = m_boxes.at(i);
89
1/1
✓ Branch 20 → 21 taken 5 times.
 5 const double dx = std::max({box.left() - point.x(), 0.0, point.x() - box.right()});
90
2/2
✓ Branch 21 → 22 taken 1 time.
✓ Branch 21 → 23 taken 4 times.
 5 if (dx >= nearest)
91 1 continue;
92
1/1
✓ Branch 27 → 28 taken 4 times.
 4 const double dy = std::max({box.top() - point.y(), 0.0, point.y() - box.bottom()});
93
1/2
✗ Branch 28 → 29 not taken.
✓ Branch 28 → 30 taken 4 times.
 4 if (dy >= nearest)
94 ✗ continue;
95 4 nearest = std::min(nearest, std::hypot(dx, dy));
96
2/2
✓ Branch 31 → 32 taken 2 times.
✓ Branch 31 → 33 taken 2 times.
 4 if (nearest <= Clear)
97 2 return 0;
98 }
99
1/1
✓ Branch 36 → 37 taken 3 times.
 3 return smoothstep(Clear, Fade, nearest);
100 }
101
102 4 QList<int> Cutouts::candidates(QPointF a, QPointF b) const {
103 4 QList<int> out;
104
1/1
✓ Branch 2 → 3 taken 4 times.
 4 candidates(a, b, &out);
105 4 return out;
106 ✗ }
107
108 24701 void Cutouts::candidates(QPointF a, QPointF b, QList<int> *found) const {
109
1/1
✓ Branch 2 → 3 taken 24701 times.
 24701 index();
110 24701 QList<int> &out = *found;
111
1/1
✓ Branch 3 → 4 taken 24701 times.
 24701 out.clear();
112
1/2
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 24701 times.
 24701 if (m_cells.isEmpty())
113 ✗ return;
114 // Every cell the segment crosses (Amanatides–Woo); a box is registered in
115 // every cell within Fade of it, so a point near a box lies in one of them.
116 24701 int column = int(std::floor(a.x() / Cell)), row = int(std::floor(a.y() / Cell));
117 24701 const int lastColumn = int(std::floor(b.x() / Cell)), lastRow = int(std::floor(b.y() / Cell));
118 24701 const QPointF d = b - a;
119
4/4
✓ Branch 13 → 14 taken 10575 times.
✓ Branch 13 → 15 taken 14126 times.
✓ Branch 17 → 18 taken 11361 times.
✓ Branch 17 → 19 taken 13340 times.
 24701 const int stepX = d.x() > 0 ? 1 : -1, stepY = d.y() > 0 ? 1 : -1;
120 24701 const double inf = std::numeric_limits<double>::infinity();
121
4/4
✓ Branch 22 → 23 taken 21131 times.
✓ Branch 22 → 29 taken 3570 times.
✓ Branch 23 → 24 taken 10575 times.
✓ Branch 23 → 25 taken 10556 times.
 24701 double nextX = std::abs(d.x()) > 1e-12 ? ((column + (stepX > 0 ? 1 : 0)) * Cell - a.x()) / d.x() : inf;
122
4/4
✓ Branch 32 → 33 taken 21119 times.
✓ Branch 32 → 39 taken 3582 times.
✓ Branch 33 → 34 taken 11361 times.
✓ Branch 33 → 35 taken 9758 times.
 24701 double nextY = std::abs(d.y()) > 1e-12 ? ((row + (stepY > 0 ? 1 : 0)) * Cell - a.y()) / d.y() : inf;
123
2/2
✓ Branch 42 → 43 taken 21131 times.
✓ Branch 42 → 46 taken 3570 times.
 24701 const double deltaX = std::abs(d.x()) > 1e-12 ? Cell / std::abs(d.x()) : inf;
124
2/2
✓ Branch 49 → 50 taken 21119 times.
✓ Branch 49 → 53 taken 3582 times.
 24701 const double deltaY = std::abs(d.y()) > 1e-12 ? Cell / std::abs(d.y()) : inf;
125 // S106-944: the walk crosses |Δcolumn| + |Δrow| + 1 cells; a fixed cap of
126 // 4096 cut long segments short (their far-end labels got no fade). The
127 // bound stays as a guard against non-finite input.
128 24701 const qint64 cells = qint64(std::abs(qint64(lastColumn) - column)) + std::abs(qint64(lastRow) - row) + 1;
129 24701 const qint64 limit = std::min<qint64>(cells, qint64(1) << 22);
130
1/2
✓ Branch 85 → 58 taken 139694 times.
✗ Branch 85 → 86 not taken.
 139694 for (qint64 guard = 0; guard < limit; ++guard) {
131 139694 const auto cell = m_cells.constFind(keyOf(column, row));
132
2/2
✓ Branch 62 → 63 taken 122683 times.
✓ Branch 62 → 74 taken 17011 times.
 139694 if (cell != m_cells.cend())
133
2/2
✓ Branch 72 → 66 taken 423165 times.
✓ Branch 72 → 73 taken 122683 times.
 545848 for (int i : *cell)
134
2/2
✓ Branch 68 → 69 taken 226560 times.
✓ Branch 68 → 70 taken 196605 times.
 423165 if (!out.contains(i))
135
1/1
✓ Branch 69 → 70 taken 226560 times.
 226560 out.append(i);
136
4/4
✓ Branch 74 → 75 taken 46905 times.
✓ Branch 74 → 77 taken 92789 times.
✓ Branch 75 → 76 taken 24701 times.
✓ Branch 75 → 77 taken 22204 times.
 139694 if (column == lastColumn && row == lastRow)
137 24701 break;
138
2/2
✓ Branch 77 → 78 taken 76080 times.
✓ Branch 77 → 79 taken 38913 times.
 114993 if (nextX < nextY) {
139 76080 column += stepX;
140 76080 nextX += deltaX;
141 } else {
142 38913 row += stepY;
143 38913 nextY += deltaY;
144 }
145
3/4
✓ Branch 80 → 81 taken 9 times.
✓ Branch 80 → 83 taken 114984 times.
✗ Branch 81 → 82 not taken.
✓ Branch 81 → 83 taken 9 times.
 114993 if (nextX > 1 + deltaX && nextY > 1 + deltaY)
146 ✗ break;
147 }
148 }
149
150 3 bool Cutouts::near(QPointF a, QPointF b) const {
151 3 const QRectF reach = QRectF(a, b).normalized().adjusted(-Fade, -Fade, Fade, Fade);
152
5/5
✓ Branch 5 → 6 taken 3 times.
✓ Branch 6 → 7 taken 3 times.
✓ Branch 7 → 8 taken 3 times.
✓ Branch 16 → 9 taken 3 times.
✓ Branch 16 → 17 taken 1 time.
 4 for (int i : candidates(a, b))
153
2/2
✓ Branch 12 → 13 taken 2 times.
✓ Branch 12 → 14 taken 1 time.
 3 if (reach.intersects(m_boxes.at(i)))
154
2/2
✓ Branch 19 → 20 taken 1 time.
✓ Branch 19 → 22 taken 2 times.
 3 return true;
155 1 return false;
156 }
157
158 namespace {
159 // Liang–Barsky: the part [t0, t1] of a→b inside `rect`; false when none.
160 333552 bool clipTo(QPointF a, QPointF b, const QRectF &rect, double *t0, double *t1) {
161 333552 const QPointF d = b - a;
162 333552 *t0 = 0;
163 333552 *t1 = 1;
164 333552 const double p[4] = {-d.x(), d.x(), -d.y(), d.y()};
165 333552 const double q[4] = {a.x() - rect.left(), rect.right() - a.x(), a.y() - rect.top(), rect.bottom() - a.y()};
166
2/2
✓ Branch 31 → 16 taken 1162001 times.
✓ Branch 31 → 32 taken 183297 times.
 1345298 for (int k = 0; k < 4; ++k) {
167
2/2
✓ Branch 17 → 18 taken 249421 times.
✓ Branch 17 → 21 taken 912580 times.
 1162001 if (std::abs(p[k]) < 1e-12) {
168
2/2
✓ Branch 18 → 19 taken 50106 times.
✓ Branch 18 → 20 taken 199315 times.
 249421 if (q[k] < 0)
169 150255 return false;
170 199315 continue;
171 }
172 912580 const double r = q[k] / p[k];
173
2/2
✓ Branch 21 → 22 taken 457760 times.
✓ Branch 21 → 24 taken 454820 times.
 912580 if (p[k] < 0)
174 457760 *t0 = std::max(*t0, r);
175 else
176 454820 *t1 = std::min(*t1, r);
177
2/2
✓ Branch 26 → 27 taken 100149 times.
✓ Branch 26 → 28 taken 812431 times.
 912580 if (*t0 > *t1)
178 100149 return false;
179 }
180 183297 return true;
181 }
182 } // namespace
183
184 ✗ QList<QPair<double, double>> Cutouts::nearParts(QPointF a, QPointF b) const { return nearParts(a, b, candidates(a, b)); }
185
186 700001 double Cutouts::alphaAmong(QPointF point, const QList<int> &boxes) const {
187 700001 double nearest = Fade;
188
2/2
✓ Branch 25 → 4 taken 1215369 times.
✓ Branch 25 → 26 taken 371335 times.
 1586704 for (int i : boxes) {
189 1215369 const QRectF &box = m_boxes.at(i);
190
1/1
✓ Branch 10 → 11 taken 1215369 times.
 1215369 const double dx = std::max({box.left() - point.x(), 0.0, point.x() - box.right()});
191
2/2
✓ Branch 11 → 12 taken 252443 times.
✓ Branch 11 → 13 taken 962926 times.
 1215369 if (dx >= nearest)
192 252443 continue;
193
1/1
✓ Branch 17 → 18 taken 962926 times.
 962926 const double dy = std::max({box.top() - point.y(), 0.0, point.y() - box.bottom()});
194
2/2
✓ Branch 18 → 19 taken 202685 times.
✓ Branch 18 → 20 taken 760241 times.
 962926 if (dy >= nearest)
195 202685 continue;
196 760241 nearest = std::min(nearest, std::hypot(dx, dy));
197
2/2
✓ Branch 21 → 22 taken 328666 times.
✓ Branch 21 → 23 taken 431575 times.
 760241 if (nearest <= Clear)
198 328666 return 0;
199 }
200
1/1
✓ Branch 26 → 27 taken 371335 times.
 371335 return smoothstep(Clear, Fade, nearest);
201 }
202
203 24137 QList<QPair<double, double>> Cutouts::nearParts(QPointF a, QPointF b, const QList<int> &boxes) const {
204 24137 QList<QPair<double, double>> parts;
205
2/2
✓ Branch 24 → 4 taken 226556 times.
✓ Branch 24 → 25 taken 24137 times.
 250693 for (int i : boxes) {
206 226556 const QRectF &box = m_boxes.at(i);
207 226556 double outer0 = 0, outer1 = 0, inner0 = 0, inner1 = 0;
208
3/3
✓ Branch 7 → 8 taken 226556 times.
✓ Branch 8 → 9 taken 119560 times.
✓ Branch 8 → 10 taken 106996 times.
 226556 if (!clipTo(a, b, box.adjusted(-Fade, -Fade, Fade, Fade), &outer0, &outer1))
209 119560 continue;
210 // Within Clear of the box the line is gone: vertices only where it fades.
211
3/3
✓ Branch 11 → 12 taken 106996 times.
✓ Branch 12 → 13 taken 76301 times.
✓ Branch 12 → 18 taken 30695 times.
 106996 if (clipTo(a, b, box.adjusted(-Clear, -Clear, Clear, Clear), &inner0, &inner1)) {
212
1/1
✓ Branch 14 → 15 taken 76301 times.
 76301 parts.append({outer0, inner0});
213
1/1
✓ Branch 16 → 17 taken 76301 times.
 76301 parts.append({inner1, outer1});
214 } else {
215
1/1
✓ Branch 19 → 20 taken 30695 times.
 30695 parts.append({outer0, outer1});
216 }
217 }
218
3/3
✓ Branch 25 → 26 taken 24137 times.
✓ Branch 26 → 27 taken 24137 times.
✓ Branch 27 → 28 taken 24137 times.
 24137 std::sort(parts.begin(), parts.end());
219 24137 QList<QPair<double, double>> merged;
220
2/2
✓ Branch 46 → 31 taken 183297 times.
✓ Branch 46 → 47 taken 24137 times.
 207434 for (const auto &part : std::as_const(parts)) {
221
7/7
✓ Branch 33 → 34 taken 163864 times.
✓ Branch 33 → 37 taken 19433 times.
✓ Branch 34 → 35 taken 163864 times.
✓ Branch 35 → 36 taken 71638 times.
✓ Branch 35 → 37 taken 92226 times.
✓ Branch 38 → 39 taken 71638 times.
✓ Branch 38 → 43 taken 111659 times.
 183297 if (!merged.isEmpty() && part.first <= merged.last().second)
222
2/2
✓ Branch 39 → 40 taken 71638 times.
✓ Branch 41 → 42 taken 71638 times.
 71638 merged.last().second = std::max(merged.last().second, part.second);
223 else
224
1/1
✓ Branch 43 → 44 taken 111659 times.
 111659 merged.append(part);
225 }
226 24137 return merged;
227 24137 }
228
229
2/2
✓ Branch 2 → 3 taken 3 times.
✓ Branch 3 → 4 taken 3 times.
 3 void Mesh::push(QPointF point, const QColor &colour, double alpha) { m_indices.push_back(vertex(point, colour, alpha)); }
230
231 2089875 quint32 Mesh::vertex(QPointF point, const QColor &colour, double alpha) {
232 // The colour's channels are read once per colour, not per vertex.
233
5/6
✓ Branch 3 → 4 taken 2089864 times.
✓ Branch 3 → 5 taken 11 times.
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 2089864 times.
✓ Branch 7 → 8 taken 11 times.
✓ Branch 7 → 14 taken 2089864 times.
 2089875 if (colour.rgba() != m_colourKey || !m_colourValid) {
234 11 m_colourKey = colour.rgba();
235 11 m_colourValid = true;
236 11 m_red = float(colour.redF());
237 11 m_green = float(colour.greenF());
238 11 m_blue = float(colour.blueF());
239 11 m_alpha = float(colour.alphaF());
240 }
241 // S106-946: a NaN alpha (std::clamp keeps NaN, and NaN → unsigned char
242 // is undefined) draws nothing.
243 2089875 const float product = m_alpha * float(alpha);
244
3/3
✓ Branch 15 → 16 taken 3 times.
✓ Branch 15 → 17 taken 2089872 times.
✓ Branch 17 → 18 taken 2089872 times.
 2089875 const float a = (std::isnan(product) ? 0.0f : std::clamp(product, 0.0f, 1.0f)) * 255.0f;
245 2089875 Vertex v;
246 2089875 v.x = float(point.x());
247 2089875 v.y = float(point.y());
248 2089875 v.r = static_cast<unsigned char>(m_red * a + 0.5f);
249 2089875 v.g = static_cast<unsigned char>(m_green * a + 0.5f);
250 2089875 v.b = static_cast<unsigned char>(m_blue * a + 0.5f);
251 2089875 v.a = static_cast<unsigned char>(a + 0.5f);
252
1/1
✓ Branch 21 → 22 taken 2089875 times.
 2089875 m_vertices.push_back(v);
253 4179750 return quint32(m_vertices.size() - 1);
254 }
255
256 7144 void Mesh::stroke(const QList<QPointF> &points, double width, const QList<double> &dash, const QColor &colour,
257 double alpha, const Cutouts *cuts, bool closed) {
258
2/4
✓ Branch 2 → 3 taken 7144 times.
✗ Branch 2 → 4 not taken.
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 7144 times.
 7144 if (alpha <= 0 || width <= 0)
259 4763 return;
260 // The buffers are members, reused from line to line: a frame builds a
261 // thousand lines and their dashes without allocating for each.
262 7144 m_line.clear();
263
2/2
✓ Branch 21 → 8 taken 31844 times.
✓ Branch 21 → 22 taken 7144 times.
 38988 for (const QPointF &point : points)
264
4/6
✓ Branch 10 → 11 taken 24700 times.
✓ Branch 10 → 15 taken 7144 times.
✓ Branch 14 → 15 taken 24700 times.
✗ Branch 14 → 16 not taken.
✓ Branch 17 → 18 taken 31844 times.
✗ Branch 17 → 19 not taken.
 31844 if (m_line.empty() || length(point - m_line.back()) > 0.01)
265
1/1
✓ Branch 18 → 19 taken 31844 times.
 31844 m_line.push_back(point);
266
1/2
✗ Branch 23 → 24 not taken.
✓ Branch 23 → 25 taken 7144 times.
 7144 if (m_line.size() < 2)
267 ✗ return;
268
2/2
✓ Branch 26 → 27 taken 7141 times.
✓ Branch 26 → 53 taken 3 times.
 7144 if (!m_viewport.isEmpty()) {
269 7141 double left = m_line.front().x(), right = left, top = m_line.front().y(), bottom = top;
270
2/2
✓ Branch 44 → 33 taken 31838 times.
✓ Branch 44 → 45 taken 7141 times.
 38979 for (const QPointF &p : m_line) {
271 31838 left = std::min(left, p.x());
272 31838 right = std::max(right, p.x());
273 31838 top = std::min(top, p.y());
274 31838 bottom = std::max(bottom, p.y());
275 }
276
2/2
✓ Branch 50 → 51 taken 1 time.
✓ Branch 50 → 52 taken 7140 times.
 7141 if (!QRectF(QPointF(left, top), QPointF(right, bottom)).adjusted(-width - 2, -width - 2, width + 2, width + 2).intersects(m_viewport))
277 1 return;
278 }
279
1/4
✗ Branch 53 → 54 not taken.
✓ Branch 53 → 57 taken 7143 times.
✗ Branch 55 → 56 not taken.
✗ Branch 55 → 57 not taken.
 7143 const bool solidLoop = closed && dash.isEmpty();
280
1/4
✗ Branch 58 → 59 not taken.
✓ Branch 58 → 62 taken 7143 times.
✗ Branch 59 → 60 not taken.
✗ Branch 59 → 62 not taken.
 7143 if (closed && !solidLoop)
281 ✗ m_line.push_back(m_line.front());
282 // Per point the cut alpha; near a box extra points 3 px apart carry the
283 // fade, each asking only the boxes the segment's cells hold.
284 7143 m_dense.clear();
285 7143 m_denseAlpha.clear();
286
5/6
✓ Branch 64 → 65 taken 7141 times.
✓ Branch 64 → 68 taken 2 times.
✓ Branch 66 → 67 taken 7141 times.
✗ Branch 66 → 68 not taken.
✓ Branch 69 → 70 taken 7141 times.
✓ Branch 69 → 138 taken 2 times.
 7143 if (cuts && !cuts->isEmpty()) {
287 7141 const int count = int(m_line.size());
288
1/2
✗ Branch 71 → 72 not taken.
✓ Branch 71 → 73 taken 7141 times.
 7141 const int last = solidLoop ? count : count - 1;
289
2/2
✓ Branch 134 → 75 taken 24697 times.
✓ Branch 134 → 135 taken 7141 times.
 31838 for (int i = 0; i < last; ++i) {
290 24697 const QPointF a = m_line[i], b = m_line[(i + 1) % count];
291
1/1
✓ Branch 77 → 78 taken 24697 times.
 24697 cuts->candidates(a, b, &m_boxes);
292 // The boxes that matter near a point or a stretch of the segment: a
293 // long segment's cells hold many boxes, a few pixels of it one or two.
294 142923 const auto local = [&](const QRectF &around) {
295 142923 m_local.clear();
296
2/2
✓ Branch 14 → 6 taken 2714583 times.
✓ Branch 14 → 15 taken 142923 times.
 2857506 for (int box : std::as_const(m_boxes))
297
2/2
✓ Branch 10 → 11 taken 230337 times.
✓ Branch 10 → 12 taken 2484246 times.
 2714583 if (around.intersects(cuts->boxes().at(box)))
298
1/1
✓ Branch 11 → 12 taken 230337 times.
 230337 m_local.append(box);
299
2/2
✓ Branch 16 → 17 taken 12637 times.
✓ Branch 16 → 18 taken 130286 times.
 142923 return m_local.isEmpty() ? 1.0 : -1.0;
300 24697 };
301 24697 const double fade = Cutouts::Fade;
302 31264 const auto alphaNear = [&](QPointF p) {
303
4/4
✓ Branch 5 → 6 taken 31264 times.
✓ Branch 6 → 7 taken 12077 times.
✓ Branch 6 → 8 taken 19187 times.
✓ Branch 8 → 9 taken 19187 times.
 31264 return local(QRectF(p.x() - fade, p.y() - fade, 2 * fade, 2 * fade)) > 0 ? 1.0 : cuts->alphaAmong(p, m_local);
304 24697 };
305
2/2
✓ Branch 78 → 79 taken 7141 times.
✓ Branch 78 → 87 taken 17556 times.
 24697 if (i == 0) {
306
1/1
✓ Branch 79 → 80 taken 7141 times.
 7141 m_dense.push_back(a);
307
4/4
✓ Branch 81 → 82 taken 14 times.
✓ Branch 81 → 83 taken 7127 times.
✓ Branch 83 → 84 taken 7127 times.
✓ Branch 85 → 86 taken 7141 times.
 7141 m_denseAlpha.push_back(m_boxes.isEmpty() ? 1.0 : alphaNear(a));
308 }
309
2/2
✓ Branch 88 → 89 taken 24137 times.
✓ Branch 88 → 126 taken 560 times.
 24697 if (!m_boxes.isEmpty()) {
310 24137 const double segment = length(b - a);
311
5/5
✓ Branch 91 → 92 taken 24137 times.
✓ Branch 92 → 93 taken 24137 times.
✓ Branch 93 → 94 taken 24137 times.
✓ Branch 123 → 95 taken 111659 times.
✓ Branch 123 → 124 taken 24137 times.
 135796 for (const auto &[from, to] : cuts->nearParts(a, b, m_boxes)) {
312 111659 const QPointF start = a + (b - a) * from, end = a + (b - a) * to;
313
1/1
✓ Branch 107 → 108 taken 111659 times.
 111659 local(QRectF(start, end).normalized().adjusted(-fade, -fade, fade, fade));
314 111659 const int parts = std::max(1, int(std::ceil((to - from) * segment / 3)));
315
2/2
✓ Branch 120 → 110 taken 724676 times.
✓ Branch 120 → 121 taken 111659 times.
 836335 for (int k = 0; k <= parts; ++k) {
316 724676 const double t = from + (to - from) * k / parts;
317
4/4
✓ Branch 110 → 111 taken 702626 times.
✓ Branch 110 → 119 taken 22050 times.
✓ Branch 111 → 112 taken 680814 times.
✓ Branch 111 → 119 taken 21812 times.
 724676 if (t > 1e-6 && t < 1 - 1e-6) {
318 680814 const QPointF at = a + (b - a) * t;
319
1/1
✓ Branch 115 → 116 taken 680814 times.
 680814 m_dense.push_back(at);
320
2/2
✓ Branch 116 → 117 taken 680814 times.
✓ Branch 117 → 118 taken 680814 times.
 680814 m_denseAlpha.push_back(cuts->alphaAmong(at, m_local));
321 }
322 }
323 24137 }
324 }
325
1/1
✓ Branch 126 → 127 taken 24697 times.
 24697 m_dense.push_back(b);
326
4/4
✓ Branch 128 → 129 taken 560 times.
✓ Branch 128 → 130 taken 24137 times.
✓ Branch 130 → 131 taken 24137 times.
✓ Branch 132 → 133 taken 24697 times.
 24697 m_denseAlpha.push_back(m_boxes.isEmpty() ? 1.0 : alphaNear(b));
327 }
328
1/2
✗ Branch 135 → 136 not taken.
✓ Branch 135 → 142 taken 7141 times.
 7141 if (solidLoop) { // the loop's first point again
329 ✗ m_dense.pop_back();
330 ✗ m_denseAlpha.pop_back();
331 }
332 } else {
333
1/1
✓ Branch 138 → 139 taken 2 times.
 2 m_dense = m_line;
334
1/1
✓ Branch 140 → 141 taken 2 times.
 2 m_denseAlpha.assign(m_line.size(), 1.0);
335 }
336 7143 double total = 0;
337
2/2
✓ Branch 147 → 144 taken 4762 times.
✓ Branch 147 → 148 taken 7143 times.
 11905 for (double d : dash)
338 4762 total += d;
339
6/8
✓ Branch 149 → 150 taken 2381 times.
✓ Branch 149 → 152 taken 4762 times.
✓ Branch 150 → 151 taken 2381 times.
✗ Branch 150 → 152 not taken.
✗ Branch 151 → 152 not taken.
✓ Branch 151 → 153 taken 2381 times.
✓ Branch 154 → 155 taken 4762 times.
✓ Branch 154 → 160 taken 2381 times.
 7143 if (dash.isEmpty() || total <= 0 || solidLoop) {
340
1/1
✓ Branch 158 → 159 taken 4762 times.
 4762 emitStrip(m_dense.data(), m_denseAlpha.data(), int(m_dense.size()), width, colour, alpha, solidLoop);
341 4762 return;
342 }
343 // The dashes (on, off, on, off … px); a dash's ends get the alpha
344 // interpolated there, and reach half the width beyond them, as the
345 // Canvas's round caps did (a 1 px dot of a dotted line is a visible dot).
346 2381 const double cap = std::max(width, 1.0) / 2;
347 101412 const auto flush = [&] {
348
2/2
✓ Branch 3 → 4 taken 101411 times.
✓ Branch 3 → 13 taken 1 time.
 101412 if (m_dash.size() >= 2) {
349 202822 const auto extend = [&](size_t end, size_t inner) {
350 202822 const QPointF d = m_dash[end] - m_dash[inner];
351 202822 const double l = length(d);
352
2/2
✓ Branch 6 → 7 taken 202710 times.
✓ Branch 6 → 12 taken 112 times.
 202822 if (l > 1e-9)
353 202710 m_dash[end] += d / l * cap;
354 304233 };
355 101411 extend(0, 1);
356 101411 extend(m_dash.size() - 1, m_dash.size() - 2);
357
1/1
✓ Branch 11 → 12 taken 101411 times.
 101411 emitStrip(m_dash.data(), m_dashAlpha.data(), int(m_dash.size()), width, colour, alpha, false);
358 }
359 101412 m_dash.clear();
360 101412 m_dashAlpha.clear();
361 101412 };
362 2381 int index = 0;
363 2381 double left = dash.first();
364 2381 m_dash.clear();
365 2381 m_dashAlpha.clear();
366
1/1
✓ Branch 165 → 166 taken 2381 times.
 2381 m_dash.push_back(m_dense.front());
367
1/1
✓ Branch 167 → 168 taken 2381 times.
 2381 m_dashAlpha.push_back(m_denseAlpha.front());
368
2/2
✓ Branch 199 → 169 taken 227928 times.
✓ Branch 199 → 200 taken 2381 times.
 230309 for (size_t i = 1; i < m_dense.size(); ++i) {
369 227928 const QPointF from = m_dense[i - 1], to = m_dense[i];
370 227928 const double whole = length(to - from);
371 227928 double done = 0;
372
2/2
✓ Branch 196 → 174 taken 423574 times.
✓ Branch 196 → 197 taken 227928 times.
 651502 while (whole - done > 0) {
373 423574 const double step = std::min(whole - done, left);
374 423574 done += step;
375
1/2
✓ Branch 175 → 176 taken 423574 times.
✗ Branch 175 → 177 not taken.
 423574 const double t = whole > 0 ? done / whole : 1;
376 423574 const QPointF at = from + (to - from) * t;
377 423574 const double cut = m_denseAlpha[i - 1] + (m_denseAlpha[i] - m_denseAlpha[i - 1]) * t;
378
2/2
✓ Branch 184 → 185 taken 244722 times.
✓ Branch 184 → 187 taken 178852 times.
 423574 if (index % 2 == 0) {
379
1/1
✓ Branch 185 → 186 taken 244722 times.
 244722 m_dash.push_back(at);
380
1/1
✓ Branch 186 → 187 taken 244722 times.
 244722 m_dashAlpha.push_back(cut);
381 }
382 423574 left -= step;
383
2/2
✓ Branch 187 → 188 taken 198944 times.
✓ Branch 187 → 195 taken 224630 times.
 423574 if (left <= 1e-9) {
384
2/2
✓ Branch 188 → 189 taken 99913 times.
✓ Branch 188 → 190 taken 99031 times.
 198944 if (index % 2 == 0) {
385
1/1
✓ Branch 189 → 192 taken 99913 times.
 99913 flush();
386 } else {
387
1/1
✓ Branch 190 → 191 taken 99031 times.
 99031 m_dash.push_back(at);
388
1/1
✓ Branch 191 → 192 taken 99031 times.
 99031 m_dashAlpha.push_back(cut);
389 }
390 198944 index = (index + 1) % int(dash.size());
391 198944 left = dash.at(index);
392 }
393 }
394 }
395
2/2
✓ Branch 200 → 201 taken 1499 times.
✓ Branch 200 → 202 taken 882 times.
 2381 if (index % 2 == 0)
396
1/1
✓ Branch 201 → 202 taken 1499 times.
 1499 flush();
397 }
398
399 // Per segment three quads across the line: feather, core, feather — the
400 // cross-sections at shared points use the mitred normal, so consecutive
401 // segments meet without overlap (no darker joints on faded lines).
402 106173 void Mesh::emitStrip(const QPointF *points, const double *cutAlpha, int n, double width, const QColor &colour, double alpha,
403 bool closed) {
404
1/2
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 106173 times.
 106173 if (n < 2)
405 ✗ return;
406 // Thinner than a pixel: one pixel, fainter.
407 106173 const double half = std::max(width / 2, 0.5);
408
1/2
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 106173 times.
 106173 const double shown = width < 1 ? alpha * width : alpha;
409
1/2
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 106173 times.
 106173 const int segments = closed ? n : n - 1;
410
1/1
✓ Branch 11 → 12 taken 106173 times.
 106173 m_normals.resize(size_t(segments));
411
2/2
✓ Branch 16 → 13 taken 722307 times.
✓ Branch 16 → 17 taken 106173 times.
 828480 for (int i = 0; i < segments; ++i)
412 722307 m_normals[size_t(i)] = normalOf(points[i], points[(i + 1) % n]);
413
1/1
✓ Branch 17 → 18 taken 106173 times.
 106173 m_miters.resize(size_t(n));
414
1/1
✓ Branch 18 → 19 taken 106173 times.
 106173 m_stretch.resize(size_t(n));
415
2/2
✓ Branch 39 → 20 taken 828480 times.
✓ Branch 39 → 40 taken 106173 times.
 934653 for (int i = 0; i < n; ++i) {
416 828480 QPointF before, after;
417
1/2
✗ Branch 20 → 21 not taken.
✓ Branch 20 → 24 taken 828480 times.
 828480 if (closed) {
418 ✗ before = m_normals[size_t((i - 1 + n) % n)];
419 ✗ after = m_normals[size_t(i % n)];
420 } else {
421 828480 before = m_normals[size_t(std::max(0, i - 1))];
422 828480 after = m_normals[size_t(std::min(i, segments - 1))];
423 }
424 828480 QPointF miter = before + after;
425 828480 const double l = length(miter);
426
2/2
✓ Branch 31 → 32 taken 828368 times.
✓ Branch 31 → 33 taken 112 times.
 828480 miter = l > 1e-9 ? miter / l : after;
427 828480 m_miters[size_t(i)] = miter;
428 828480 m_stretch[size_t(i)] = 1 / std::max(0.25, dot(miter, after));
429 }
430 106173 const double offsets[4] = {-(half + 1), -half, half, half + 1};
431 106173 const double edge[4] = {0, 1, 1, 0};
432 // Four vertices per point (feather, core, core, feather), only for points
433 // of segments that are drawn.
434
1/1
✓ Branch 40 → 41 taken 106173 times.
 106173 m_first.assign(size_t(n), -1);
435 855506 const auto crossSection = [&](int i) {
436
2/2
✓ Branch 3 → 4 taken 333038 times.
✓ Branch 3 → 6 taken 522468 times.
 855506 if (m_first[size_t(i)] >= 0)
437 333038 return quint32(m_first[size_t(i)]);
438 522468 quint32 base = 0;
439
2/2
✓ Branch 15 → 7 taken 2089872 times.
✓ Branch 15 → 16 taken 522468 times.
 2612340 for (int k = 0; k < 4; ++k) {
440
1/1
✓ Branch 11 → 12 taken 2089872 times.
 2089872 const quint32 at = vertex(points[i] + m_miters[size_t(i)] * (offsets[k] * m_stretch[size_t(i)]), colour,
441 2089872 shown * edge[k] * cutAlpha[i]);
442
2/2
✓ Branch 12 → 13 taken 522468 times.
✓ Branch 12 → 14 taken 1567404 times.
 2089872 if (k == 0)
443 522468 base = at;
444 }
445 522468 m_first[size_t(i)] = base;
446 522468 return base;
447 106173 };
448
2/2
✓ Branch 65 → 42 taken 722307 times.
✓ Branch 65 → 66 taken 106173 times.
 828480 for (int i = 0; i < segments; ++i) {
449 722307 const int j = (i + 1) % n;
450
4/4
✓ Branch 42 → 43 taken 326153 times.
✓ Branch 42 → 45 taken 396154 times.
✓ Branch 43 → 44 taken 294554 times.
✓ Branch 43 → 45 taken 31599 times.
 722307 if (cutAlpha[i] <= 0 && cutAlpha[j] <= 0)
451 294554 continue;
452 427753 const QPointF a = points[i], b = points[j];
453
2/2
✓ Branch 46 → 47 taken 427742 times.
✓ Branch 46 → 54 taken 11 times.
 427753 if (!m_viewport.isEmpty()) {
454 427742 const QRectF box = QRectF(a, b).normalized().adjusted(-half - 2, -half - 2, half + 2, half + 2);
455
1/2
✗ Branch 51 → 52 not taken.
✓ Branch 51 → 53 taken 427742 times.
 427742 if (!box.intersects(m_viewport))
456 ✗ continue;
457 }
458
2/2
✓ Branch 54 → 55 taken 427753 times.
✓ Branch 55 → 56 taken 427753 times.
 427753 const quint32 from = crossSection(i), to = crossSection(j);
459
2/2
✓ Branch 61 → 57 taken 1283259 times.
✓ Branch 61 → 62 taken 427753 times.
 1711012 for (quint32 k = 0; k < 3; ++k)
460
1/1
✓ Branch 59 → 60 taken 1283259 times.
 1283259 m_indices.insert(m_indices.end(), {from + k, from + k + 1, to + k + 1, from + k, to + k + 1, to + k});
461 }
462 }
463
464 2 void Mesh::fill(const QList<QPointF> &triangles, const QColor &colour, double alpha) {
465
1/2
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 2 times.
 2 if (alpha <= 0)
466 ✗ return;
467
2/2
✓ Branch 27 → 5 taken 2 times.
✓ Branch 27 → 28 taken 2 times.
 4 for (qsizetype i = 0; i + 2 < triangles.size(); i += 3) {
468
9/12
✓ Branch 6 → 7 taken 1 time.
✓ Branch 6 → 15 taken 1 time.
✓ Branch 10 → 11 taken 1 time.
✓ Branch 11 → 12 taken 1 time.
✓ Branch 13 → 14 taken 1 time.
✗ Branch 13 → 15 not taken.
✓ Branch 16 → 17 taken 1 time.
✓ Branch 16 → 18 taken 1 time.
✓ Branch 18 → 19 taken 1 time.
✓ Branch 18 → 20 taken 1 time.
✗ Branch 30 → 31 not taken.
✗ Branch 30 → 32 not taken.
 2 if (!m_viewport.isEmpty() && !boundsOf({triangles.at(i), triangles.at(i + 1), triangles.at(i + 2)}).intersects(m_viewport))
469 1 continue;
470
2/2
✓ Branch 24 → 21 taken 3 times.
✓ Branch 24 → 25 taken 1 time.
 4 for (qsizetype k = 0; k < 3; ++k)
471 3 push(triangles.at(i + k), colour, alpha);
472 }
473 }
474
475 ✗ void Mesh::triangle(QPointF a, QPointF b, QPointF c, const QColor &colour, double alpha, const Cutouts *cuts) {
476 ✗ if (alpha <= 0)
477 ✗ return;
478 // Small: one cut alpha for the whole arrowhead, from its middle.
479 ✗ if (cuts && !cuts->isEmpty())
480 ✗ alpha *= cuts->alphaAt((a + b + c) / 3);
481 ✗ if (alpha <= 0)
482 ✗ return;
483 ✗ push(a, colour, alpha);
484 ✗ push(b, colour, alpha);
485 ✗ push(c, colour, alpha);
486 ✗ const QPointF centre = (a + b + c) / 3;
487 ✗ const QPointF corners[3] = {a, b, c};
488 ✗ for (int k = 0; k < 3; ++k) {
489 ✗ const QPointF p = corners[k], q = corners[(k + 1) % 3];
490 ✗ QPointF out = normalOf(p, q);
491 ✗ if (dot(out, (p + q) / 2 - centre) < 0)
492 ✗ out = -out;
493 ✗ push(p, colour, alpha);
494 ✗ push(q, colour, alpha);
495 ✗ push(q + out, colour, 0);
496 ✗ push(p, colour, alpha);
497 ✗ push(q + out, colour, 0);
498 ✗ push(p + out, colour, 0);
499 }
500 }
501
502 ✗ void Mesh::band(const QList<QPointF> &outer, const QList<QPointF> &inner, const QColor &colour, double outerAlpha,
503 double innerAlpha, bool closed) {
504 ✗ const int n = int(std::min(outer.size(), inner.size()));
505 ✗ if (n < 2)
506 ✗ return;
507 ✗ const int segments = closed ? n : n - 1;
508 ✗ for (int i = 0; i < segments; ++i) {
509 ✗ const int j = (i + 1) % n;
510 ✗ if (!m_viewport.isEmpty() &&
511 ✗ !boundsOf({outer.at(i), outer.at(j), inner.at(i), inner.at(j)}).intersects(m_viewport))
512 ✗ continue;
513 ✗ push(outer.at(i), colour, outerAlpha);
514 ✗ push(outer.at(j), colour, outerAlpha);
515 ✗ push(inner.at(j), colour, innerAlpha);
516 ✗ push(outer.at(i), colour, outerAlpha);
517 ✗ push(inner.at(j), colour, innerAlpha);
518 ✗ push(inner.at(i), colour, innerAlpha);
519 }
520 }
521
522 2771 QList<QPointF> quadratic(QPointF a, QPointF c, QPointF b, double tolerance) {
523 2771 const double bend = length(a - 2 * c + b);
524
1/1
✓ Branch 7 → 8 taken 2771 times.
 2771 const int steps = std::clamp(int(std::ceil(std::sqrt(bend / (4 * std::max(tolerance, 0.05))))), 1, 64);
525 2771 QList<QPointF> out;
526
1/1
✓ Branch 8 → 9 taken 2771 times.
 2771 out.reserve(steps + 1);
527
2/2
✓ Branch 17 → 10 taken 12900 times.
✓ Branch 17 → 18 taken 2771 times.
 15671 for (int i = 0; i <= steps; ++i) {
528 12900 const double t = double(i) / steps, u = 1 - t;
529
1/1
✓ Branch 15 → 16 taken 12900 times.
 12900 out.append(a * (u * u) + c * (2 * u * t) + b * (t * t));
530 }
531 2771 return out;
532 ✗ }
533
534 1195 QList<QPointF> rounded(const QList<QPointF> &points, double radius) {
535
5/6
✓ Branch 3 → 4 taken 941 times.
✓ Branch 3 → 5 taken 254 times.
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 941 times.
✓ Branch 7 → 8 taken 254 times.
✓ Branch 7 → 9 taken 941 times.
 1195 if (points.size() < 3 || radius <= 0)
536 254 return points;
537
1/1
✓ Branch 10 → 11 taken 941 times.
 941 QList<QPointF> out{points.first()};
538
2/2
✓ Branch 48 → 12 taken 1484 times.
✓ Branch 48 → 49 taken 941 times.
 2425 for (int i = 1; i + 1 < points.size(); ++i) {
539 1484 const QPointF a = points.at(i - 1), c = points.at(i), b = points.at(i + 1);
540 1484 const double in = length(c - a), outLength = length(b - c);
541
2/4
✓ Branch 19 → 20 taken 1484 times.
✗ Branch 19 → 21 not taken.
✗ Branch 20 → 21 not taken.
✓ Branch 20 → 23 taken 1484 times.
 1484 if (in < 1e-6 || outLength < 1e-6) {
542 ✗ out.append(c);
543 ✗ continue;
544 }
545 1484 const QPointF toA = (a - c) / in, toB = (b - c) / outLength;
546
1/1
✓ Branch 28 → 29 taken 1484 times.
 1484 const double angle = std::acos(std::clamp(dot(toA, toB), -1.0, 1.0));
547 // A tangent distance as arcTo's for a circle of `radius` in this corner.
548
2/4
✓ Branch 29 → 30 taken 1484 times.
✗ Branch 29 → 32 not taken.
✓ Branch 30 → 31 taken 1484 times.
✗ Branch 30 → 32 not taken.
 1484 const double tangent = angle > 1e-3 && angle < M_PI - 1e-3 ? radius / std::tan(angle / 2) : 0;
549
1/1
✓ Branch 33 → 34 taken 1484 times.
 1484 const double reach = std::min({tangent, in / 2, outLength / 2});
550
1/2
✗ Branch 34 → 35 not taken.
✓ Branch 34 → 37 taken 1484 times.
 1484 if (reach < 0.5) {
551 ✗ out.append(c);
552 ✗ continue;
553 }
554
1/1
✓ Branch 41 → 42 taken 1484 times.
 1484 const QList<QPointF> arc = quadratic(c + toA * reach, c, c + toB * reach, 0.25);
555
1/1
✓ Branch 42 → 43 taken 1484 times.
 1484 out.append(arc);
556 1484 }
557
1/1
✓ Branch 50 → 51 taken 941 times.
 941 out.append(points.last());
558
1/1
✓ Branch 51 → 52 taken 941 times.
 941 return withoutRepeats(out);
559 941 }
560
561 ✗ QList<QPointF> densified(const QList<QPointF> &points, double step, bool closed) {
562 ✗ if (points.size() < 2 || step <= 0)
563 ✗ return points;
564 ✗ QList<QPointF> out{points.first()};
565 ✗ const int segments = closed ? int(points.size()) : int(points.size()) - 1;
566 ✗ for (int i = 0; i < segments; ++i) {
567 ✗ const QPointF a = points.at(i), b = points.at((i + 1) % points.size());
568 ✗ const int parts = std::max(1, int(std::ceil(length(b - a) / step)));
569 ✗ for (int k = 1; k <= parts; ++k)
570 ✗ out.append(a + (b - a) * (double(k) / parts));
571 }
572 ✗ if (closed)
573 ✗ out.removeLast();
574 ✗ return out;
575 ✗ }
576
577 96 QPointF middle(const QList<QPointF> &points, double *total) {
578 96 double sum = 0;
579
2/2
✓ Branch 9 → 3 taken 211 times.
✓ Branch 9 → 10 taken 96 times.
 307 for (int i = 1; i < points.size(); ++i)
580 211 sum += length(points.at(i) - points.at(i - 1));
581
1/2
✓ Branch 10 → 11 taken 96 times.
✗ Branch 10 → 12 not taken.
 96 if (total)
582 96 *total = sum;
583
1/2
✗ Branch 13 → 14 not taken.
✓ Branch 13 → 17 taken 96 times.
 96 if (points.isEmpty())
584 ✗ return {};
585 96 double left = sum / 2;
586
1/2
✓ Branch 33 → 18 taken 153 times.
✗ Branch 33 → 34 not taken.
 153 for (int i = 1; i < points.size(); ++i) {
587 153 const double step = length(points.at(i) - points.at(i - 1));
588
3/4
✓ Branch 22 → 23 taken 96 times.
✓ Branch 22 → 31 taken 57 times.
✓ Branch 23 → 24 taken 96 times.
✗ Branch 23 → 31 not taken.
 153 if (step >= left && step > 0)
589 96 return points.at(i - 1) + (points.at(i) - points.at(i - 1)) * (left / step);
590 57 left -= step;
591 }
592 ✗ return points.first();
593 }
594
595 namespace {
596 2394 void simplifyRange(const QList<QPointF> &points, int first, int last, double tolerance, QList<bool> *keep) {
597
2/2
✓ Branch 2 → 3 taken 81 times.
✓ Branch 2 → 4 taken 2313 times.
 2394 if (last <= first + 1)
598 1230 return;
599 2313 const QLineF chord(points.at(first), points.at(last));
600 2313 double farthest = -1;
601 2313 int index = -1;
602
2/2
✓ Branch 25 → 8 taken 38649 times.
✓ Branch 25 → 26 taken 2313 times.
 40962 for (int i = first + 1; i < last; ++i) {
603 38649 const QPointF p = points.at(i);
604 38649 const QPointF d = chord.p2() - chord.p1();
605 38649 const double l = length(d);
606
1/2
✓ Branch 13 → 14 taken 38649 times.
✗ Branch 13 → 19 not taken.
 38649 const double distance = l > 1e-9 ? std::abs(cross(d, p - chord.p1())) / l : length(p - chord.p1());
607
2/2
✓ Branch 22 → 23 taken 18340 times.
✓ Branch 22 → 24 taken 20309 times.
 38649 if (distance > farthest) {
608 18340 farthest = distance;
609 18340 index = i;
610 }
611 }
612
2/2
✓ Branch 26 → 27 taken 1149 times.
✓ Branch 26 → 28 taken 1164 times.
 2313 if (farthest <= tolerance)
613 1149 return;
614
1/1
✓ Branch 28 → 29 taken 1164 times.
 1164 (*keep)[index] = true;
615
1/1
✓ Branch 29 → 30 taken 1164 times.
 1164 simplifyRange(points, first, index, tolerance, keep);
616
1/1
✓ Branch 30 → 31 taken 1164 times.
 1164 simplifyRange(points, index, last, tolerance, keep);
617 }
618 } // namespace
619
620 33 QList<QPointF> simplified(const QList<QPointF> &loop, double tolerance) {
621 33 const int n = int(loop.size());
622
1/2
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 33 times.
 33 if (n < 5)
623 ✗ return loop;
624 33 int far = 0;
625 33 double best = -1;
626
2/2
✓ Branch 13 → 6 taken 7687 times.
✓ Branch 13 → 14 taken 33 times.
 7720 for (int i = 1; i < n; ++i) {
627 7687 const double d = length(loop.at(i) - loop.first());
628
2/2
✓ Branch 10 → 11 taken 3610 times.
✓ Branch 10 → 12 taken 4077 times.
 7687 if (d > best) {
629 3610 best = d;
630 3610 far = i;
631 }
632 }
633 33 QList<QPointF> ring = loop;
634
1/1
✓ Branch 16 → 17 taken 33 times.
 33 ring.append(loop.first());
635
1/1
✓ Branch 18 → 19 taken 33 times.
 33 QList<bool> keep(ring.size(), false);
636
3/3
✓ Branch 20 → 21 taken 33 times.
✓ Branch 21 → 22 taken 33 times.
✓ Branch 22 → 23 taken 33 times.
 33 keep[0] = keep[far] = keep[ring.size() - 1] = true;
637
1/1
✓ Branch 23 → 24 taken 33 times.
 33 simplifyRange(ring, 0, far, tolerance, &keep);
638
1/1
✓ Branch 25 → 26 taken 33 times.
 33 simplifyRange(ring, far, int(ring.size()) - 1, tolerance, &keep);
639 33 QList<QPointF> out;
640
2/2
✓ Branch 33 → 27 taken 7720 times.
✓ Branch 33 → 34 taken 33 times.
 7753 for (int i = 0; i + 1 < ring.size(); ++i)
641
2/2
✓ Branch 28 → 29 taken 1230 times.
✓ Branch 28 → 31 taken 6490 times.
 7720 if (keep.at(i))
642
1/1
✓ Branch 30 → 31 taken 1230 times.
 1230 out.append(ring.at(i));
643
1/2
✓ Branch 35 → 36 taken 33 times.
✗ Branch 35 → 37 not taken.
 33 return out.size() >= 3 ? out : loop;
644 33 }
645
646 111 double signedArea(const QList<QPointF> &loop) {
647 111 double sum = 0;
648
2/2
✓ Branch 12 → 3 taken 7148 times.
✓ Branch 12 → 13 taken 111 times.
 7259 for (int i = 0; i < loop.size(); ++i) {
649 7148 const QPointF a = loop.at(i), b = loop.at((i + 1) % loop.size());
650 7148 sum += a.x() * b.y() - b.x() * a.y();
651 }
652 111 return sum / 2;
653 }
654
655 14 bool contains(const QList<QPointF> &loop, QPointF point) {
656 14 bool inside = false;
657
2/2
✓ Branch 26 → 4 taken 307 times.
✓ Branch 26 → 27 taken 14 times.
 321 for (int i = 0, j = int(loop.size()) - 1; i < loop.size(); j = i++) {
658 307 const QPointF a = loop.at(i), b = loop.at(j);
659
4/4
✓ Branch 10 → 11 taken 14 times.
✓ Branch 10 → 21 taken 293 times.
✓ Branch 22 → 23 taken 6 times.
✓ Branch 22 → 24 taken 301 times.
 321 if ((a.y() > point.y()) != (b.y() > point.y()) &&
660
2/2
✓ Branch 19 → 20 taken 6 times.
✓ Branch 19 → 21 taken 8 times.
 14 point.x() < (b.x() - a.x()) * (point.y() - a.y()) / (b.y() - a.y()) + a.x())
661 6 inside = !inside;
662 }
663 14 return inside;
664 }
665
666 namespace {
667
668 16 bool segmentsCross(QPointF a, QPointF b, QPointF c, QPointF d) {
669 16 const double d1 = cross(b - a, c - a), d2 = cross(b - a, d - a);
670 16 const double d3 = cross(d - c, a - c), d4 = cross(d - c, b - c);
671
6/10
✓ Branch 14 → 15 taken 4 times.
✓ Branch 14 → 16 taken 12 times.
✓ Branch 15 → 16 taken 4 times.
✗ Branch 15 → 18 not taken.
✓ Branch 16 → 17 taken 4 times.
✓ Branch 16 → 23 taken 12 times.
✗ Branch 17 → 18 not taken.
✓ Branch 17 → 23 taken 4 times.
✗ Branch 18 → 19 not taken.
✗ Branch 18 → 20 not taken.
 16 return ((d1 > 1e-9 && d2 < -1e-9) || (d1 < -1e-9 && d2 > 1e-9)) &&
672
0/6
✗ Branch 19 → 20 not taken.
✗ Branch 19 → 22 not taken.
✗ Branch 20 → 21 not taken.
✗ Branch 20 → 23 not taken.
✗ Branch 21 → 22 not taken.
✗ Branch 21 → 23 not taken.
 16 ((d3 > 1e-9 && d4 < -1e-9) || (d3 < -1e-9 && d4 > 1e-9));
673 }
674
675 198900 bool inTriangle(QPointF p, QPointF a, QPointF b, QPointF c) {
676 198900 const double d1 = cross(b - a, p - a), d2 = cross(c - b, p - b), d3 = cross(a - c, p - c);
677
6/6
✓ Branch 11 → 12 taken 196962 times.
✓ Branch 11 → 15 taken 1938 times.
✓ Branch 12 → 13 taken 183075 times.
✓ Branch 12 → 15 taken 13887 times.
✓ Branch 13 → 14 taken 54 times.
✓ Branch 13 → 15 taken 183021 times.
 198900 return d1 >= -1e-9 && d2 >= -1e-9 && d3 >= -1e-9;
678 }
679
680 // Joins a hole into the outline through its rightmost point and the nearest
681 // outline point that sees it (no edge crossed): one polygon with a slit.
682 2 QList<QPointF> bridged(const QList<QPointF> &outline, const QList<QPointF> &hole, const QList<QList<QPointF>> &others) {
683 2 int m = 0;
684
2/2
✓ Branch 11 → 3 taken 6 times.
✓ Branch 11 → 12 taken 2 times.
 8 for (int i = 1; i < hole.size(); ++i)
685
2/2
✓ Branch 7 → 8 taken 2 times.
✓ Branch 7 → 9 taken 4 times.
 6 if (hole.at(i).x() > hole.at(m).x())
686 2 m = i;
687 2 const QPointF from = hole.at(m);
688 2 QList<int> order;
689
2/2
✓ Branch 17 → 14 taken 8 times.
✓ Branch 17 → 18 taken 2 times.
 10 for (int i = 0; i < outline.size(); ++i)
690
1/1
✓ Branch 14 → 15 taken 8 times.
 8 order.append(i);
691
3/3
✓ Branch 18 → 19 taken 2 times.
✓ Branch 19 → 20 taken 2 times.
✓ Branch 20 → 21 taken 2 times.
 2 std::sort(order.begin(), order.end(),
692 10 [&](int a, int b) { return length(outline.at(a) - from) < length(outline.at(b) - from); });
693 2 const auto visible = [&](QPointF to) {
694 4 const auto crossesLoop = [&](const QList<QPointF> &loop) {
695
2/2
✓ Branch 11 → 3 taken 16 times.
✓ Branch 11 → 12 taken 4 times.
 20 for (int i = 0; i < loop.size(); ++i)
696
1/2
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 16 times.
 16 if (segmentsCross(from, to, loop.at(i), loop.at((i + 1) % loop.size())))
697 ✗ return true;
698 4 return false;
699 2 };
700
3/6
✓ Branch 3 → 4 taken 2 times.
✗ Branch 3 → 6 not taken.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 2 times.
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 2 times.
 2 if (crossesLoop(outline) || crossesLoop(hole))
701 ✗ return false;
702
1/2
✗ Branch 18 → 12 not taken.
✓ Branch 18 → 19 taken 2 times.
 2 for (const QList<QPointF> &other : others)
703 ✗ if (crossesLoop(other))
704 ✗ return false;
705 2 return true;
706 2 };
707
2/3
✗ Branch 22 → 23 not taken.
✓ Branch 22 → 24 taken 2 times.
✓ Branch 24 → 25 taken 2 times.
 2 int p = order.isEmpty() ? 0 : order.first();
708
1/2
✓ Branch 36 → 29 taken 2 times.
✗ Branch 36 → 37 not taken.
 2 for (int candidate : std::as_const(order))
709
2/3
✓ Branch 31 → 32 taken 2 times.
✓ Branch 32 → 33 taken 2 times.
✗ Branch 32 → 34 not taken.
 2 if (visible(outline.at(candidate))) {
710 2 p = candidate;
711 2 break;
712 }
713 2 QList<QPointF> out;
714
1/1
✓ Branch 39 → 40 taken 2 times.
 2 out.reserve(outline.size() + hole.size() + 2);
715
2/2
✓ Branch 44 → 41 taken 6 times.
✓ Branch 44 → 45 taken 2 times.
 8 for (int i = 0; i <= p; ++i)
716
1/1
✓ Branch 42 → 43 taken 6 times.
 6 out.append(outline.at(i));
717
2/2
✓ Branch 51 → 46 taken 8 times.
✓ Branch 51 → 52 taken 2 times.
 10 for (int k = 0; k < hole.size(); ++k)
718
1/1
✓ Branch 48 → 49 taken 8 times.
 8 out.append(hole.at((m + k) % hole.size()));
719
1/1
✓ Branch 53 → 54 taken 2 times.
 2 out.append(hole.at(m));
720
2/2
✓ Branch 59 → 55 taken 4 times.
✓ Branch 59 → 60 taken 2 times.
 6 for (int i = p; i < outline.size(); ++i)
721
1/1
✓ Branch 56 → 57 taken 4 times.
 4 out.append(outline.at(i));
722 2 return out;
723 2 }
724
725 39 void earClip(const QList<QPointF> &polygon, QList<QPointF> *triangles) {
726 39 QList<int> ring;
727
2/2
✓ Branch 6 → 3 taken 3520 times.
✓ Branch 6 → 7 taken 39 times.
 3559 for (int i = 0; i < polygon.size(); ++i)
728
1/1
✓ Branch 3 → 4 taken 3520 times.
 3520 ring.append(i);
729 39 int i = 0;
730 39 int sinceEar = 0;
731
2/2
✓ Branch 58 → 8 taken 3708 times.
✓ Branch 58 → 59 taken 39 times.
 3747 while (ring.size() > 3) {
732 3708 const int n = int(ring.size());
733
1/2
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 3708 times.
 3708 if (sinceEar > n)
734 ✗ break; // a whole round without an ear (rounding at a bridge): the rest stays empty
735 3708 i %= n;
736 3708 const int prev = ring.at((i - 1 + n) % n), cur = ring.at(i), next = ring.at((i + 1) % n);
737 3708 const QPointF a = polygon.at(prev), b = polygon.at(cur), c = polygon.at(next);
738 3708 const double turn = cross(b - a, c - b);
739
1/2
✗ Branch 21 → 22 not taken.
✓ Branch 21 → 24 taken 3708 times.
 3708 if (std::abs(turn) <= 1e-9) {
740 ✗ ring.removeAt(i); // collinear: drops out without a triangle
741 ✗ sinceEar = 0;
742 ✗ continue;
743 }
744 3708 bool ear = turn > 0;
745
4/4
✓ Branch 47 → 48 taken 209490 times.
✓ Branch 47 → 49 taken 3403 times.
✓ Branch 48 → 25 taken 209185 times.
✓ Branch 48 → 49 taken 305 times.
 212893 for (int k = 0; k < n && ear; ++k) {
746 209185 const int index = ring.at(k);
747
6/6
✓ Branch 26 → 27 taken 205780 times.
✓ Branch 26 → 29 taken 3405 times.
✓ Branch 27 → 28 taken 202349 times.
✓ Branch 27 → 29 taken 3431 times.
✓ Branch 28 → 29 taken 3443 times.
✓ Branch 28 → 30 taken 198906 times.
 209185 if (index == prev || index == cur || index == next)
748 10285 continue;
749 198906 const QPointF p = polygon.at(index);
750
7/8
✓ Branch 32 → 33 taken 198906 times.
✗ Branch 32 → 37 not taken.
✓ Branch 34 → 35 taken 198902 times.
✓ Branch 34 → 37 taken 4 times.
✓ Branch 36 → 37 taken 2 times.
✓ Branch 36 → 38 taken 198900 times.
✓ Branch 39 → 40 taken 6 times.
✓ Branch 39 → 41 taken 198900 times.
 198906 if (p == a || p == b || p == c)
751 6 continue; // the two ends of a bridge
752
2/2
✓ Branch 42 → 43 taken 54 times.
✓ Branch 42 → 44 taken 198846 times.
 198900 if (inTriangle(p, a, b, c))
753 54 ear = false;
754 }
755
2/2
✓ Branch 49 → 50 taken 3403 times.
✓ Branch 49 → 55 taken 305 times.
 3708 if (ear) {
756
2/2
✓ Branch 50 → 51 taken 3403 times.
✓ Branch 51 → 52 taken 3403 times.
 3403 triangles->append({a, b, c});
757
1/1
✓ Branch 53 → 54 taken 3403 times.
 3403 ring.removeAt(i);
758 3403 sinceEar = 0;
759 } else {
760 305 ++i;
761 305 ++sinceEar;
762 }
763 }
764
1/2
✓ Branch 60 → 61 taken 39 times.
✗ Branch 60 → 71 not taken.
 39 if (ring.size() == 3)
765
2/2
✓ Branch 67 → 68 taken 39 times.
✓ Branch 68 → 69 taken 39 times.
 39 triangles->append({polygon.at(ring.at(0)), polygon.at(ring.at(1)), polygon.at(ring.at(2))});
766 39 }
767
768 } // namespace
769
770 36 QList<QPointF> triangulate(const QList<QList<QPointF>> &loops) {
771 36 QList<QList<QPointF>> clean;
772
2/2
✓ Branch 29 → 4 taken 41 times.
✓ Branch 29 → 30 taken 36 times.
 77 for (const QList<QPointF> &loop : loops) {
773
1/1
✓ Branch 5 → 6 taken 41 times.
 41 QList<QPointF> points = withoutRepeats(loop);
774
5/8
✓ Branch 7 → 8 taken 41 times.
✗ Branch 7 → 14 not taken.
✓ Branch 8 → 9 taken 41 times.
✓ Branch 9 → 10 taken 41 times.
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 14 taken 41 times.
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 41 times.
 41 if (points.size() >= 2 && length(points.first() - points.last()) <= 0.01)
775 ✗ points.removeLast();
776
3/6
✓ Branch 18 → 19 taken 41 times.
✗ Branch 18 → 23 not taken.
✓ Branch 21 → 22 taken 41 times.
✗ Branch 21 → 23 not taken.
✓ Branch 24 → 25 taken 41 times.
✗ Branch 24 → 26 not taken.
 41 if (points.size() >= 3 && std::abs(signedArea(points)) > 1e-6)
777
1/1
✓ Branch 25 → 26 taken 41 times.
 41 clean.append(points);
778 41 }
779 // Depth: how many other loops enclose a loop. Even depth bounds the
780 // region (an outline), odd depth is a hole of the outline around it.
781 36 QList<int> depth;
782
2/2
✓ Branch 48 → 31 taken 41 times.
✓ Branch 48 → 49 taken 36 times.
 77 for (int i = 0; i < clean.size(); ++i) {
783 41 int d = 0;
784
2/2
✓ Branch 44 → 32 taken 53 times.
✓ Branch 44 → 45 taken 41 times.
 94 for (int j = 0; j < clean.size(); ++j)
785
6/6
✓ Branch 32 → 33 taken 12 times.
✓ Branch 32 → 39 taken 41 times.
✓ Branch 37 → 38 taken 4 times.
✓ Branch 37 → 39 taken 8 times.
✓ Branch 40 → 41 taken 4 times.
✓ Branch 40 → 42 taken 49 times.
 53 if (j != i && contains(clean.at(j), clean.at(i).first()))
786 4 ++d;
787
1/1
✓ Branch 45 → 46 taken 41 times.
 41 depth.append(d);
788 }
789 36 QList<QPointF> triangles;
790
2/2
✓ Branch 104 → 50 taken 41 times.
✓ Branch 104 → 105 taken 36 times.
 77 for (int i = 0; i < clean.size(); ++i) {
791
2/2
✓ Branch 51 → 52 taken 2 times.
✓ Branch 51 → 53 taken 39 times.
 41 if (depth.at(i) % 2 != 0)
792 2 continue;
793 39 QList<QPointF> outline = clean.at(i);
794
2/2
✓ Branch 56 → 57 taken 32 times.
✓ Branch 56 → 60 taken 7 times.
 39 if (signedArea(outline) < 0)
795
3/3
✓ Branch 57 → 58 taken 32 times.
✓ Branch 58 → 59 taken 32 times.
✓ Branch 59 → 60 taken 32 times.
 32 std::reverse(outline.begin(), outline.end());
796 39 QList<QList<QPointF>> holes;
797
2/2
✓ Branch 84 → 61 taken 48 times.
✓ Branch 84 → 85 taken 39 times.
 87 for (int j = 0; j < clean.size(); ++j)
798
5/6
✓ Branch 63 → 64 taken 2 times.
✓ Branch 63 → 70 taken 46 times.
✓ Branch 68 → 69 taken 2 times.
✗ Branch 68 → 70 not taken.
✓ Branch 71 → 72 taken 2 times.
✓ Branch 71 → 82 taken 46 times.
 48 if (depth.at(j) == depth.at(i) + 1 && contains(clean.at(i), clean.at(j).first())) {
799 2 QList<QPointF> hole = clean.at(j);
800
1/2
✓ Branch 75 → 76 taken 2 times.
✗ Branch 75 → 79 not taken.
 2 if (signedArea(hole) > 0)
801
3/3
✓ Branch 76 → 77 taken 2 times.
✓ Branch 77 → 78 taken 2 times.
✓ Branch 78 → 79 taken 2 times.
 2 std::reverse(hole.begin(), hole.end());
802
1/1
✓ Branch 79 → 80 taken 2 times.
 2 holes.append(hole);
803 2 }
804 // Rightmost holes first, so a later bridge never crosses an earlier one.
805
3/3
✓ Branch 85 → 86 taken 39 times.
✓ Branch 86 → 87 taken 39 times.
✓ Branch 87 → 88 taken 39 times.
 39 std::sort(holes.begin(), holes.end(), [](const QList<QPointF> &a, const QList<QPointF> &b) {
806 ✗ return boundsOf(a).right() > boundsOf(b).right();
807 });
808
2/2
✓ Branch 97 → 89 taken 2 times.
✓ Branch 97 → 98 taken 39 times.
 41 for (int h = 0; h < holes.size(); ++h)
809
2/2
✓ Branch 89 → 90 taken 2 times.
✓ Branch 91 → 92 taken 2 times.
 2 outline = bridged(outline, holes.at(h), holes.mid(h + 1));
810
1/1
✓ Branch 98 → 99 taken 39 times.
 39 earClip(outline, &triangles);
811 39 }
812 36 return triangles;
813 36 }
814
815 } // namespace GraphGeometry
816