GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "urin_o_graham_passage/stl/include/ops_stl.hpp"
2
3			#include <algorithm>
4			#include <atomic>
5			#include <cmath>
6			#include <cstddef>
7			#include <thread>
8			#include <vector>
9
10			#include "urin_o_graham_passage/common/include/common.hpp"
11
12			namespace urin_o_graham_passage {
13
14		✗	UrinOGrahamPassageSTL::UrinOGrahamPassageSTL(const InType &in) {
15			SetTypeOfTask(GetStaticTypeOfTask());
16		✗	GetInput() = in;
17		✗	GetOutput() = OutType();
18		✗	}
19
20		✗	bool UrinOGrahamPassageSTL::ValidationImpl() {
21			const auto &points = GetInput();
22
23		✗	if (points.size() < 3) {
24			return false;
25			}
26
27			const Point &first = points[0];
28		✗	for (size_t i = 1; i < points.size(); ++i) {
29			if (points[i] != first) {
30			return true;
31			}
32			}
33
34			return false;
35			}
36
37		✗	bool UrinOGrahamPassageSTL::PreProcessingImpl() {
38			GetOutput().clear();
39		✗	return true;
40			}
41			//.
42		✗	Point UrinOGrahamPassageSTL::FindLocalMinimum(const InType &points, size_t start, size_t end) {
43		✗	Point local_min = points[start];
44		✗	for (size_t i = start + 1; i < end; ++i) {
45		✗	if (points[i].y < local_min.y - 1e-10 ||
46		✗	(std::abs(points[i].y - local_min.y) < 1e-10 && points[i].x < local_min.x - 1e-10)) {
47		✗	local_min = points[i];
48			}
49			}
50		✗	return local_min;
51			}
52
53		✗	Point UrinOGrahamPassageSTL::CombineMinimums(const std::vector<Point> &mins) {
54		✗	Point global_min = mins[0];
55		✗	for (size_t i = 1; i < mins.size(); ++i) {
56		✗	if (mins[i].y < global_min.y - 1e-10 ||
57		✗	(std::abs(mins[i].y - global_min.y) < 1e-10 && mins[i].x < global_min.x - 1e-10)) {
58		✗	global_min = mins[i];
59			}
60			}
61		✗	return global_min;
62			}
63
64		✗	Point UrinOGrahamPassageSTL::FindLowestPoint(const InType &points) {
65		✗	Point lowest = points[0];
66
67		✗	for (size_t i = 1; i < points.size(); ++i) {
68		✗	if (points[i].y < lowest.y - 1e-10 ||
69		✗	(std::abs(points[i].y - lowest.y) < 1e-10 && points[i].x < lowest.x - 1e-10)) {
70		✗	lowest = points[i];
71			}
72			}
73
74		✗	return lowest;
75			}
76
77		✗	Point UrinOGrahamPassageSTL::FindLowestPointParallel(const InType &points) {
78		✗	unsigned int num_threads = std::thread::hardware_concurrency();
79		✗	if (num_threads == 0) {
80			num_threads = 2;
81			}
82
83		✗	std::vector<std::thread> threads;
84		✗	std::vector<Point> local_mins(num_threads, points[0]);
85		✗	size_t block_size = points.size() / num_threads;
86
87		✗	for (unsigned int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
88		✗	size_t start = thread_idx * block_size;
89		✗	size_t end = (thread_idx == num_threads - 1) ? points.size() : start + block_size;
90
91		✗	threads.emplace_back([&points, start, end, &local_mins, thread_idx]() {
92		✗	local_mins[thread_idx] = FindLocalMinimum(points, start, end);
93		✗	});
94			}
95
96		✗	for (auto &th : threads) {
97		✗	th.join();
98			}
99
100		✗	return CombineMinimums(local_mins);
101		✗	}
102
103		✗	double UrinOGrahamPassageSTL::PolarAngle(const Point &base, const Point &p) {
104		✗	double dx = p.x - base.x;
105		✗	double dy = p.y - base.y;
106
107		✗	if (std::abs(dx) < 1e-10 && std::abs(dy) < 1e-10) {
108			return -1e10;
109			}
110
111		✗	return std::atan2(dy, dx);
112			}
113
114		✗	int UrinOGrahamPassageSTL::Orientation(const Point &p, const Point &q, const Point &r) {
115		✗	double val = ((q.x - p.x) * (r.y - p.y)) - ((q.y - p.y) * (r.x - p.x));
116
117		✗	if (std::abs(val) < 1e-10) {
118			return 0;
119			}
120		✗	return (val > 0) ? 1 : -1;
121			}
122
123		✗	double UrinOGrahamPassageSTL::DistanceSquared(const Point &p1, const Point &p2) {
124		✗	double dx = p2.x - p1.x;
125		✗	double dy = p2.y - p1.y;
126		✗	return (dx * dx) + (dy * dy);
127			}
128
129		✗	std::vector<Point> UrinOGrahamPassageSTL::PrepareOtherPointsParallel(const InType &points, const Point &p0) {
130		✗	unsigned int num_threads = std::thread::hardware_concurrency();
131		✗	if (num_threads == 0) {
132			num_threads = 2;
133			}
134
135		✗	std::vector<std::thread> threads;
136		✗	std::vector<std::vector<Point>> local_points(num_threads);
137		✗	size_t block_size = points.size() / num_threads;
138
139		✗	for (unsigned int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
140		✗	size_t start = thread_idx * block_size;
141		✗	size_t end = (thread_idx == num_threads - 1) ? points.size() : start + block_size;
142
143		✗	threads.emplace_back([&points, &p0, start, end, &local_points, thread_idx]() {
144		✗	for (size_t i = start; i < end; ++i) {
145		✗	if (points[i] != p0) {
146		✗	local_points[thread_idx].push_back(points[i]);
147			}
148			}
149		✗	});
150			}
151
152		✗	for (auto &th : threads) {
153		✗	th.join();
154			}
155
156		✗	std::vector<Point> other_points;
157		✗	for (const auto &vec : local_points) {
158		✗	other_points.insert(other_points.end(), vec.begin(), vec.end());
159			}
160
161		✗	std::ranges::sort(other_points.begin(), other_points.end(), [&p0](const Point &a, const Point &b) {
162		✗	double angle_a = PolarAngle(p0, a);
163		✗	double angle_b = PolarAngle(p0, b);
164		✗	if (std::abs(angle_a - angle_b) < 1e-10) {
165		✗	return DistanceSquared(p0, a) < DistanceSquared(p0, b);
166			}
167		✗	return angle_a < angle_b;
168			});
169
170		✗	return other_points;
171		✗	}
172
173		✗	bool UrinOGrahamPassageSTL::AreAllCollinear(const Point &p0, const std::vector<Point> &points) {
174		✗	std::atomic<bool> all_collinear{true};
175		✗	unsigned int num_threads = std::thread::hardware_concurrency();
176		✗	if (num_threads == 0) {
177			num_threads = 2;
178			}
179
180		✗	std::vector<std::thread> threads;
181		✗	size_t block_size = points.size() / num_threads;
182
183		✗	for (unsigned int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
184		✗	size_t start = (thread_idx == 0) ? 1 : thread_idx * block_size;
185		✗	size_t end = (thread_idx == num_threads - 1) ? points.size() : (thread_idx + 1) * block_size;
186
187		✗	threads.emplace_back([&points, &p0, start, end, &all_collinear]() {
188		✗	for (size_t i = start; i < end && all_collinear.load(); ++i) {
189		✗	if (Orientation(p0, points[0], points[i]) != 0) {
190		✗	all_collinear.store(false);
191			}
192			}
193		✗	});
194			}
195
196		✗	for (auto &th : threads) {
197		✗	th.join();
198			}
199
200		✗	return all_collinear.load();
201		✗	}
202
203		✗	std::vector<Point> UrinOGrahamPassageSTL::BuildConvexHull(const Point &p0, const std::vector<Point> &points) {
204		✗	std::vector<Point> hull;
205		✗	hull.reserve(points.size() + 1);
206			hull.push_back(p0);
207			hull.push_back(points[0]);
208
209		✗	for (size_t i = 1; i < points.size(); ++i) {
210		✗	while (hull.size() >= 2) {
211			const Point &p = hull[hull.size() - 2];
212			const Point &q = hull.back();
213			if (Orientation(p, q, points[i]) <= 0) {
214			hull.pop_back();
215			} else {
216			break;
217			}
218			}
219			hull.push_back(points[i]);
220			}
221
222		✗	return hull;
223			}
224
225		✗	bool UrinOGrahamPassageSTL::RunImpl() {
226			const InType &points = GetInput();
227
228		✗	if (points.size() < 3) {
229			return false;
230			}
231
232		✗	Point p0 = FindLowestPointParallel(points);
233
234		✗	std::vector<Point> other_points = PrepareOtherPointsParallel(points, p0);
235		✗	if (other_points.empty()) {
236			return false;
237			}
238
239		✗	if (AreAllCollinear(p0, other_points)) {
240		✗	GetOutput() = {p0, other_points.back()};
241		✗	return true;
242			}
243
244		✗	GetOutput() = BuildConvexHull(p0, other_points);
245		✗	return true;
246			}
247
248		✗	bool UrinOGrahamPassageSTL::PostProcessingImpl() {
249		✗	return !GetOutput().empty();
250			}
251
252			} // namespace urin_o_graham_passage
253