Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include "SphereCalculus.h"
SphereCalculus::SphereCalculus(const SphereCalculus &other, QObject *parent)
: QObject (parent)
{
*this = other;
}
SphereCalculus &SphereCalculus::operator=(const SphereCalculus &other)
{
setEpsilonMeter(other.epsilonMeter());
return *this;
}
void SphereCalculus::setEpsilonMeter(double epsilon)
{
if (epsilon > 0) {
_epsilonMeter = epsilon;
}
}
double SphereCalculus::epsilonMeter() const
{
return _epsilonMeter;
}
/*!
* \fn bool SphereCalculus::dijkstraPath(const QList<QGeoCoordinate> &polygon, const QGeoCoordinate &c1, const QGeoCoordinate &c2, QList<QGeoCoordinate> &dijkstraPath)
* Calculates the shortest path (inside \a polygon) between \a start and \a end.
* The \l {Dijkstra Algorithm} is used to find the shorest path.
* Stores the result inside \a dijkstraPath when sucessfull.
* Stores error messages in \a errorString.
* Returns \c true if successful, \c false else.
*
* \sa QList
*/
SphereCalculus::DijkstraError SphereCalculus::dijkstraPath(const QList<QGeoCoordinate> &polygon, const QGeoCoordinate &start, const QGeoCoordinate &end, QList<QGeoCoordinate> &dijkstraPath)
{
if ( isSimplePolygon(polygon) ) {
return SphereCalculus::DijkstraError::NotSimplePolygon;
}
// Each QGeoCoordinate gets stuff into a Node
/// @param distance is the distance between the Node and it's predecessor
struct Node{
QGeoCoordinate coordinate;
double distance = std::numeric_limits<qreal>::infinity();
Node* predecessorNode = nullptr;
};
// The list with all Nodes (start, end + poly.path())
QList<Node> nodeList;
// This list will be initalized with (pointer to) all elements of nodeList.
// Elements will be successively remove during the execution of the Dijkstra Algorithm.
QList<Node*> workingSet;
// initialize nodeList_maxAltitude
// start cooridnate
Node startNode;
startNode.coordinate = start;
startNode.distance = 0;
nodeList.append(startNode);
//poly cooridnates
for (int i = 0; i < polygon.size(); i++) {
Node node;
node.coordinate = polygon[i];
nodeList.append(node);
}
//end coordinate
Node endNode;
endNode.coordinate = end;
nodeList.append(endNode);
// initialize working set
for (int i = 0; i < nodeList.size(); i++) {
Node* nodePtr = &nodeList[i];
workingSet.append(nodePtr);
}
// Dijkstra Algorithm
// https://de.wikipedia.org/wiki/Dijkstra-Algorithmus
while (workingSet.size() > 0) {
// serach Node with minimal distance
double minDist = std::numeric_limits<qreal>::infinity();
int minDistIndex = 0;
for (int i = 0; i < workingSet.size(); i++) {
Node* node = workingSet.value(i);
double dist = node->distance;
if (dist < minDist) {
minDist = dist;
minDistIndex = i;
}
}
Node* u = workingSet.takeAt(minDistIndex);
//update distance
for (int i = 0; i < workingSet.size(); i++) {
Node* v = workingSet[i];
// is neighbour? dist == infinity if no neihbour
double dist = distanceInsidePolygon(u->coordinate, v->coordinate, polygon);
// is ther a alternative path which is shorter?QList<QGeoCoordinate>
double alternative = u->distance + dist;
if (alternative < v->distance) {
v->distance = alternative;
v->predecessorNode = u;
}
}
}
// end Djikstra Algorithm
// reverse assemble path
Node* Node = &nodeList.last();
while (1) {
dijkstraPath.prepend(Node->coordinate);
//Update Node
Node = Node->predecessorNode;
if (Node == nullptr) {
if (dijkstraPath[0].distanceTo(start) < _epsilonMeter)// check if starting point was reached
break;
qWarning("WimaArea::dijkstraPath(): Error, no path found!\n");
return SphereCalculus::DijkstraError::NoPathFound;
}
}
return SphereCalculus::DijkstraError::PathFound;
}
/*!
\class SphereCalculus
\inmodule Wima
\brief The \c WimaArea class provides the a base class for
all areas used within the Wima extension.
\c WimaArea uses a \l {Simple Polygon} derived from \c {QGCMapPolygon}
to define areas inside which certain taskts are performed. The polygon (often refered to as the path) can
be displayed visually on a map.
*/
/*!
\externalpage https://en.wikipedia.org/wiki/Simple_polygon
\title Simple Polygon
*/
/*!
\externalpage https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
\title Dijkstra Algorithm
*/