GCC Code Coverage Report

Directory: ./
File: tasks/peryashkin_v_binary_component_contour_processing/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 73 75 97.3%
Functions: 10 10 100.0%
Branches: 70 166 42.2%
Line Branch Exec Source
1 #include "peryashkin_v_binary_component_contour_processing/omp/include/ops_omp.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <queue>
7 #include <utility>
8 #include <vector>
9
10 #include "peryashkin_v_binary_component_contour_processing/common/include/common.hpp"
11
12 namespace peryashkin_v_binary_component_contour_processing {
13
14 namespace {
15
16 inline bool InBounds(int x, int y, int w, int h) {
17 1484 return (x >= 0) && (y >= 0) && (x < w) && (y < h);
18 }
19
20 inline std::int64_t Cross(const Point &o, const Point &a, const Point &b) {
21 360 const std::int64_t x1 = static_cast<std::int64_t>(a.x) - static_cast<std::int64_t>(o.x);
22 360 const std::int64_t y1 = static_cast<std::int64_t>(a.y) - static_cast<std::int64_t>(o.y);
23 360 const std::int64_t x2 = static_cast<std::int64_t>(b.x) - static_cast<std::int64_t>(o.x);
24 360 const std::int64_t y2 = static_cast<std::int64_t>(b.y) - static_cast<std::int64_t>(o.y);
25 360 return (x1 * y2) - (y1 * x2);
26 }
27
28
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 inline std::vector<Point> ConvexHullMonotonicChain(std::vector<Point> pts) {
29
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 if (pts.empty()) {
30 ✗ return {};
31 }
32
33
9/78
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 54 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 58 not taken.
✗ Branch 59 not taken.
✗ Branch 60 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✓ Branch 67 taken 160 times.
✓ Branch 68 taken 44 times.
✓ Branch 69 taken 116 times.
✗ Branch 70 not taken.
✓ Branch 71 taken 44 times.
✓ Branch 72 taken 144 times.
✓ Branch 73 taken 160 times.
✓ Branch 74 taken 108 times.
✓ Branch 75 taken 52 times.
✗ Branch 76 not taken.
✓ Branch 77 taken 108 times.
 464 std::ranges::sort(pts, [](const Point &a, const Point &b) { return (a.x < b.x) || ((a.x == b.x) && (a.y < b.y)); });
34
35 const auto new_end =
36
3/8
✓ Branch 0 taken 108 times.
✓ Branch 1 taken 52 times.
✓ Branch 2 taken 108 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 160 std::ranges::unique(pts, [](const Point &a, const Point &b) { return (a.x == b.x) && (a.y == b.y); }).begin();
37 pts.erase(new_end, pts.end());
38
39
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 24 times.
 28 if (pts.size() == 1) {
40 return pts;
41 }
42
43
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<Point> lower;
44
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 lower.reserve(pts.size());
45
2/2
✓ Branch 0 taken 184 times.
✓ Branch 1 taken 24 times.
 208 for (const auto &p : pts) {
46
4/4
✓ Branch 0 taken 180 times.
✓ Branch 1 taken 120 times.
✓ Branch 2 taken 116 times.
✓ Branch 3 taken 64 times.
 300 while ((lower.size() >= 2) && (Cross(lower[lower.size() - 2], lower[lower.size() - 1], p) <= 0)) {
47 lower.pop_back();
48 }
49 lower.push_back(p);
50 }
51
52
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<Point> upper;
53
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 upper.reserve(pts.size());
54
2/2
✓ Branch 0 taken 184 times.
✓ Branch 1 taken 24 times.
 208 for (std::size_t i = pts.size(); i-- > 0;) {
55 const auto &p = pts[i];
56
4/4
✓ Branch 0 taken 180 times.
✓ Branch 1 taken 120 times.
✓ Branch 2 taken 64 times.
✓ Branch 3 taken 116 times.
 300 while ((upper.size() >= 2) && (Cross(upper[upper.size() - 2], upper[upper.size() - 1], p) <= 0)) {
57 upper.pop_back();
58 }
59 upper.push_back(p);
60 }
61
62 lower.pop_back();
63 upper.pop_back();
64
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 lower.insert(lower.end(), upper.begin(), upper.end());
65 return lower;
66 }
67
68 inline std::size_t Index2D(int x, int y, int w) {
69
5/6
✓ Branch 0 taken 188 times.
✓ Branch 1 taken 764 times.
✓ Branch 3 taken 28 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 400 times.
✓ Branch 6 taken 312 times.
 1692 return (static_cast<std::size_t>(y) * static_cast<std::size_t>(w)) + static_cast<std::size_t>(x);
70 }
71
72
2/2
✓ Branch 0 taken 732 times.
✓ Branch 1 taken 20 times.
 752 inline void TryPushNeighbor(const BinaryImage &img, std::vector<std::uint8_t> &vis, std::queue<Point> &q, int w, int h,
73 int nx, int ny) {
74
2/2
✓ Branch 0 taken 712 times.
✓ Branch 1 taken 20 times.
 732 if (!InBounds(nx, ny, w, h)) {
75 return;
76 }
77 const std::size_t nid = Index2D(nx, ny, w);
78
4/4
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 312 times.
✓ Branch 2 taken 160 times.
✓ Branch 3 taken 240 times.
 712 if ((img.data[nid] == 1) && (vis[nid] == 0U)) {
79 160 vis[nid] = 1U;
80 160 q.push(Point{.x = nx, .y = ny});
81 }
82 }
83
84 28 inline std::vector<Point> BfsComponent4(const BinaryImage &img, std::vector<std::uint8_t> &vis, int w, int h, int sx,
85 int sy) {
86 std::queue<Point> q;
87 const std::size_t start_id = Index2D(sx, sy, w);
88 28 vis[start_id] = 1U;
89
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 q.push(Point{.x = sx, .y = sy});
90
91 28 std::vector<Point> pts;
92
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 pts.reserve(128);
93
94
2/2
✓ Branch 0 taken 188 times.
✓ Branch 1 taken 28 times.
 216 while (!q.empty()) {
95 188 const Point p = q.front();
96 q.pop();
97 pts.push_back(p);
98
99
1/2
✓ Branch 1 taken 188 times.
✗ Branch 2 not taken.
 188 TryPushNeighbor(img, vis, q, w, h, p.x + 1, p.y);
100
1/2
✓ Branch 1 taken 188 times.
✗ Branch 2 not taken.
 188 TryPushNeighbor(img, vis, q, w, h, p.x - 1, p.y);
101
1/2
✓ Branch 1 taken 188 times.
✗ Branch 2 not taken.
 188 TryPushNeighbor(img, vis, q, w, h, p.x, p.y + 1);
102
1/2
✓ Branch 1 taken 188 times.
✗ Branch 2 not taken.
 188 TryPushNeighbor(img, vis, q, w, h, p.x, p.y - 1);
103 }
104
105 28 return pts;
106 }
107
108 28 inline std::vector<std::vector<Point>> ExtractComponents4(const BinaryImage &img) {
109 28 const int w = img.width;
110 28 const int h = img.height;
111 28 const std::size_t n = static_cast<std::size_t>(w) * static_cast<std::size_t>(h);
112
113 28 std::vector<std::uint8_t> vis(n, 0U);
114 28 std::vector<std::vector<Point>> comps;
115
116
2/2
✓ Branch 0 taken 152 times.
✓ Branch 1 taken 28 times.
 180 for (int yy = 0; yy < h; ++yy) {
117
2/2
✓ Branch 0 taken 952 times.
✓ Branch 1 taken 152 times.
 1104 for (int xx = 0; xx < w; ++xx) {
118 const std::size_t id = Index2D(xx, yy, w);
119
4/4
✓ Branch 0 taken 188 times.
✓ Branch 1 taken 764 times.
✓ Branch 2 taken 160 times.
✓ Branch 3 taken 28 times.
 952 if ((img.data[id] == 0) || (vis[id] != 0U)) {
120 924 continue;
121 }
122
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 56 comps.push_back(BfsComponent4(img, vis, w, h, xx, yy));
123 }
124 }
125
126 28 return comps;
127 ✗ }
128
129 28 inline OutType SolveOMP(const BinaryImage &img) {
130 28 auto comps = ExtractComponents4(img);
131
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 OutType hulls;
132
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 hulls.resize(comps.size());
133
134 28 const int n = static_cast<int>(comps.size());
135
136 28 #pragma omp parallel for default(none) shared(comps, hulls, n) schedule(static)
137 for (int i = 0; i < n; ++i) {
138 const auto idx = static_cast<std::size_t>(i);
139 hulls[idx] = ConvexHullMonotonicChain(std::move(comps[idx]));
140 }
141
142 28 return hulls;
143 28 }
144
145 } // namespace
146
147
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 PeryashkinVBinaryComponentContourProcessingOMP::PeryashkinVBinaryComponentContourProcessingOMP(const InType &in) {
148 SetTypeOfTask(GetStaticTypeOfTask());
149 GetInput() = in;
150 GetOutput().clear();
151 28 }
152
153 56 bool PeryashkinVBinaryComponentContourProcessingOMP::ValidationImpl() {
154 const auto &in = GetInput();
155
2/4
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 56 times.
✗ Branch 3 not taken.
 56 if ((in.width <= 0) || (in.height <= 0)) {
156 return false;
157 }
158 56 const std::size_t need = static_cast<std::size_t>(in.width) * static_cast<std::size_t>(in.height);
159 56 return in.data.size() == need;
160 }
161
162
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 bool PeryashkinVBinaryComponentContourProcessingOMP::PreProcessingImpl() {
163 local_out_.clear();
164 28 return true;
165 }
166
167 28 bool PeryashkinVBinaryComponentContourProcessingOMP::RunImpl() {
168
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 if (!ValidationImpl()) {
169 return false;
170 }
171 28 local_out_ = SolveOMP(GetInput());
172 28 return true;
173 }
174
175 28 bool PeryashkinVBinaryComponentContourProcessingOMP::PostProcessingImpl() {
176 28 GetOutput() = local_out_;
177 28 return true;
178 }
179
180 } // namespace peryashkin_v_binary_component_contour_processing
181