GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "paramonov_v_bin_img_conv_hul/seq/include/ops_seq.hpp"
2
3			#include <algorithm>
4			#include <array>
5			#include <cstddef>
6			#include <cstdint>
7			#include <iterator>
8			#include <stack>
9			#include <utility>
10			#include <vector>
11
12			#include "paramonov_v_bin_img_conv_hul/common/include/common.hpp"
13
14			namespace paramonov_v_bin_img_conv_hul {
15
16			namespace {
17			constexpr std::array<std::pair<int, int>, 4> kNeighbors = {{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}};
18
19		✗	bool ComparePoints(const PixelPoint &a, const PixelPoint &b) {
20		✗	if (a.row != b.row) {
21		✗	return a.row < b.row;
22			}
23		✗	return a.col < b.col;
24			}
25
26			} // namespace
27
28		✗	ConvexHullSequential::ConvexHullSequential(const InputType &input) {
29			SetTypeOfTask(StaticTaskType());
30			GetInput() = input;
31		✗	}
32
33		✗	bool ConvexHullSequential::ValidationImpl() {
34			const auto &img = GetInput();
35		✗	if (img.rows <= 0 || img.cols <= 0) {
36			return false;
37			}
38
39		✗	const size_t expected_size = static_cast<size_t>(img.rows) * static_cast<size_t>(img.cols);
40		✗	return img.pixels.size() == expected_size;
41			}
42
43		✗	bool ConvexHullSequential::PreProcessingImpl() {
44			working_image_ = GetInput();
45			BinarizeImage();
46			GetOutput().clear();
47		✗	return true;
48			}
49
50		✗	bool ConvexHullSequential::RunImpl() {
51		✗	ExtractConnectedComponents();
52		✗	return true;
53			}
54
55		✗	bool ConvexHullSequential::PostProcessingImpl() {
56		✗	return true;
57			}
58
59		✗	void ConvexHullSequential::BinarizeImage(uint8_t threshold) {
60			std::ranges::transform(working_image_.pixels, working_image_.pixels.begin(),
61			[threshold](uint8_t pixel) { return pixel > threshold ? uint8_t{255} : uint8_t{0}; });
62		✗	}
63
64		✗	void ConvexHullSequential::FloodFill(int start_row, int start_col, std::vector<bool> &visited,
65			std::vector<PixelPoint> &component) const {
66			std::stack<PixelPoint> pixel_stack;
67			pixel_stack.emplace(start_row, start_col);
68
69		✗	const int rows = working_image_.rows;
70		✗	const int cols = working_image_.cols;
71
72		✗	visited[PixelIndex(start_row, start_col, cols)] = true;
73
74		✗	while (!pixel_stack.empty()) {
75		✗	PixelPoint current = pixel_stack.top();
76			pixel_stack.pop();
77
78			component.push_back(current);
79
80		✗	for (const auto &[dr, dc] : kNeighbors) {
81		✗	int next_row = current.row + dr;
82		✗	int next_col = current.col + dc;
83
84		✗	if (next_row >= 0 && next_row < rows && next_col >= 0 && next_col < cols) {
85			size_t idx = PixelIndex(next_row, next_col, cols);
86		✗	if (!visited[idx] && working_image_.pixels[idx] == 255) {
87			visited[idx] = true;
88			pixel_stack.emplace(next_row, next_col);
89			}
90			}
91			}
92			}
93		✗	}
94
95		✗	void ConvexHullSequential::ExtractConnectedComponents() {
96		✗	const int rows = working_image_.rows;
97		✗	const int cols = working_image_.cols;
98		✗	const size_t total_pixels = static_cast<size_t>(rows) * static_cast<size_t>(cols);
99
100		✗	std::vector<bool> visited(total_pixels, false);
101			auto &output_hulls = GetOutput();
102
103		✗	for (int row = 0; row < rows; ++row) {
104		✗	for (int col = 0; col < cols; ++col) {
105			size_t idx = PixelIndex(row, col, cols);
106
107		✗	if (working_image_.pixels[idx] == 255 && !visited[idx]) {
108		✗	std::vector<PixelPoint> component;
109		✗	FloodFill(row, col, visited, component);
110
111		✗	if (!component.empty()) {
112		✗	std::vector<PixelPoint> hull = ComputeConvexHull(component);
113			output_hulls.push_back(std::move(hull));
114			}
115			}
116			}
117			}
118		✗	}
119
120		✗	int64_t ConvexHullSequential::Orientation(const PixelPoint &p, const PixelPoint &q, const PixelPoint &r) {
121		✗	return (static_cast<int64_t>(q.col - p.col) * (r.row - p.row)) -
122		✗	(static_cast<int64_t>(q.row - p.row) * (r.col - p.col));
123			}
124
125		✗	std::vector<PixelPoint> ConvexHullSequential::ComputeConvexHull(const std::vector<PixelPoint> &points) {
126		✗	if (points.size() <= 2) {
127		✗	return points;
128			}
129
130		✗	auto lowest_point = *std::ranges::min_element(points, ComparePoints);
131
132		✗	std::vector<PixelPoint> sorted_points;
133		✗	std::ranges::copy_if(points, std::back_inserter(sorted_points), [&lowest_point](const PixelPoint &p) {
134		✗	return (p.row != lowest_point.row) || (p.col != lowest_point.col);
135			});
136
137		✗	std::ranges::sort(sorted_points, [&lowest_point](const PixelPoint &a, const PixelPoint &b) {
138		✗	int64_t orient = Orientation(lowest_point, a, b);
139		✗	if (orient == 0) {
140		✗	int64_t dist_a = ((a.row - lowest_point.row) * (a.row - lowest_point.row)) +
141		✗	((a.col - lowest_point.col) * (a.col - lowest_point.col));
142		✗	int64_t dist_b = ((b.row - lowest_point.row) * (b.row - lowest_point.row)) +
143		✗	((b.col - lowest_point.col) * (b.col - lowest_point.col));
144		✗	return dist_a < dist_b;
145			}
146		✗	return orient > 0;
147			});
148
149		✗	std::vector<PixelPoint> hull;
150			hull.push_back(lowest_point);
151
152		✗	for (const auto &p : sorted_points) {
153		✗	while (hull.size() >= 2) {
154			const auto &a = hull[hull.size() - 2];
155			const auto &b = hull.back();
156
157		✗	if (Orientation(a, b, p) <= 0) {
158			hull.pop_back();
159			} else {
160			break;
161			}
162			}
163			hull.push_back(p);
164			}
165
166			return hull;
167			}
168
169			} // namespace paramonov_v_bin_img_conv_hul
170