GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "urin_o_graham_passage/all/include/ops_all.hpp"
2
3			#include <algorithm>
4			#include <atomic>
5			#include <cmath>
6			#include <cstddef>
7			// #include <thread>
8			#include <vector>
9
10			// Подключение TBB
11			#include <tbb/blocked_range.h>
12			#include <tbb/concurrent_vector.h>
13			#include <tbb/parallel_for.h>
14			#include <tbb/parallel_reduce.h>
15
16			// OpenMP (используется для демонстрации в одном из этапов)
17			#include <omp.h>
18
19			#include "urin_o_graham_passage/common/include/common.hpp"
20			// #include "util/include/util.hpp"
21
22			namespace urin_o_graham_passage {
23
24		✗	UrinOGrahamPassageALL::UrinOGrahamPassageALL(const InType &in) {
25			SetTypeOfTask(GetStaticTypeOfTask());
26		✗	GetInput() = in;
27		✗	GetOutput() = OutType();
28		✗	}
29
30		✗	bool UrinOGrahamPassageALL::ValidationImpl() {
31			const auto &points = GetInput();
32		✗	if (points.size() < 3) {
33			return false;
34			}
35			const Point &first = points[0];
36		✗	for (size_t i = 1; i < points.size(); ++i) {
37			if (points[i] != first) {
38			return true;
39			}
40			}
41			return false;
42			}
43
44		✗	bool UrinOGrahamPassageALL::PreProcessingImpl() {
45			GetOutput().clear();
46		✗	return true;
47			}
48
49		✗	Point UrinOGrahamPassageALL::FindLowestPoint(const InType &points) {
50		✗	Point lowest = points[0];
51		✗	for (size_t i = 1; i < points.size(); ++i) {
52		✗	if (points[i].y < lowest.y - 1e-10 ||
53		✗	(std::abs(points[i].y - lowest.y) < 1e-10 && points[i].x < lowest.x - 1e-10)) {
54		✗	lowest = points[i];
55			}
56			}
57		✗	return lowest;
58			}
59
60		✗	Point UrinOGrahamPassageALL::FindLowestPointParallel(const InType &points) {
61		✗	return tbb::parallel_reduce(tbb::blocked_range<size_t>(0, points.size()), points[0],
62		✗	[&points](const tbb::blocked_range<size_t> &range, Point current_min) {
63		✗	for (size_t i = range.begin(); i < range.end(); ++i) {
64		✗	if (points[i].y < current_min.y - 1e-10 ||
65		✗	(std::abs(points[i].y - current_min.y) < 1e-10 && points[i].x < current_min.x - 1e-10)) {
66		✗	current_min = points[i];
67			}
68			}
69		✗	return current_min;
70		✗	}, [](const Point &a, const Point &b) {
71		✗	if (a.y < b.y - 1e-10 || (std::abs(a.y - b.y) < 1e-10 && a.x < b.x - 1e-10)) {
72		✗	return a;
73			}
74		✗	return b;
75		✗	});
76			}
77
78		✗	double UrinOGrahamPassageALL::PolarAngle(const Point &base, const Point &p) {
79		✗	double dx = p.x - base.x;
80		✗	double dy = p.y - base.y;
81		✗	if (std::abs(dx) < 1e-10 && std::abs(dy) < 1e-10) {
82			return -1e10;
83			}
84		✗	return std::atan2(dy, dx);
85			}
86
87		✗	int UrinOGrahamPassageALL::Orientation(const Point &p, const Point &q, const Point &r) {
88		✗	double val = ((q.x - p.x) * (r.y - p.y)) - ((q.y - p.y) * (r.x - p.x));
89		✗	if (std::abs(val) < 1e-10) {
90			return 0;
91			}
92		✗	return (val > 0) ? 1 : -1;
93			}
94
95		✗	double UrinOGrahamPassageALL::DistanceSquared(const Point &p1, const Point &p2) {
96		✗	double dx = p2.x - p1.x;
97		✗	double dy = p2.y - p1.y;
98		✗	return (dx * dx) + (dy * dy);
99			}
100
101		✗	std::vector<Point> UrinOGrahamPassageALL::PrepareOtherPointsParallel(const InType &points, const Point &p0) {
102			tbb::concurrent_vector<Point> other_points_concurrent;
103		✗	tbb::parallel_for(tbb::blocked_range<size_t>(0, points.size()),
104		✗	[&points, &p0, &other_points_concurrent](const tbb::blocked_range<size_t> &range) {
105		✗	for (size_t i = range.begin(); i < range.end(); ++i) {
106		✗	if (points[i] != p0) {
107		✗	other_points_concurrent.push_back(points[i]);
108			}
109			}
110		✗	});
111		✗	std::vector<Point> other_points(other_points_concurrent.begin(), other_points_concurrent.end());
112		✗	std::ranges::sort(other_points.begin(), other_points.end(), [&p0](const Point &a, const Point &b) {
113		✗	double angle_a = PolarAngle(p0, a);
114		✗	double angle_b = PolarAngle(p0, b);
115		✗	if (std::abs(angle_a - angle_b) < 1e-10) {
116		✗	return DistanceSquared(p0, a) < DistanceSquared(p0, b);
117			}
118		✗	return angle_a < angle_b;
119			});
120		✗	return other_points;
121			}
122
123		✗	bool UrinOGrahamPassageALL::AreAllCollinear(const Point &p0, const std::vector<Point> &points) {
124		✗	std::atomic<bool> all_collinear{true};
125		✗	tbb::parallel_for(tbb::blocked_range<size_t>(1, points.size()),
126		✗	[&points, &p0, &all_collinear](const tbb::blocked_range<size_t> &range) {
127		✗	for (size_t i = range.begin(); i < range.end() && all_collinear.load(); ++i) {
128		✗	if (Orientation(p0, points[0], points[i]) != 0) {
129		✗	all_collinear.store(false);
130			}
131			}
132		✗	});
133		✗	return all_collinear.load();
134			}
135
136		✗	std::vector<Point> UrinOGrahamPassageALL::BuildConvexHull(const Point &p0, const std::vector<Point> &points) {
137		✗	std::vector<Point> hull;
138		✗	hull.reserve(points.size() + 1);
139			hull.push_back(p0);
140			hull.push_back(points[0]);
141		✗	for (size_t i = 1; i < points.size(); ++i) {
142		✗	while (hull.size() >= 2) {
143			const Point &p = hull[hull.size() - 2];
144			const Point &q = hull.back();
145			if (Orientation(p, q, points[i]) <= 0) {
146			hull.pop_back();
147			} else {
148			break;
149			}
150			}
151			hull.push_back(points[i]);
152			}
153		✗	return hull;
154			}
155
156		✗	bool UrinOGrahamPassageALL::RunImpl() {
157			const InType &points = GetInput();
158		✗	if (points.size() < 3) {
159			return false;
160			}
161
162			// Поиск самой нижней точки – через TBB parallel_reduce
163		✗	Point p0 = FindLowestPointParallel(points);
164
165			// Сбор точек, отличных от p0 – через TBB concurrent_vector
166		✗	std::vector<Point> other_points = PrepareOtherPointsParallel(points, p0);
167		✗	if (other_points.empty()) {
168			return false;
169			}
170
171			// Проверка на коллинеарность – через TBB parallel_for с атомарным флагом
172		✗	if (AreAllCollinear(p0, other_points)) {
173		✗	GetOutput() = {p0, other_points.back()};
174		✗	return true;
175			}
176
177			// Построение выпуклой оболочки – последовательно
178		✗	GetOutput() = BuildConvexHull(p0, other_points);
179		✗	return true;
180			}
181
182		✗	bool UrinOGrahamPassageALL::PostProcessingImpl() {
183		✗	return !GetOutput().empty();
184			}
185
186			} // namespace urin_o_graham_passage
187