Newer
Older
#include "PolygonCalculus.h"
namespace PolygonCalculus {
namespace {
bool isReflexVertex(const QPolygonF& polygon, const QPointF *vertex) {
// Original Code from SurveyComplexItem::_VertexIsReflex()
auto vertexBefore = vertex == polygon.begin() ? polygon.end() - 1 : vertex - 1;
auto vertexAfter = vertex == polygon.end() - 1 ? polygon.begin() : vertex + 1;
auto area = ( ((vertex->x() - vertexBefore->x())*(vertexAfter->y() - vertexBefore->y()))
-((vertexAfter->x() - vertexBefore->x())*(vertex->y() - vertexBefore->y())));
return area > 0;
}
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
/*!
* \fn bool containsPath(QPolygonF polygon, const QPointF &c1, const QPointF &c2)
* Returns true if the shortest path between the two coordinates is not fully inside the \a area.
*
* \sa QPointF, QPolygonF
*/
bool containsPath(QPolygonF polygon, const QPointF &c1, const QPointF &c2)
{
if ( !polygon.isEmpty()) {
if ( !polygon.containsPoint(c1, Qt::FillRule::OddEvenFill)
|| !polygon.containsPoint(c2, Qt::FillRule::OddEvenFill))
return false;
QList<QPointF> intersectionList;
QLineF line;
line.setP1(c1);
line.setP2(c2);
PlanimetryCalculus::IntersectList intersectTypeList;
bool retValue = PlanimetryCalculus::intersects(polygon, line, intersectionList, intersectTypeList);
if (!retValue) {
for (int i = 0; i < intersectTypeList.size(); i++) {
PlanimetryCalculus::IntersectType type = intersectTypeList[i];
if ( type == PlanimetryCalculus::EdgeEdgeIntersection
|| type == PlanimetryCalculus::Error)
return false;
}
}
return true;
} else {
return false;
}
}
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
/*!
* \fn int closestVertexIndex(const QPolygonF &polygon, const QPointF &coordinate)
* Returns the vertex index of \a polygon which has the least distance to \a coordinate.
*
* \sa QPointF, QPolygonF
*/
int closestVertexIndex(const QPolygonF &polygon, const QPointF &coordinate)
{
if (polygon.size() == 0) {
qWarning("Path is empty!");
return -1;
}else if (polygon.size() == 1) {
return 0;
}else {
int index = 0; // the index of the closest vertex
double min_dist = PlanimetryCalculus::distance(coordinate, polygon[index]);
for(int i = 1; i < polygon.size(); i++){
double dist = PlanimetryCalculus::distance(coordinate, polygon[i]);
if (dist < min_dist){
min_dist = dist;
index = i;
}
}
return index;
}
}
/*!
* \fn QPointF closestVertex(const QPolygonF &polygon, const QPointF &coordinate);
* Returns the vertex of \a polygon with the least distance to \a coordinate.
*
* \sa QPointF, QPolygonF
*/
QPointF closestVertex(const QPolygonF &polygon, const QPointF &coordinate)
{
int index = closestVertexIndex(polygon, coordinate);
if (index >=0 ) {
return polygon[index];
} else {
return QPointF();
}
}
/*!
* \fn int nextPolygonIndex(int pathsize, int index)
* Returns the index of the next vertex (of a polygon), which is \a index + 1 if \a index is smaller than \c {\a pathsize - 1},
* or 0 if \a index equals \c {\a pathsize - 1}, or -1 if the \a index is out of bounds.
* \note \a pathsize is usually obtained by invoking polygon.size()
*/
{
if (index >= 0 && index < pathsize-1) {
return index + 1;
} else if (index == pathsize-1) {
return 0;
} else {
qWarning("nextPolygonIndex(): Index out of bounds! index:count = %i:%i", index, pathsize);
return -1;
}
}
/*!
* \fn int previousPolygonIndex(int pathsize, int index)
* Returns the index of the previous vertex (of a polygon), which is \a index - 1 if \a index is larger 0,
* or \c {\a pathsize - 1} if \a index equals 0, or -1 if the \a index is out of bounds.
* \note pathsize is usually obtained by invoking polygon.size()
*/
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
175
176
177
{
if (index > 0 && index <pathsize) {
return index - 1;
} else if (index == 0) {
return pathsize-1;
} else {
qWarning("previousVertexIndex(): Index out of bounds! index:count = %i:%i", index, pathsize);
return -1;
}
}
/*!
* \fn JoinPolygonError joinPolygon(QPolygonF polygon1, QPolygonF polygon2, QPolygonF &joinedPolygon);
* Joins \a polygon1 and \a polygon2 such that a \l {Simple Polygon} is created.
* Stores the result inside \a joinedArea.
* Returns \c NotSimplePolygon1 if \a polygon1 isn't a Simple Polygon, \c NotSimplePolygon2 if \a polygon2 isn't a Simple Polygon, \c Disjoind if the polygons are disjoint,
* \c PathSizeLow if at least one polygon has a size samler than 3, or \c PolygonJoined on success.
* The algorithm will be able to join the areas, if either their edges intersect with each other,
* or one area is inside the other.
* The algorithm assumes that \a joinedPolygon is empty.
*/
JoinPolygonError joinPolygon(QPolygonF polygon1, QPolygonF polygon2, QPolygonF &joinedPolygon)
{
if (polygon1.size() >= 3 && polygon2.size() >= 3) {
if ( !isSimplePolygon(polygon1) || !isSimplePolygon(polygon2)) {
return JoinPolygonError::NotSimplePolygon;
}
if ( !hasClockwiseWinding(polygon1)) {
reversePath(polygon1);
}
if ( !hasClockwiseWinding(polygon2)) {
reversePath(polygon2);
}
const QPolygonF *walkerPoly = &polygon1; // "walk" on this polygon towards higher indices
const QPolygonF *crossPoly = &polygon2; // check for crossings with this polygon while "walking"
// and swicht to this polygon on a intersection,
// continue to walk towards higher indices
// begin with the first index which is not inside crosspoly, if all Vertices are inside crosspoly return crosspoly
int startIndex = 0;
bool crossContainsWalker = true;
for (int i = 0; i < walkerPoly->size(); i++) {
if ( !crossPoly->contains(walkerPoly->value(i)) ) {
crossContainsWalker = false;
startIndex = i;
break;
}
}
if ( crossContainsWalker == true) {
joinedPolygon.append(*crossPoly);
return JoinPolygonError::PolygonJoined;
}
QPointF currentVertex = walkerPoly->value(startIndex);
QPointF startVertex = currentVertex;
// possible nextVertex (if no intersection between currentVertex and protoVertex with crossPoly)
int nextVertexNumber = nextVertexIndex(walkerPoly->size(), startIndex);
QPointF protoNextVertex = walkerPoly->value(nextVertexNumber);
bool switchHappenedPreviously = false; // means switch between crossPoly and walkerPoly
while (1) {
//qDebug("nextVertexNumber: %i", nextVertexNumber);
joinedPolygon.append(currentVertex);
QLineF walkerPolySegment;
walkerPolySegment.setP1(currentVertex);
walkerPolySegment.setP2(protoNextVertex);
QList<QPair<int, int>> neighbourList;
QList<QPointF> intersectionList;
//qDebug("IntersectionList.size() on init: %i", intersectionList.size());
PlanimetryCalculus::intersects(*crossPoly, walkerPolySegment, intersectionList, neighbourList);
//qDebug("IntersectionList.size(): %i", intersectionList.size());
if (intersectionList.size() >= 1) { bool containsPath (const QPointF &c1, const QPointF &c2, QPolygonF polygon);
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
int minDistIndex = 0;
// find the vertex with the least distance to currentVertex
if (intersectionList.size() > 1) {
double minDist = PlanimetryCalculus::distance(currentVertex, intersectionList[minDistIndex]);
for (int i = 1; i < intersectionList.size(); i++) {
double currentDist = PlanimetryCalculus::distance(currentVertex, intersectionList[i]);
if ( minDist > currentDist ) {
minDist = currentDist;
minDistIndex = i;
}
}
}
//qDebug("MinDistIndex: %i", minDistIndex);
QPointF protoCurrentVertex = intersectionList.value(minDistIndex);
// If the currentVertex is a intersection point a intersection ocisSelfIntersectingcures with the
// crossPoly. This would cause unwanted switching of crossPoly and walkerPoly, thus intersections
// are only token in to account if they occur beyond a certain distance (_epsilonMeter) or no switching happend in the
// previous step.
if (switchHappenedPreviously == false){
//|| protoCurrentVertex.distanceTo(currentVertex) > _epsilonMeter) {
currentVertex = protoCurrentVertex;
QPair<int, int> neighbours = neighbourList.value(minDistIndex);
protoNextVertex = crossPoly->value(neighbours.second);
nextVertexNumber = neighbours.second;
// switch walker and cross poly
const QPolygonF *temp = walkerPoly;
walkerPoly = crossPoly;
crossPoly = temp;
switchHappenedPreviously = true;
} else {
currentVertex = walkerPoly->value(nextVertexNumber);
nextVertexNumber = nextVertexIndex(walkerPoly->size(), nextVertexNumber);
protoNextVertex = walkerPoly->value(nextVertexNumber);
switchHappenedPreviously = false;
}
} else {
currentVertex = walkerPoly->value(nextVertexNumber);
nextVertexNumber = nextVertexIndex(walkerPoly->size(), nextVertexNumber);
protoNextVertex = walkerPoly->value(nextVertexNumber);
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
}
if (currentVertex == startVertex) {
if (polygon1.size() == joinedPolygon.size()) {
return JoinPolygonError::Disjoint;
} else {
return JoinPolygonError::PolygonJoined;
}
}
}
} else {
return JoinPolygonError::PathSizeLow;
}
}
/*!
* \fn bool isSimplePolygon(const QPolygonF &polygon);
* Returns \c true if \a polygon is a \l {Simple Polygon}, \c false else.
* \note A polygon is a Simple Polygon iff it is not self intersecting.
*/
bool isSimplePolygon(const QPolygonF &polygon)
{
int i = 0;
if (polygon.size() > 3) {
// check if any edge of the area (formed by two adjacent vertices) intersects with any other edge of the area
while(i < polygon.size()-1) {
double cCIntersectCounter = 0; // corner corner intersection counter
QPointF refBeginCoordinate = polygon[i];
QPointF refEndCoordinate = polygon[nextVertexIndex(polygon.size(), i)];
QLineF refLine;
refLine.setP1(refBeginCoordinate);
refLine.setP2(refEndCoordinate);
while(j < polygon.size()) {
QPointF intersectionPt;
QLineF iteratorLine;
iteratorLine.setP1(polygon[j]);
iteratorLine.setP2(polygon[nextVertexIndex(polygon.size(), j)]);
PlanimetryCalculus::IntersectType intersectType;
PlanimetryCalculus::intersects(refLine, iteratorLine, intersectionPt, intersectType);
if ( intersectType == PlanimetryCalculus::CornerCornerIntersection) {
cCIntersectCounter++;
// max two corner corner intersections allowed, a specific coordinate can appear only once in a simple polygon
}
if ( cCIntersectCounter > 2
|| intersectType == PlanimetryCalculus::EdgeEdgeIntersection
|| intersectType == PlanimetryCalculus::EdgeCornerIntersection
|| intersectType == PlanimetryCalculus::LinesEqual
|| intersectType == PlanimetryCalculus::Error){
return false;
j++;
}
i++;
}
}
return true;
}
/*!
* \fn bool hasClockwiseWinding(const QPolygonF &polygon)
* Returns \c true if \a path has clockwise winding, \c false else.
*/
bool hasClockwiseWinding(const QPolygonF &polygon)
{
if (polygon.size() <= 2) {
return false;
}
double sum = 0;
for (int i=0; i <polygon.size(); i++) {
QPointF coord1 = polygon[i];
QPointF coord2 = polygon[nextVertexIndex(polygon.size(), i)];
sum += (coord2.x() - coord1.x()) * (coord2.y() + coord1.y());
}
if (sum < 0.0)
return false;
return true;
}
/*!
* \fn void reversePath(QPolygonF &polygon)
* Reverses the path, i.e. changes the first Vertex with the last, the second with the befor last and so forth.
*/
void reversePath(QPolygonF &polygon)
{
QPolygonF pathReversed;
for (int i = 0; i < polygon.size(); i++) {
pathReversed.prepend(polygon[i]);
}
polygon.clear();
polygon.append(pathReversed);
}
/*!
* \fn void offsetPolygon(QPolygonF &polygon, double offset)
* Offsets a \a polygon by the given \a offset. The algorithm assumes that polygon is a \l {SimplePolygon}.
*/
void offsetPolygon(QPolygonF &polygon, double offset)
// Original code from QGCMapPolygon::offset()
QPolygonF newPolygon;
if (polygon.size() > 2) {
// Walk the edges, offsetting by the specified distance
QList<QLineF> rgOffsetEdges;
for (int i = 0; i < polygon.size(); i++) {
int nextIndex = nextVertexIndex(polygon.size(), i);
QLineF offsetEdge;
QLineF originalEdge(polygon[i], polygon[nextIndex]);
QLineF workerLine = originalEdge;
workerLine.setLength(offset);
workerLine.setAngle(workerLine.angle() - 90.0);
offsetEdge.setP1(workerLine.p2());
workerLine.setPoints(originalEdge.p2(), originalEdge.p1()); bool containsPath (const QPointF &c1, const QPointF &c2, QPolygonF polygon);
workerLine.setLength(offset);
workerLine.setAngle(workerLine.angle() + 90.0);
offsetEdge.setP2(workerLine.p2());
rgOffsetEdges << offsetEdge;
}
// Intersect the offset edges to generate new vertices
polygon.clear();
QPointF newVertex;
for (int i=0; i<rgOffsetEdges.count(); i++) {
int prevIndex = previousVertexIndex(rgOffsetEdges.size(), i);
if (rgOffsetEdges[prevIndex].intersect(rgOffsetEdges[i], &newVertex) == QLineF::NoIntersection) {
// FIXME: Better error handling?
qWarning("Intersection failed");
return;
}
polygon.append(newVertex);
}
}
void decomposeToConvex(const QPolygonF &polygon, QList<QPolygonF> &convexPolygons)
// Original Code SurveyComplexItem::_PolygonDecomposeConvex()
// this follows "Mark Keil's Algorithm" https://mpen.ca/406/keil
int decompSize = std::numeric_limits<int>::max();
if (polygon.size() < 3) return;
if (polygon.size() == 3) {
convexPolygons << polygon;
return;
}
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
QList<QPolygonF> decomposedPolygonsMin{};
for (const QPointF *vertex = polygon.begin(); vertex != polygon.end(); ++vertex)
{
// is vertex reflex?
bool vertexIsReflex = isReflexVertex(polygon, vertex);
if (!vertexIsReflex) continue;
for (const QPointF *vertexOther = polygon.begin(); vertexOther != polygon.end(); ++vertexOther)
{
const QPointF *vertexBefore = vertex == polygon.begin() ? polygon.end() - 1 : vertex - 1;
const QPointF *vertexAfter = vertex == polygon.end() - 1 ? polygon.begin() : vertex + 1;
if (vertexOther == vertex) continue;
if (vertexAfter == vertexOther) continue;
if (vertexBefore == vertexOther) continue;
bool canSee = containsPath(polygon, *vertex, *vertexOther);
if (!canSee) continue;
QPolygonF polyLeft;
const QPointF *v = vertex;
bool polyLeftContainsReflex = false;
while ( v != vertexOther) {
if (v != vertex && isReflexVertex(polygon, v)) {
polyLeftContainsReflex = true;
}
polyLeft << *v;
++v;
if (v == polygon.end()) v = polygon.begin();
}
polyLeft << *vertexOther;
bool polyLeftValid = !(polyLeftContainsReflex && polyLeft.size() == 3);
QPolygonF polyRight;
v = vertexOther;
bool polyRightContainsReflex = false;
while ( v != vertex) {
if (v != vertex && isReflexVertex(polygon, v)) {
polyRightContainsReflex = true;
}
polyRight << *v;
++v;
if (v == polygon.end()) v = polygon.begin();
}
polyRight << *vertex;
auto polyRightValid = !(polyRightContainsReflex && polyRight.size() == 3);
if (!polyLeftValid || ! polyRightValid) {
// decompSize = std::numeric_limits<int>::max();
continue;
}
// recursion
QList<QPolygonF> polyLeftDecomposed{};
decomposeToConvex(polyLeft, polyLeftDecomposed);
QList<QPolygonF> polyRightDecomposed{};
decomposeToConvex(polyRight, polyRightDecomposed);
// compositon
int subSize = polyLeftDecomposed.size() + polyRightDecomposed.size();
if ( (polyLeftContainsReflex && polyLeftDecomposed.size() == 1)
|| (polyRightContainsReflex && polyRightDecomposed.size() == 1))
{
// don't accept polygons that contian reflex vertices and were not split
subSize = std::numeric_limits<int>::max();
}
if (subSize < decompSize) {
decompSize = subSize;
decomposedPolygonsMin = polyLeftDecomposed + polyRightDecomposed;
}
}
// assemble output
if (decomposedPolygonsMin.size() > 0) {
convexPolygons << decomposedPolygonsMin;
bool shortestPath(const QPolygonF &polygon, const QPointF &startVertex, const QPointF &endVertex, QList<QPointF> &shortestPath)
{
if ( polygon.containsPoint(startVertex, Qt::FillRule::OddEvenFill)
&& polygon.containsPoint(endVertex, Qt::FillRule::OddEvenFill)) {
// lambda
auto distance = [polygon](const QPointF &p1, const QPointF &p2) -> double {
if (containsPath(polygon, p1, p2)){
double dx = p1.x()-p2.x();
double dy = p1.y()-p2.y();
return sqrt(dx*dx+dy*dy);
} else
return std::numeric_limits<double>::infinity();
};
QList<QPointF> elementList;
elementList.append(startVertex);
elementList.append(endVertex);
for (int i = 0; i < polygon.size(); i++) {
elementList.append(polygon[i]);
}
return OptimisationTools::dijkstraAlgorithm<QPointF>(elementList, 0, 1, shortestPath, distance);
} // end PolygonCalculus namespace