GCC Code Coverage Report

Directory: ./
File: tasks/pylaeva_s_convex_hull_bin/seq/src/ops_seq.cpp
Date: 2026-01-10 02:40:41
Exec Total Coverage
Lines: 66 67 98.5%
Functions: 10 10 100.0%
Branches: 64 82 78.0%
Line Branch Exec Source
1 #include "pylaeva_s_convex_hull_bin/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <cstdint>
7 #include <queue>
8 #include <utility>
9 #include <vector>
10
11 #include "pylaeva_s_convex_hull_bin/common/include/common.hpp"
12
13 namespace pylaeva_s_convex_hull_bin {
14
15 namespace {
16
17 int Cross(const Point &o, const Point &a, const Point &b) {
18 43664 return ((a.x - o.x) * (b.y - o.y)) - ((a.y - o.y) * (b.x - o.x));
19 }
20
21 4624 void ProcessPixelNeighbors(const Point &p, int width, int height, const ImageData &processed_data,
22 std::vector<bool> &visited, std::queue<Point> &q) {
23 4624 const std::vector<std::pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
24
25
2/2
✓ Branch 0 taken 18496 times.
✓ Branch 1 taken 4624 times.
 23120 for (const auto &dir : directions) {
26 18496 int nx = p.x + dir.first;
27 18496 int ny = p.y + dir.second;
28
29
8/8
✓ Branch 0 taken 18448 times.
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 18424 times.
✓ Branch 3 taken 24 times.
✓ Branch 4 taken 18376 times.
✓ Branch 5 taken 48 times.
✓ Branch 6 taken 18352 times.
✓ Branch 7 taken 24 times.
 18496 if (nx >= 0 && nx < width && ny >= 0 && ny < height) {
30 18352 int nidx = (ny * width) + nx;
31
4/4
✓ Branch 0 taken 14304 times.
✓ Branch 1 taken 4048 times.
✓ Branch 2 taken 4480 times.
✓ Branch 3 taken 9824 times.
 18352 if (processed_data.pixels[static_cast<size_t>(nidx)] == 255 && !visited[static_cast<size_t>(nidx)]) {
32 visited[static_cast<size_t>(nidx)] = true;
33 q.emplace(nx, ny);
34 }
35 }
36 }
37 4624 }
38
39 144 void ProcessConnectedComponent(int start_x, int start_y, int width, int height, const ImageData &processed_data,
40 std::vector<bool> &visited, std::vector<std::vector<Point>> &components) {
41
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 144 std::vector<Point> component;
42 std::queue<Point> q;
43
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 144 size_t start_idx = (static_cast<size_t>(start_y) * static_cast<size_t>(width)) + static_cast<size_t>(start_x);
44 q.emplace(start_x, start_y);
45 visited[start_idx] = true;
46
47
2/2
✓ Branch 0 taken 4624 times.
✓ Branch 1 taken 144 times.
 4768 while (!q.empty()) {
48 4624 Point p = q.front();
49 q.pop();
50 component.push_back(p);
51
52
1/2
✓ Branch 1 taken 4624 times.
✗ Branch 2 not taken.
 4624 ProcessPixelNeighbors(p, width, height, processed_data, visited, q);
53 }
54
55
1/2
✓ Branch 0 taken 144 times.
✗ Branch 1 not taken.
 144 if (!component.empty()) {
56
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 144 components.push_back(component);
57 }
58 144 }
59
60 } // namespace
61
62
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 PylaevaSConvexHullBinSEQ::PylaevaSConvexHullBinSEQ(const InType &in) : processed_data_(in) {
63 SetTypeOfTask(GetStaticTypeOfTask());
64
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 GetInput() = in;
65 80 }
66
67 80 bool PylaevaSConvexHullBinSEQ::ValidationImpl() {
68
3/6
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 80 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 80 times.
 80 return GetInput().width > 0 && GetInput().height > 0 && !GetInput().pixels.empty() &&
69
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 GetInput().pixels.size() == static_cast<size_t>(GetInput().width) * static_cast<size_t>(GetInput().height);
70 }
71
72 80 bool PylaevaSConvexHullBinSEQ::PreProcessingImpl() {
73 const uint8_t threshold = 128;
74
2/2
✓ Branch 0 taken 1232000 times.
✓ Branch 1 taken 80 times.
 1232080 for (auto &pixel : processed_data_.pixels) {
75
2/2
✓ Branch 0 taken 1227376 times.
✓ Branch 1 taken 4624 times.
 2459376 pixel = (pixel > threshold) ? 255 : 0;
76 }
77 80 return true;
78 }
79
80 80 bool PylaevaSConvexHullBinSEQ::RunImpl() {
81 80 FindConnectedComponents();
82 processed_data_.convex_hulls.clear();
83
84
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 80 times.
 224 for (const auto &component : processed_data_.components) {
85
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 64 times.
 144 if (component.size() >= 3) {
86 160 processed_data_.convex_hulls.push_back(GrahamScan(component));
87
1/2
✓ Branch 0 taken 64 times.
✗ Branch 1 not taken.
 64 } else if (!component.empty()) {
88 64 processed_data_.convex_hulls.push_back(component);
89 }
90 }
91
92 80 GetOutput() = processed_data_;
93 80 return true;
94 }
95
96 80 bool PylaevaSConvexHullBinSEQ::PostProcessingImpl() {
97 80 return true;
98 }
99
100 80 void PylaevaSConvexHullBinSEQ::FindConnectedComponents() {
101 80 int width = processed_data_.width;
102 80 int height = processed_data_.height;
103 80 int total_pixels = width * height;
104
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 80 times.
 80 std::vector<bool> visited(static_cast<size_t>(total_pixels), false);
105 processed_data_.components.clear();
106
107
2/2
✓ Branch 0 taken 8800 times.
✓ Branch 1 taken 80 times.
 8880 for (int row_y = 0; row_y < height; ++row_y) {
108
2/2
✓ Branch 0 taken 1232000 times.
✓ Branch 1 taken 8800 times.
 1240800 for (int col_x = 0; col_x < width; ++col_x) {
109
2/2
✓ Branch 0 taken 4624 times.
✓ Branch 1 taken 1227376 times.
 1232000 size_t idx = (static_cast<size_t>(row_y) * static_cast<size_t>(width)) + static_cast<size_t>(col_x);
110
4/4
✓ Branch 0 taken 4624 times.
✓ Branch 1 taken 1227376 times.
✓ Branch 2 taken 144 times.
✓ Branch 3 taken 4480 times.
 1232000 if (processed_data_.pixels[idx] == 255 && !visited[idx]) {
111
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 144 ProcessConnectedComponent(col_x, row_y, width, height, processed_data_, visited, processed_data_.components);
112 }
113 }
114 }
115 80 }
116
117
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 std::vector<Point> PylaevaSConvexHullBinSEQ::GrahamScan(const std::vector<Point> &points) {
118
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 if (points.size() <= 3) {
119 ✗ return points;
120 }
121
122 80 std::vector<Point> pts = points;
123 size_t n = pts.size();
124
125 size_t min_idx = 0;
126
2/2
✓ Branch 0 taken 4480 times.
✓ Branch 1 taken 80 times.
 4560 for (size_t i = 1; i < n; ++i) {
127
4/6
✓ Branch 0 taken 4480 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 224 times.
✓ Branch 3 taken 4256 times.
✓ Branch 4 taken 224 times.
✗ Branch 5 not taken.
 4480 if (pts[i].y < pts[min_idx].y || (pts[i].y == pts[min_idx].y && pts[i].x < pts[min_idx].x)) {
128 min_idx = i;
129 }
130 }
131 std::swap(pts[0], pts[min_idx]);
132
133 80 Point pivot = pts[0];
134 35440 std::sort(pts.begin() + 1, pts.end(), [&pivot](const Point &a, const Point &b) {
135 35360 int orient = Cross(pivot, a, b);
136
2/2
✓ Branch 0 taken 6960 times.
✓ Branch 1 taken 28400 times.
 35360 if (orient == 0) {
137 6960 return ((a.x - pivot.x) * (a.x - pivot.x)) + ((a.y - pivot.y) * (a.y - pivot.y)) <
138 6960 ((b.x - pivot.x) * (b.x - pivot.x)) + ((b.y - pivot.y) * (b.y - pivot.y));
139 }
140 28400 return orient > 0;
141 });
142
143 80 std::vector<Point> hull;
144
2/2
✓ Branch 0 taken 4560 times.
✓ Branch 1 taken 80 times.
 4640 for (size_t i = 0; i < n; ++i) {
145
4/4
✓ Branch 0 taken 8304 times.
✓ Branch 1 taken 384 times.
✓ Branch 2 taken 4176 times.
✓ Branch 3 taken 4128 times.
 8688 while (hull.size() >= 2 && Cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0) {
146 hull.pop_back();
147 }
148 hull.push_back(pts[i]);
149 }
150
151 return hull;
152 }
153 } // namespace pylaeva_s_convex_hull_bin
154