GCC Code Coverage Report

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