GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "urin_o_graham_passage/omp/include/ops_omp.hpp"
2
3			#include <algorithm>
4			#include <cmath>
5			#include <cstddef>
6			#include <vector>
7
8			#ifdef _OPENMP
9			# include <omp.h>
10			#endif
11
12			#include "urin_o_graham_passage/common/include/common.hpp"
13
14			namespace urin_o_graham_passage {
15
16		✗	UrinOGrahamPassageOMP::UrinOGrahamPassageOMP(const InType &in) {
17			SetTypeOfTask(GetStaticTypeOfTask());
18		✗	GetInput() = in;
19		✗	GetOutput() = OutType();
20		✗	}
21
22		✗	bool UrinOGrahamPassageOMP::ValidationImpl() {
23			const auto &points = GetInput();
24
25		✗	if (points.size() < 3) {
26			return false;
27			}
28
29			const Point &first = points[0];
30		✗	for (size_t i = 1; i < points.size(); ++i) {
31			if (points[i] != first) {
32			return true;
33			}
34			}
35
36			return false;
37			}
38
39		✗	bool UrinOGrahamPassageOMP::PreProcessingImpl() {
40			GetOutput().clear();
41		✗	return true;
42			}
43
44		✗	Point UrinOGrahamPassageOMP::FindLowestPoint(const InType &points) {
45		✗	Point lowest = points[0];
46
47		✗	for (size_t i = 1; i < points.size(); ++i) {
48		✗	if (points[i].y < lowest.y - 1e-10 ||
49		✗	(std::abs(points[i].y - lowest.y) < 1e-10 && points[i].x < lowest.x - 1e-10)) {
50		✗	lowest = points[i];
51			}
52			}
53
54		✗	return lowest;
55			}
56
57		✗	Point UrinOGrahamPassageOMP::FindLowestPointParallel(const InType &points) {
58			int lowest_index = 0;
59		✗	int n = static_cast<int>(points.size()); // Сохраняем размер в int
60
61		✗	#pragma omp parallel for default(none) shared(points, lowest_index, n)
62			for (int i = 1; i < n; ++i) { // Простое сравнение
63			#pragma omp critical
64			{
65			if (points[i].y < points[lowest_index].y - 1e-10 ||
66			(std::abs(points[i].y - points[lowest_index].y) < 1e-10 && points[i].x < points[lowest_index].x - 1e-10)) {
67			lowest_index = i;
68			}
69			}
70			}
71
72		✗	return points[lowest_index];
73			}
74
75		✗	double UrinOGrahamPassageOMP::PolarAngle(const Point &base, const Point &p) {
76		✗	double dx = p.x - base.x;
77		✗	double dy = p.y - base.y;
78
79		✗	if (std::abs(dx) < 1e-10 && std::abs(dy) < 1e-10) {
80			return -1e10;
81			}
82
83		✗	return std::atan2(dy, dx);
84			}
85
86		✗	int UrinOGrahamPassageOMP::Orientation(const Point &p, const Point &q, const Point &r) {
87		✗	double val = ((q.x - p.x) * (r.y - p.y)) - ((q.y - p.y) * (r.x - p.x));
88
89		✗	if (std::abs(val) < 1e-10) {
90			return 0;
91			}
92		✗	return (val > 0) ? 1 : -1;
93			}
94
95		✗	double UrinOGrahamPassageOMP::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> UrinOGrahamPassageOMP::PrepareOtherPoints(const InType &points, const Point &p0) {
102		✗	std::vector<Point> other_points;
103		✗	other_points.reserve(points.size() - 1);
104
105		✗	for (const auto &point : points) {
106			if (point != p0) {
107			other_points.push_back(point);
108			}
109			}
110
111		✗	std::ranges::sort(other_points, [&p0](const Point &a, const Point &b) { // Исправлено
112		✗	double angle_a = PolarAngle(p0, a);
113		✗	double angle_b = PolarAngle(p0, b);
114
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
121		✗	return other_points;
122			}
123
124		✗	std::vector<Point> UrinOGrahamPassageOMP::PrepareOtherPointsParallel(const InType &points, const Point &p0) {
125		✗	std::vector<Point> other_points;
126		✗	other_points.reserve(points.size() - 1);
127
128			#ifdef _OPENMP
129		✗	int n = static_cast<int>(points.size()); // Сохраняем размер в int
130
131		✗	# pragma omp parallel default(none) shared(points, p0, other_points, n)
132			{
133			std::vector<Point> local_points;
134			local_points.reserve((n / omp_get_num_threads()) + 1);
135
136			# pragma omp for nowait
137			for (int i = 0; i < n; ++i) { // Простое сравнение
138			if (points[i] != p0) {
139			local_points.push_back(points[i]);
140			}
141			}
142
143			# pragma omp critical
144			{
145			other_points.insert(other_points.end(), local_points.begin(), local_points.end());
146			}
147			}
148			#else
149			for (const auto &point : points) {
150			if (point != p0) {
151			other_points.push_back(point);
152			}
153			}
154			#endif
155
156		✗	std::ranges::sort(other_points, [&p0](const Point &a, const Point &b) { // Исправлено
157		✗	double angle_a = PolarAngle(p0, a);
158		✗	double angle_b = PolarAngle(p0, b);
159
160		✗	if (std::abs(angle_a - angle_b) < 1e-10) {
161		✗	return DistanceSquared(p0, a) < DistanceSquared(p0, b);
162			}
163		✗	return angle_a < angle_b;
164			});
165
166		✗	return other_points;
167			}
168
169		✗	bool UrinOGrahamPassageOMP::AreAllCollinear(const Point &p0, const std::vector<Point> &points) {
170		✗	bool all_collinear = true;
171		✗	int n = static_cast<int>(points.size()); // Сохраняем размер в int
172
173		✗	#pragma omp parallel for default(none) shared(points, p0, all_collinear, n)
174			for (int i = 1; i < n; ++i) { // Простое сравнение
175			if (Orientation(p0, points[0], points[i]) != 0) {
176			#pragma omp atomic write
177			all_collinear = false;
178			}
179			}
180
181		✗	return all_collinear;
182			}
183
184		✗	std::vector<Point> UrinOGrahamPassageOMP::BuildConvexHull(const Point &p0, const std::vector<Point> &points) {
185		✗	std::vector<Point> hull;
186		✗	hull.reserve(points.size() + 1);
187			hull.push_back(p0);
188			hull.push_back(points[0]);
189
190		✗	for (size_t i = 1; i < points.size(); ++i) {
191		✗	while (hull.size() >= 2) {
192			const Point &p = hull[hull.size() - 2];
193			const Point &q = hull.back();
194			if (Orientation(p, q, points[i]) <= 0) {
195			hull.pop_back();
196			} else {
197			break;
198			}
199			}
200			hull.push_back(points[i]);
201			}
202
203		✗	return hull;
204			}
205
206		✗	bool UrinOGrahamPassageOMP::RunImpl() {
207			const InType &points = GetInput();
208
209		✗	if (points.size() < 3) {
210			return false;
211			}
212
213		✗	Point p0 = FindLowestPointParallel(points);
214
215		✗	std::vector<Point> other_points = PrepareOtherPointsParallel(points, p0);
216		✗	if (other_points.empty()) {
217			return false;
218			}
219
220		✗	if (AreAllCollinear(p0, other_points)) {
221		✗	GetOutput() = {p0, other_points.back()};
222		✗	return true;
223			}
224
225		✗	GetOutput() = BuildConvexHull(p0, other_points);
226		✗	return true;
227			}
228
229		✗	bool UrinOGrahamPassageOMP::PostProcessingImpl() {
230		✗	return !GetOutput().empty();
231			}
232
233			} // namespace urin_o_graham_passage
234