Locus No Pilotus
Project of four first grade MIPT DAFE/RSE students (for engineering practical work in the second semester) in Qt C++
Loading...
Searching...
No Matches
math::OptimalWayCalculator Class Reference

Функтор, находящий кратчайший путь между точками More...

#include <optimal_way.h>

Collaboration diagram for math::OptimalWayCalculator:

Public Member Functions

 OptimalWayCalculator (const std::vector< CircleObstacle > &circles, const std::vector< PolygonObstacle > &polys)
 Находит кратчайший путь между точками
 
void FindOptimalWay (Point p1, Point p2)
 
std::vector< std::shared_ptr< PathWayNode > > GetGraphNodes ()
 
std::vector< std::size_t > GetOptimalWay ()
 
double GetOptimalWayLength ()
 
std::vector< lib::SegmentGetTrajectoryPart ()
 

Private Member Functions

void AddCommonTangents ()
 
std::set< std::size_t > AddGraphControlPoints (Point point)
 
void AddGraphTangentPoints ()
 
template<typename T , typename U >
void AddTangent (const LinearFunction &tangent, T &obstacle1, U &obstacle2)
 Добавляет информацию об общей касательной двух препятствий
 
void MakeTrajectoryPart ()
 
void ResetInformation ()
 
template<typename T , typename U >
bool TangentGoesThroughOtherObstacle (const LinearFunction &tangent, T &obstacle1, U &obstacle2)
 Проверяет, пересекает ли общая касательная двух препятствий другое препятствие
 
bool TangentGoesThroughOtherObstacle (const Point &tangent_point, const Point &control_point)
 Проверяет, пересекает ли касательная препятствие
 

Private Attributes

std::vector< CircleObstaclecircles_
 
PathWayGraph graph_
 
std::vector< std::size_t > optimal_way_
 
double optimal_way_length_
 
std::vector< PolygonObstaclepolys_
 
std::vector< lib::Segmenttrajectory_part_
 

Detailed Description

Функтор, находящий кратчайший путь между точками

Constructor & Destructor Documentation

◆ OptimalWayCalculator()

math::OptimalWayCalculator::OptimalWayCalculator ( const std::vector< CircleObstacle > & circles,
const std::vector< PolygonObstacle > & polys )
inline

Находит кратчайший путь между точками

Parameters
circlesкруговые препятствия
polysмногоугольные препятствия
22 : circles_{circles}, polys_{polys} {
25 }
void AddCommonTangents()
Definition optimal_way.cpp:50
void AddGraphTangentPoints()
Definition optimal_way.cpp:87
std::vector< CircleObstacle > circles_
Definition optimal_way.h:41
std::vector< PolygonObstacle > polys_
Definition optimal_way.h:43
Here is the call graph for this function:

Member Function Documentation

◆ AddCommonTangents()

void math::OptimalWayCalculator::AddCommonTangents ( )
private
50 {
51 for (std::size_t i = 0; i < circles_.size(); ++i) {
52 for (std::size_t j = i + 1; j < circles_.size(); ++j) {
53 std::vector<LinearFunction> tangents =
55
56 for (std::size_t k = 0; k < tangents.size(); ++k)
57 if (!TangentGoesThroughOtherObstacle<CircleObstacle, CircleObstacle>(
58 tangents[k], circles_[i], circles_[j]))
59 AddTangent<CircleObstacle, CircleObstacle>(tangents[k], circles_[i],
60 circles_[j]);
61 }
62 }
63 for (std::size_t i = 0; i < polys_.size(); ++i) {
64 for (std::size_t j = 0; j < circles_.size(); ++j) {
65 std::vector<LinearFunction> tangents =
67
68 for (std::size_t k = 0; k < tangents.size(); ++k)
69 if (!TangentGoesThroughOtherObstacle<PolygonObstacle, CircleObstacle>(
70 tangents[k], polys_[i], circles_[j]))
71 AddTangent<PolygonObstacle, CircleObstacle>(tangents[k], polys_[i],
72 circles_[j]);
73 }
74 for (std::size_t j = i + 1; j < polys_.size(); ++j) {
75 std::vector<LinearFunction> tangents =
77
78 for (std::size_t k = 0; k < tangents.size(); ++k)
79 if (!TangentGoesThroughOtherObstacle<PolygonObstacle, PolygonObstacle>(
80 tangents[k], polys_[i], polys_[j]))
81 AddTangent<PolygonObstacle, PolygonObstacle>(tangents[k], polys_[i],
82 polys_[j]);
83 }
84 }
85}
std::vector< LinearFunction > TangentsBetween(const CircleObstacle &circle1, const CircleObstacle &circle2)
Находит уравнения общих касательных двух кругов
Definition helpers_functions.cpp:158
Here is the call graph for this function:
Here is the caller graph for this function:

◆ AddGraphControlPoints()

std::set< std::size_t > math::OptimalWayCalculator::AddGraphControlPoints ( Point point)
private
152 {
153 std::set<std::size_t> tangent_points_numbers;
154 for (auto& circle : circles_) {
155 std::pair<Point, Point> tangent_points = TangentPoints(circle, point);
156 for (auto& tangent_point : {tangent_points.first, tangent_points.second}) {
157 if (TangentGoesThroughOtherObstacle(tangent_point, point)) continue;
158 bool is_unique = true;
159 for (std::size_t i = 0; i < graph_.nodes.size(); ++i) {
160 if (tangent_point == graph_.nodes[i]->point) {
161 is_unique = false;
162 tangent_points_numbers.insert(graph_.nodes[i]->number);
163 break;
164 }
165 }
166 if (!is_unique) continue;
167 PathWayNode* new_node =
168 new PathWayNode(tangent_point, graph_.nodes.size(), false);
169 new_node->circle_ptr = std::make_shared<CircleObstacle>(circle);
170 tangent_points_numbers.insert(graph_.nodes.size());
171 graph_.AddNode(new_node);
172
173 for (std::size_t i = 0; i < graph_.nodes.size(); ++i) {
174 if ((graph_.nodes[i]->circle_ptr) &&
175 (*graph_.nodes[i]->circle_ptr == circle) &&
176 (graph_.nodes[i]->number != new_node->number)) {
177 graph_.AddEdge(graph_.nodes[i]->number, new_node->number,
178 DistanceBetweenPointsOnCircle(circle, tangent_point,
179 graph_.nodes[i]->point));
180 }
181 }
182 }
183 }
184
185 for (auto& poly : polys_) {
186 std::pair<Point, Point> tangent_points = TangentPoints(poly, point);
187 for (auto& tangent_point : {tangent_points.first, tangent_points.second}) {
188 if (TangentGoesThroughOtherObstacle(tangent_point, point)) continue;
189 for (std::size_t i = 0; i < graph_.nodes.size(); ++i) {
190 if (tangent_point == graph_.nodes[i]->point) {
191 tangent_points_numbers.insert(graph_.nodes[i]->number);
192 break;
193 }
194 }
195 }
196 }
197
198 return tangent_points_numbers;
199}
bool TangentGoesThroughOtherObstacle(const LinearFunction &tangent, T &obstacle1, U &obstacle2)
Проверяет, пересекает ли общая касательная двух препятствий другое препятствие
Definition optimal_way.cpp:12
PathWayGraph graph_
Definition optimal_way.h:46
std::pair< Point, Point > TangentPoints(const LinearFunction &tangent, const CircleObstacle &circle1, const CircleObstacle &circle2)
Находит точки касания кругов с их общей касательной
Definition helpers_functions.cpp:43
double DistanceBetweenPointsOnCircle(const CircleObstacle &circle, const Point &p1, const Point &p2)
Definition helpers_functions.cpp:9
void AddNode(PathWayNode *new_node)
Definition path_graph.h:51
std::vector< std::shared_ptr< PathWayNode > > nodes
Definition path_graph.h:48
void AddEdge(std::size_t node_1, std::size_t node_2, double length)
Definition path_graph.h:78
Here is the call graph for this function:
Here is the caller graph for this function:

◆ AddGraphTangentPoints()

void math::OptimalWayCalculator::AddGraphTangentPoints ( )
private
87 {
88 for (auto& circle : circles_)
89 for (auto& point : circle.GetTangentPoints()) {
90 bool is_unique = true;
91 for (std::size_t i = 0; i < graph_.nodes.size(); ++i) {
92 if (point == graph_.nodes[i]->point) {
93 is_unique = false;
94 break;
95 }
96 }
97 if (is_unique == false) continue;
98 PathWayNode* new_node = new PathWayNode(point, graph_.nodes.size(), true);
99 new_node->circle_ptr = std::make_shared<CircleObstacle>(circle);
100 graph_.AddNode(new_node);
101 for (std::size_t i = 0; i < graph_.nodes.size() - 1; ++i) {
102 if (graph_.nodes[i]->circle_ptr &&
103 ((*graph_.nodes[i]->circle_ptr) == circle)) {
104 graph_.AddEdge(graph_.nodes[i]->number, new_node->number,
106 circle, graph_.nodes[i]->point, new_node->point));
107 } else if (new_node->point ==
108 *graph_.nodes[i]->point.another_tangent_point) {
110 graph_.nodes[i]->number, new_node->number,
111 DistanceBetweenPoints(graph_.nodes[i]->point, new_node->point));
112 }
113 }
114 }
115 for (auto& poly : polys_) {
116 std::vector<Point> vertexes = poly.GetVertexes();
117 for (std::size_t i = 0; i < vertexes.size(); ++i) {
118 PathWayNode* new_node =
119 new PathWayNode(vertexes[i], graph_.nodes.size(), true);
120 for (std::size_t j = 0; j < poly.GetTangentPoints().size(); ++j) {
121 if (poly.GetTangentPoints()[j] == vertexes[i])
122 new_node->point = poly.GetTangentPoints()[j];
123 }
124 new_node->poly_ptr = std::make_shared<PolygonObstacle>(poly);
125 graph_.AddNode(new_node);
126 // Проводим ребра в графе только между соседними вершинами
127 // многоугольника
128 if (i != 0)
130 graph_.nodes[graph_.nodes.size() - 2]->number, new_node->number,
131 DistanceBetweenPoints(graph_.nodes[graph_.nodes.size() - 2]->point,
132 new_node->point));
133 if (i == vertexes.size() - 1)
135 graph_.nodes[graph_.nodes.size() - vertexes.size()]->number,
136 new_node->number,
138 graph_.nodes[graph_.nodes.size() - vertexes.size()]->point,
139 new_node->point));
140 for (auto& tangent_point : poly.GetTangentPoints()) {
141 if (tangent_point != new_node->point) continue;
142 for (auto& node : graph_.nodes) {
143 if (*tangent_point.another_tangent_point != node->point) continue;
144 graph_.AddEdge(node->number, new_node->number,
145 DistanceBetweenPoints(node->point, new_node->point));
146 }
147 }
148 }
149 }
150}
double DistanceBetweenPoints(const Point &first_point, const Point &second_point)
Находит расстояние между двумя мат. точками
Definition point.cpp:27
Here is the call graph for this function:
Here is the caller graph for this function:

◆ AddTangent()

template<typename T , typename U >
template void math::OptimalWayCalculator::AddTangent< PolygonObstacle, PolygonObstacle > ( const LinearFunction & tangent,
T & obstacle1,
U & obstacle2 )
private

Добавляет информацию об общей касательной двух препятствий

Parameters
tangentобщая касательная
obstacle1препятствие 1
obstacle2препятствие 2
39 {
40 std::pair<Point, Point> tangent_points =
41 TangentPoints(tangent, obstacle1, obstacle2);
42 tangent_points.first.another_tangent_point =
43 std::make_shared<Point>(tangent_points.second);
44 tangent_points.second.another_tangent_point =
45 std::make_shared<Point>(tangent_points.first);
46 obstacle1.AddTangentPoint(tangent_points.first);
47 obstacle2.AddTangentPoint(tangent_points.second);
48}
Here is the call graph for this function:

◆ FindOptimalWay()

void math::OptimalWayCalculator::FindOptimalWay ( Point p1,
Point p2 )
201 {
203 std::set<std::size_t> point1_tangents = AddGraphControlPoints(p1);
204 std::set<std::size_t> point2_tangents = AddGraphControlPoints(p2);
205
206 PathWayNode* new_node1 = new PathWayNode(p1, graph_.nodes.size(), false);
207 graph_.AddNode(new_node1);
208 for (const auto& index : point1_tangents) {
210 new_node1->number, graph_.nodes[index]->number,
211 DistanceBetweenPoints(new_node1->point, graph_.nodes[index]->point));
212 }
213 PathWayNode* new_node2 = new PathWayNode(p2, graph_.nodes.size(), false);
214 graph_.AddNode(new_node2);
215 for (const auto& index : point2_tangents) {
217 new_node2->number, graph_.nodes[index]->number,
218 DistanceBetweenPoints(new_node2->point, graph_.nodes[index]->point));
219 }
220
221 if (!TangentGoesThroughOtherObstacle(p1, p2)) {
222 graph_.AddEdge(graph_.nodes.size() - 2, graph_.nodes.size() - 1,
223 DistanceBetweenPoints(p1, p2));
224 }
225
226 DijkstrasAlgorithm da(graph_);
227 optimal_way_ = da.Get_Min_Path();
228 optimal_way_length_ = da.Get_Min_Len();
231}
void MakeTrajectoryPart()
Definition optimal_way.cpp:233
std::vector< std::size_t > optimal_way_
Definition optimal_way.h:49
std::set< std::size_t > AddGraphControlPoints(Point point)
Definition optimal_way.cpp:152
double optimal_way_length_
Definition optimal_way.h:52
void ResetInformation()
Definition optimal_way.cpp:252
void RemoveNonConstantNodes()
Definition path_graph.h:54
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GetGraphNodes()

std::vector< std::shared_ptr< PathWayNode > > math::OptimalWayCalculator::GetGraphNodes ( )
inline
27 {
28 return graph_.nodes;
29 }

◆ GetOptimalWay()

std::vector< std::size_t > math::OptimalWayCalculator::GetOptimalWay ( )
inline
31{ return optimal_way_; }

◆ GetOptimalWayLength()

double math::OptimalWayCalculator::GetOptimalWayLength ( )
inline
33{ return optimal_way_length_; }
Here is the caller graph for this function:

◆ GetTrajectoryPart()

std::vector< lib::Segment > math::OptimalWayCalculator::GetTrajectoryPart ( )
inline
35{ return trajectory_part_; }
std::vector< lib::Segment > trajectory_part_
Definition optimal_way.h:55
Here is the caller graph for this function:

◆ MakeTrajectoryPart()

void math::OptimalWayCalculator::MakeTrajectoryPart ( )
private
233 {
234 for (std::size_t i = 0; i < optimal_way_.size() - 1; ++i) {
235 // Если точки лежат на одной окружности, их следует соединить дугой
236 if ((graph_.nodes[optimal_way_[i]]->circle_ptr) &&
237 (graph_.nodes[optimal_way_[i + 1]]->circle_ptr) &&
238 (*(graph_.nodes[optimal_way_[i]]->circle_ptr) ==
239 *(graph_.nodes[optimal_way_[i + 1]]->circle_ptr))) {
240 trajectory_part_.push_back(
241 Segment(graph_.nodes[optimal_way_[i]]->point,
242 graph_.nodes[optimal_way_[i + 1]]->point,
243 graph_.nodes[optimal_way_[i]]->circle_ptr->GetCenter()));
244 } else {
245 trajectory_part_.push_back(
246 Segment(graph_.nodes[optimal_way_[i]]->point,
247 graph_.nodes[optimal_way_[i + 1]]->point));
248 }
249 }
250}
Сегмент математический траектории
Definition segment.h:12
Here is the caller graph for this function:

◆ ResetInformation()

void math::OptimalWayCalculator::ResetInformation ( )
private
252 {
253 trajectory_part_.clear();
254 for (auto& node : graph_.nodes) node->is_visited = false;
255}
Here is the caller graph for this function:

◆ TangentGoesThroughOtherObstacle() [1/2]

template<typename T , typename U >
bool math::OptimalWayCalculator::TangentGoesThroughOtherObstacle ( const LinearFunction & tangent,
T & obstacle1,
U & obstacle2 )
private

Проверяет, пересекает ли общая касательная двух препятствий другое препятствие

Parameters
tangentобщая касательная
obstacle1номер препятствие 1
obstacle2номер препятствие 2
Returns
bool: результат проверки
13 {
14 std::pair<Point, Point> tangent_points =
15 TangentPoints(tangent, obstacle1, obstacle2);
16 for (std::size_t i = 0; i < circles_.size(); ++i)
17 if (AreThereIntersections(circles_[i], tangent_points.first,
18 tangent_points.second))
19 return true;
20 for (std::size_t i = 0; i < polys_.size(); ++i)
21 if (AreThereIntersections(polys_[i], tangent_points.first,
22 tangent_points.second))
23 return true;
24 return false;
25}
bool AreThereIntersections(const CircleObstacle &cr_obst, const Point &point1, const Point &point2)
Проверяет, пересекает ли отрезок, проведенный через две точки, окружность
Definition helpers_functions.cpp:224
Here is the call graph for this function:
Here is the caller graph for this function:

◆ TangentGoesThroughOtherObstacle() [2/2]

bool math::OptimalWayCalculator::TangentGoesThroughOtherObstacle ( const Point & tangent_point,
const Point & control_point )
private

Проверяет, пересекает ли касательная препятствие

Parameters
tangent_pointточка касания
control_pointконтрольная точка
Returns
результат проверки
28 {
29 for (auto& circle : circles_)
30 if (AreThereIntersections(circle, tangent_point, control_point))
31 return true;
32 for (auto& poly : polys_)
33 if (AreThereIntersections(poly, tangent_point, control_point)) return true;
34 return false;
35}
Here is the call graph for this function:

Member Data Documentation

◆ circles_

std::vector<CircleObstacle> math::OptimalWayCalculator::circles_
private

◆ graph_

PathWayGraph math::OptimalWayCalculator::graph_
private

◆ optimal_way_

std::vector<std::size_t> math::OptimalWayCalculator::optimal_way_
private

◆ optimal_way_length_

double math::OptimalWayCalculator::optimal_way_length_
private

◆ polys_

std::vector<PolygonObstacle> math::OptimalWayCalculator::polys_
private

◆ trajectory_part_

std::vector<lib::Segment> math::OptimalWayCalculator::trajectory_part_
private

The documentation for this class was generated from the following files: