GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "egorova_l_binary_convex_hull/seq/include/ops_seq.hpp"
2
3			#include <algorithm>
4			#include <cstddef>
5			#include <cstdint>
6			#include <stack>
7			#include <tuple>
8			#include <utility> // для std::move
9			#include <vector>
10
11			#include "egorova_l_binary_convex_hull/common/include/common.hpp"
12
13			namespace {
14
15			using Point = egorova_l_binary_convex_hull::Point;
16
17			int64_t CrossProduct(const Point &a, const Point &b, const Point &c) {
18		✗	return (static_cast<int64_t>(b.x - a.x) * (c.y - a.y)) - (static_cast<int64_t>(b.y - a.y) * (c.x - a.x));
19			}
20
21			// Helper function for building lower hull
22		✗	void BuildLowerHull(const std::vector<Point> &points, size_t n, std::vector<Point> &hull) {
23		✗	for (size_t i = 0; i < n; ++i) {
24		✗	while (hull.size() >= 2) {
25			const Point &a = hull[hull.size() - 2];
26			const Point &b = hull.back();
27		✗	if (CrossProduct(a, b, points[i]) <= 0) {
28			hull.pop_back();
29			} else {
30			break;
31			}
32			}
33			hull.push_back(points[i]);
34			}
35		✗	}
36
37			// Helper function for building upper hull
38		✗	void BuildUpperHull(const std::vector<Point> &points, size_t n, size_t lower_size, std::vector<Point> &hull) {
39		✗	for (size_t i = n - 1; i > 0; --i) {
40		✗	const size_t idx = i - 1;
41		✗	while (hull.size() > lower_size) {
42			const Point &a = hull[hull.size() - 2];
43			const Point &b = hull.back();
44		✗	if (CrossProduct(a, b, points[idx]) <= 0) {
45			hull.pop_back();
46			} else {
47			break;
48			}
49			}
50			hull.push_back(points[idx]);
51			}
52		✗	}
53
54		✗	void BuildConvexHull(std::vector<Point> &points, std::vector<Point> &hull) {
55			const size_t n = points.size();
56		✗	if (n <= 2) {
57		✗	hull.assign(points.begin(), points.end());
58		✗	return;
59			}
60
61			// Sort points in-place
62			std::ranges::sort(points,
63			[](const Point &lhs, const Point &rhs) { return std::tie(lhs.x, lhs.y) < std::tie(rhs.x, rhs.y); });
64
65			hull.clear();
66		✗	hull.reserve(n + 1); // Reserve space to avoid reallocations
67
68			// Build lower hull
69		✗	BuildLowerHull(points, n, hull);
70
71			// Build upper hull
72			const size_t lower_size = hull.size();
73		✗	BuildUpperHull(points, n, lower_size, hull);
74
75			// Remove the last point if it's the same as the first (closed polygon)
76		✗	if (hull.size() > 1 && hull.front().x == hull.back().x && hull.front().y == hull.back().y) {
77			hull.pop_back();
78			}
79			}
80
81			// Helper function to process a single direction
82		✗	inline void TryAddNeighbor(const std::vector<uint8_t> &image, int width, int height, int next_x, int next_y, int label,
83			std::vector<int> &labels, std::stack<Point> &stack) {
84		✗	if (next_x >= 0 && next_x < width && next_y >= 0 && next_y < height) {
85		✗	const size_t next_index = (static_cast<size_t>(next_y) * static_cast<size_t>(width)) + static_cast<size_t>(next_x);
86		✗	if (image[next_index] != 0 && labels[next_index] == 0) {
87		✗	labels[next_index] = label;
88		✗	stack.push({next_x, next_y});
89			}
90			}
91		✗	}
92
93		✗	void ProcessComponent(const std::vector<uint8_t> &image, int width, int height, int start_x, int start_y, int label,
94			std::vector<int> &labels, std::vector<Point> &component_points) {
95			std::stack<Point> stack;
96		✗	stack.push({start_x, start_y});
97
98		✗	const size_t start_index = (static_cast<size_t>(start_y) * static_cast<size_t>(width)) + static_cast<size_t>(start_x);
99		✗	labels[start_index] = label;
100
101			component_points.clear();
102		✗	component_points.reserve(100); // Reserve some space to avoid reallocations
103
104		✗	while (!stack.empty()) {
105		✗	const Point current = stack.top();
106			stack.pop();
107			component_points.push_back(current);
108
109			// Process all 4 directions using helper function
110		✗	TryAddNeighbor(image, width, height, current.x + 1, current.y, label, labels, stack);
111		✗	TryAddNeighbor(image, width, height, current.x - 1, current.y, label, labels, stack);
112		✗	TryAddNeighbor(image, width, height, current.x, current.y + 1, label, labels, stack);
113		✗	TryAddNeighbor(image, width, height, current.x, current.y - 1, label, labels, stack);
114			}
115		✗	}
116
117			} // namespace
118
119			namespace egorova_l_binary_convex_hull {
120
121		✗	BinaryConvexHullSEQ::BinaryConvexHullSEQ(const InType &in) {
122			SetTypeOfTask(GetStaticTypeOfTask());
123			GetInput() = in;
124		✗	}
125
126		✗	bool BinaryConvexHullSEQ::ValidationImpl() {
127			const auto &input = GetInput();
128		✗	return input.width > 0 && input.height > 0 && !input.data.empty();
129			}
130
131		✗	bool BinaryConvexHullSEQ::PreProcessingImpl() {
132			GetOutput().clear();
133		✗	return true;
134			}
135
136		✗	bool BinaryConvexHullSEQ::RunImpl() {
137		✗	const int width = GetInput().width;
138		✗	const int height = GetInput().height;
139		✗	const auto &image = GetInput().data;
140		✗	const size_t image_size = static_cast<size_t>(width) * static_cast<size_t>(height);
141
142		✗	std::vector<int> labels(image_size, 0);
143			int label_counter = 0;
144
145			// Clear output and reserve some space
146			auto &output = GetOutput();
147			output.clear();
148		✗	output.reserve(10); // Reserve space for expected number of components
149
150		✗	for (int row = 0; row < height; ++row) {
151		✗	for (int col = 0; col < width; ++col) {
152		✗	const size_t index = (static_cast<size_t>(row) * static_cast<size_t>(width)) + static_cast<size_t>(col);
153		✗	if (image[index] != 0 && labels[index] == 0) {
154		✗	++label_counter;
155		✗	std::vector<Point> component_points;
156
157		✗	ProcessComponent(image, width, height, col, row, label_counter, labels, component_points);
158
159		✗	if (!component_points.empty()) {
160		✗	std::vector<Point> hull;
161		✗	BuildConvexHull(component_points, hull);
162			output.push_back(std::move(hull));
163			}
164			}
165			}
166			}
167		✗	return true;
168			}
169
170		✗	bool BinaryConvexHullSEQ::PostProcessingImpl() {
171		✗	return true;
172			}
173
174			} // namespace egorova_l_binary_convex_hull
175