GCC Code Coverage Report

Directory: ./
File: tasks/kamalagin_a_binary_image_convex_hull/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 89 89 100.0%
Functions: 14 14 100.0%
Branches: 74 102 72.5%
Line Branch Exec Source
1 #include "kamalagin_a_binary_image_convex_hull/tbb/include/ops_tbb.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <utility>
8 #include <vector>
9
10 #include "kamalagin_a_binary_image_convex_hull/common/include/common.hpp"
11 #include "oneapi/tbb/blocked_range.h"
12 #include "oneapi/tbb/parallel_for.h"
13
14 namespace kamalagin_a_binary_image_convex_hull {
15
16 namespace {
17
18 constexpr std::array<std::pair<int, int>, 4> kFourNeighbors = {{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}};
19
20 int64_t Cross(const Point &o, const Point &a, const Point &b) {
21 132 return (static_cast<int64_t>(a.x - o.x) * (b.y - o.y)) - (static_cast<int64_t>(a.y - o.y) * (b.x - o.x));
22 }
23
24 int64_t DistSq(const Point &a, const Point &b) {
25 56 const int dx = a.x - b.x;
26 56 const int dy = a.y - b.y;
27 56 return (static_cast<int64_t>(dx) * dx) + (static_cast<int64_t>(dy) * dy);
28 }
29
30 12 size_t GrahamFindPivot(std::vector<Point> &pts) {
31 size_t pivot = 0;
32 const size_t n = pts.size();
33
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 12 times.
 64 for (size_t i = 1; i < n; ++i) {
34
4/6
✓ Branch 0 taken 52 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 28 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 24 times.
 52 if (pts[i].y < pts[pivot].y || (pts[i].y == pts[pivot].y && pts[i].x < pts[pivot].x)) {
35 pivot = i;
36 }
37 }
38 12 return pivot;
39 }
40
41 12 void GrahamCollinearReduce(std::vector<Point> &pts) {
42 size_t m = 1;
43 const size_t n = pts.size();
44
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 12 times.
 52 for (size_t i = 2; i < n; ++i) {
45
4/4
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 28 times.
✓ Branch 2 taken 32 times.
✓ Branch 3 taken 12 times.
 72 while (m > 0 && Cross(pts[m - 1], pts[m], pts[i]) == 0) {
46 --m;
47 }
48 40 ++m;
49 40 pts[m] = pts[i];
50 }
51 12 pts.resize(m + 1);
52 12 }
53
54
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 void GrahamScan(std::vector<Point> &pts, Hull &out) {
55 out.push_back(pts[0]);
56
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
 12 if (pts.size() <= 2) {
57
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 if (pts.size() == 2) {
58 out.push_back(pts[1]);
59 }
60 8 return;
61 }
62 out.push_back(pts[1]);
63
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
 12 for (size_t i = 2; i < pts.size(); ++i) {
64
2/4
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 8 times.
 8 while (out.size() >= 2 && Cross(out[out.size() - 2], out.back(), pts[i]) <= 0) {
65 out.pop_back();
66 }
67 out.push_back(pts[i]);
68 }
69 }
70
71
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 void GrahamHull(std::vector<Point> &pts, Hull &out) {
72 out.clear();
73 const size_t n = pts.size();
74
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 12 times.
 32 if (n <= 1) {
75
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (n == 1) {
76 out.push_back(pts[0]);
77 }
78 20 return;
79 }
80 12 const size_t pivot = GrahamFindPivot(pts);
81 std::swap(pts[0], pts[pivot]);
82 const Point &p0 = pts[0];
83 92 std::sort(pts.begin() + 1, pts.end(), [&p0](const Point &a, const Point &b) {
84 80 const int64_t c = Cross(p0, a, b);
85
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 56 times.
 80 if (c != 0) {
86 24 return c > 0;
87 }
88 56 return DistSq(p0, a) < DistSq(p0, b);
89 });
90 12 GrahamCollinearReduce(pts);
91 12 GrahamScan(pts, out);
92 }
93
94 32 void FloodFillComponent(const BinaryImage &img, int start_row, int start_col, std::vector<int> &label,
95 std::vector<Point> &component_pts) {
96 32 const int rows = img.rows;
97
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 const int cols = img.cols;
98 component_pts.clear();
99 32 std::vector<std::pair<int, int>> stack;
100
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 stack.emplace_back(start_row, start_col);
101 32 const size_t start_idx = img.Index(start_row, start_col);
102 32 label[start_idx] = 1;
103
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 32 times.
 116 while (!stack.empty()) {
104 const auto [cur_r, cur_c] = stack.back();
105 stack.pop_back();
106
1/4
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 84 component_pts.push_back(Point{.x = cur_c, .y = cur_r});
107
2/2
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 84 times.
 420 for (const auto &[dr, dc] : kFourNeighbors) {
108 336 const int nr = cur_r + dr;
109 336 const int nc = cur_c + dc;
110
8/8
✓ Branch 0 taken 284 times.
✓ Branch 1 taken 52 times.
✓ Branch 2 taken 232 times.
✓ Branch 3 taken 52 times.
✓ Branch 4 taken 188 times.
✓ Branch 5 taken 44 times.
✓ Branch 6 taken 44 times.
✓ Branch 7 taken 144 times.
 336 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
111 192 continue;
112 }
113
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 24 times.
 144 const size_t nidx = (static_cast<size_t>(nr) * static_cast<size_t>(cols)) + static_cast<size_t>(nc);
114
4/4
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 52 times.
✓ Branch 3 taken 68 times.
 144 if (img.data[nidx] != 0 && label[nidx] == 0) {
115 52 label[nidx] = 1;
116
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 stack.emplace_back(nr, nc);
117 }
118 }
119 }
120 32 }
121
122
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 void CollectComponents(const BinaryImage &img, std::vector<std::vector<Point>> &components) {
123 components.clear();
124 28 const int rows = img.rows;
125 28 const int cols = img.cols;
126 28 const size_t total = static_cast<size_t>(rows) * static_cast<size_t>(cols);
127 28 std::vector<int> label(total, 0);
128
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 28 times.
 80 for (int row = 0; row < rows; ++row) {
129
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 52 times.
 176 for (int col = 0; col < cols; ++col) {
130 const size_t idx = img.Index(row, col);
131
4/4
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 40 times.
✓ Branch 2 taken 52 times.
✓ Branch 3 taken 32 times.
 124 if (img.data[idx] == 0 || label[idx] != 0) {
132 92 continue;
133 }
134
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 components.emplace_back();
135
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 FloodFillComponent(img, row, col, label, components.back());
136 }
137 }
138 28 }
139
140
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 void RunBinaryImageConvexHullTbb(const BinaryImage &img, HullList &hulls) {
141 hulls.clear();
142 28 std::vector<std::vector<Point>> components;
143
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 CollectComponents(img, components);
144 const size_t count = components.size();
145
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 hulls.resize(count);
146
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 60 tbb::parallel_for(tbb::blocked_range<size_t>(0, count), [&](const tbb::blocked_range<size_t> &range) {
147
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
 64 for (size_t i = range.begin(); i != range.end(); ++i) {
148 32 GrahamHull(components[i], hulls[i]);
149 }
150 32 });
151 28 }
152
153 } // namespace
154
155
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 KamalaginABinaryImageConvexHullTBB::KamalaginABinaryImageConvexHullTBB(const InType &in) {
156 SetTypeOfTask(GetStaticTypeOfTask());
157 GetInput() = in;
158 28 GetOutput() = HullList{};
159 28 }
160
161 28 bool KamalaginABinaryImageConvexHullTBB::ValidationImpl() {
162 const auto &img = GetInput();
163
2/4
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 28 times.
✗ Branch 3 not taken.
 28 if (img.rows < 0 || img.cols < 0) {
164 return false;
165 }
166
3/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 24 times.
 28 if (img.rows == 0 || img.cols == 0) {
167 4 return img.data.empty();
168 }
169
2/4
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 if (img.rows > 8192 || img.cols > 8192) {
170 return false;
171 }
172 24 return (static_cast<size_t>(img.rows) * static_cast<size_t>(img.cols)) == img.data.size();
173 }
174
175
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 bool KamalaginABinaryImageConvexHullTBB::PreProcessingImpl() {
176 GetOutput().clear();
177 28 return true;
178 }
179
180 28 bool KamalaginABinaryImageConvexHullTBB::RunImpl() {
181 28 RunBinaryImageConvexHullTbb(GetInput(), GetOutput());
182 28 return true;
183 }
184
185 28 bool KamalaginABinaryImageConvexHullTBB::PostProcessingImpl() {
186 28 return true;
187 }
188
189 } // namespace kamalagin_a_binary_image_convex_hull
190