PolygonCalculus.cc 22.4 KB
Newer Older
1
#include "PolygonCalculus.h"
2
#include "PlanimetryCalculus.h"
3
#include "Wima/OptimisationTools.h"
4 5 6 7

#include <QVector3D>

#include <functional>
8

9 10
namespace PolygonCalculus {
    namespace  {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
11 12 13 14 15 16 17 18
        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;
        }
19 20 21

    } // end anonymous namespace

Valentin Platzgummer's avatar
Valentin Platzgummer committed
22 23 24 25 26 27 28 29
    /*!
     * \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)
    {
30

Valentin Platzgummer's avatar
Valentin Platzgummer committed
31 32 33 34 35
        if ( !polygon.isEmpty()) {
            if (   !polygon.containsPoint(c1, Qt::FillRule::OddEvenFill)
                || !polygon.containsPoint(c2, Qt::FillRule::OddEvenFill))
                return false;

36 37 38
            QLineF line(c1, c2);
            if (PlanimetryCalculus::intersectsFast(polygon, line))
                return false;
Valentin Platzgummer's avatar
Valentin Platzgummer committed
39 40 41 42 43 44
            return true;
        } else {
            return false;
        }
    }

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
    /*!
     * \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;
        }
    }

72
    /*!auto distance
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
     * \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()
     */
Valentin Platzgummer's avatar
Valentin Platzgummer committed
94
    int nextVertexIndex(int pathsize, int index)
95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
    {
        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()
     */
Valentin Platzgummer's avatar
Valentin Platzgummer committed
112
    int previousVertexIndex(int pathsize, int index)
113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133
    {
        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.
     */
134
    JoinPolygonError join(QPolygonF polygon1, QPolygonF polygon2, QPolygonF &joinedPolygon)
135
    {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
136
        using namespace PlanimetryCalculus;
137 138 139 140 141
        if (polygon1.size() >= 3 && polygon2.size() >= 3) {

            if ( !isSimplePolygon(polygon1) || !isSimplePolygon(polygon2)) {
                return JoinPolygonError::NotSimplePolygon;
            }
142 143 144 145 146

            if (polygon1 == polygon2) {
                joinedPolygon = polygon1;
                return JoinPolygonError::PolygonJoined;
            }
147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162
            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++) {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
163
                if ( !contains(*crossPoly, walkerPoly->at(i)) ) {
164 165 166 167 168 169 170 171 172 173
                    crossContainsWalker = false;
                    startIndex = i;
                    break;
                }
            }

            if ( crossContainsWalker == true) {
                joinedPolygon.append(*crossPoly);
                return JoinPolygonError::PolygonJoined;
            }
Valentin Platzgummer's avatar
Valentin Platzgummer committed
174
            QPointF currentVertex    = walkerPoly->at(startIndex);
175 176
            QPointF startVertex      = currentVertex;
            // possible nextVertex (if no intersection between currentVertex and protoVertex with crossPoly)
Valentin Platzgummer's avatar
Valentin Platzgummer committed
177
            int nextVertexNumber     = nextVertexIndex(walkerPoly->size(), startIndex);
178
            QPointF protoNextVertex  = walkerPoly->value(nextVertexNumber);
179
            long counter = 0;
180
            while (1) {
181
                //qDebug("nextVertexNumber: %i", nextVertexNumber);
182 183 184 185 186 187
                joinedPolygon.append(currentVertex);

                QLineF walkerPolySegment;
                walkerPolySegment.setP1(currentVertex);
                walkerPolySegment.setP2(protoNextVertex);

188 189
                QVector<QPair<int, int>> neighbourList;
                QVector<QPointF> intersectionList;
190 191 192 193 194
                //qDebug("IntersectionList.size() on init: %i", intersectionList.size());
                PlanimetryCalculus::intersects(*crossPoly, walkerPolySegment, intersectionList, neighbourList);

                //qDebug("IntersectionList.size(): %i", intersectionList.size());

Valentin Platzgummer's avatar
Valentin Platzgummer committed
195 196
                if (intersectionList.size() > 0) {
                    int minDistIndex = -1;
197

Valentin Platzgummer's avatar
Valentin Platzgummer committed
198 199 200
                    double minDist = std::numeric_limits<double>::infinity();
                    for (int i = 0; i < intersectionList.size(); i++) {
                        double currentDist = PlanimetryCalculus::distance(currentVertex, intersectionList[i]);
201

Valentin Platzgummer's avatar
Valentin Platzgummer committed
202
                        if ( minDist > currentDist && !qFuzzyIsNull(distance(currentVertex, intersectionList[i])) ) {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
203 204
                            minDist         = currentDist;
                            minDistIndex    = i;
205 206 207
                        }
                    }

Valentin Platzgummer's avatar
Valentin Platzgummer committed
208 209
                    if (minDistIndex != -1){
                        currentVertex                   = intersectionList.value(minDistIndex);
210 211
                        QPair<int, int> neighbours      = neighbourList.value(minDistIndex);
                        protoNextVertex                 = crossPoly->value(neighbours.second);
212
                        nextVertexNumber                 = neighbours.second;
213 214 215 216 217 218

                        // switch walker and cross poly
                        const QPolygonF *temp   = walkerPoly;
                        walkerPoly              = crossPoly;
                        crossPoly               = temp;
                    } else {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
219
                        currentVertex    = walkerPoly->value(nextVertexNumber);
220
                        nextVertexNumber = nextVertexIndex(walkerPoly->size(), nextVertexNumber);
Valentin Platzgummer's avatar
Valentin Platzgummer committed
221
                        protoNextVertex  = walkerPoly->value(nextVertexNumber);
222 223 224
                    }

                } else {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
225
                    currentVertex    = walkerPoly->value(nextVertexNumber);
226
                    nextVertexNumber = nextVertexIndex(walkerPoly->size(), nextVertexNumber);
Valentin Platzgummer's avatar
Valentin Platzgummer committed
227
                    protoNextVertex  = walkerPoly->value(nextVertexNumber);
228 229 230 231
                }

                if (currentVertex == startVertex) {
                    if (polygon1.size() == joinedPolygon.size()) {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
232 233 234 235 236
                        for (int i = 0; i < polygon1.size(); i++) {
                            if (polygon1[i] != joinedPolygon[i])
                                return PolygonJoined;
                        }
                        return Disjoint;
237
                    } else {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
238
                        return PolygonJoined;
239 240
                    }
                }
241 242 243 244 245 246

                counter++;
                if (counter > 1e5) {
                    qWarning("PolygonCalculus::join(): no successfull termination!");
                    return Error;
                }
247 248 249
            }

        } else {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
250
            return PathSizeLow;
251 252 253 254 255 256 257 258 259 260 261 262 263 264
        }
    }

    /*!
     * \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) {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
265
                double cCIntersectCounter = 0; // corner corner intersection counter
266
                QPointF refBeginCoordinate = polygon[i];
Valentin Platzgummer's avatar
Valentin Platzgummer committed
267
                QPointF refEndCoordinate = polygon[nextVertexIndex(polygon.size(), i)];
268 269 270
                QLineF refLine;
                refLine.setP1(refBeginCoordinate);
                refLine.setP2(refEndCoordinate);
Valentin Platzgummer's avatar
Valentin Platzgummer committed
271
                int j = nextVertexIndex(polygon.size(), i);
272 273 274 275 276
                while(j < polygon.size()) {

                    QPointF intersectionPt;
                    QLineF iteratorLine;
                    iteratorLine.setP1(polygon[j]);
Valentin Platzgummer's avatar
Valentin Platzgummer committed
277 278 279 280 281 282 283 284 285 286 287 288 289
                    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;
290
                    }
Valentin Platzgummer's avatar
Valentin Platzgummer committed
291

292 293 294 295 296 297 298 299 300 301
                    j++;
                }
                i++;
            }
        }
        return true;
    }

    /*!
     * \fn bool hasClockwiseWinding(const QPolygonF &polygon)
302
     * Returns \c true if \a path has clockwiauto distancese winding, \c false else.
303 304 305 306 307 308 309 310 311 312
     */
    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];
Valentin Platzgummer's avatar
Valentin Platzgummer committed
313
            QPointF coord2 = polygon[nextVertexIndex(polygon.size(), i)];
314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337

            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);
    }

Valentin Platzgummer's avatar
Valentin Platzgummer committed
338 339 340 341 342
    /*!
     * \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)
343
    {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
344 345 346 347
        // Original code from QGCMapPolygon::offset()
        QPolygonF newPolygon;
        if (polygon.size() > 2) {

348
            // Walk the edges, offsetting by theauto distance specified distance
Valentin Platzgummer's avatar
Valentin Platzgummer committed
349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366
            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;
            }
367

Valentin Platzgummer's avatar
Valentin Platzgummer committed
368 369 370 371 372 373 374 375 376 377 378 379 380
            // 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);
            }
        }
381 382
    }

Valentin Platzgummer's avatar
Valentin Platzgummer committed
383
    void decomposeToConvex(const QPolygonF &polygon, QList<QPolygonF> &convexPolygons)
384
    {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
385 386 387 388 389 390 391 392
        // 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;
        }
393

Valentin Platzgummer's avatar
Valentin Platzgummer committed
394 395 396 397 398 399 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
        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);
449

Valentin Platzgummer's avatar
Valentin Platzgummer committed
450 451 452 453 454 455 456 457 458 459 460 461 462 463 464
                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;
                }
465
            }
Valentin Platzgummer's avatar
Valentin Platzgummer committed
466 467 468 469 470
        }

        // assemble output
        if (decomposedPolygonsMin.size() > 0) {
            convexPolygons << decomposedPolygonsMin;
471
        } else {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
472
            convexPolygons << polygon;
473
        }
Valentin Platzgummer's avatar
Valentin Platzgummer committed
474 475

        return;
476
    }
Valentin Platzgummer's avatar
Valentin Platzgummer committed
477

478
    bool shortestPath(const QPolygonF &polygon,const QPointF &startVertex, const QPointF &endVertex, QVector<QPointF> &shortestPath)
Valentin Platzgummer's avatar
Valentin Platzgummer committed
479
    {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
480
        using namespace PlanimetryCalculus;
481
        QPolygonF bigPolygon(polygon);
482
        offsetPolygon(bigPolygon, 0.5); // solves numerical errors
483 484
        if (    bigPolygon.containsPoint(startVertex, Qt::FillRule::OddEvenFill)
             && bigPolygon.containsPoint(endVertex, Qt::FillRule::OddEvenFill)) {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
485 486 487 488 489 490 491 492

            QVector<QPointF> elementList;
            elementList.append(startVertex);
            elementList.append(endVertex);
            for (auto vertex : polygon)  elementList.append(vertex);
            const int listSize = elementList.size();


493
            std::function<double(const int, const int)> distanceDij = [bigPolygon, elementList](const int ind1,  const int ind2) -> double {
Valentin Platzgummer's avatar
Valentin Platzgummer committed
494 495 496
                QPointF p1 = elementList[ind1];
                QPointF p2 = elementList[ind2];
                double dist = std::numeric_limits<double>::infinity();
497
                if (containsPathFast(bigPolygon, p1, p2)){ // containsPathFast can be used since all points are inside bigPolygon
Valentin Platzgummer's avatar
Valentin Platzgummer committed
498 499
                    double dx = p1.x()-p2.x();
                    double dy = p1.y()-p2.y();
500
                    dist =  sqrt((dx*dx)+(dy*dy));
Valentin Platzgummer's avatar
Valentin Platzgummer committed
501 502 503
                }

                return dist;
Valentin Platzgummer's avatar
Valentin Platzgummer committed
504 505
            };

Valentin Platzgummer's avatar
Valentin Platzgummer committed
506 507 508 509
            QVector<int> shortestPathIndex;
            bool retVal = OptimisationTools::dijkstraAlgorithm(listSize, 0, 1, shortestPathIndex, distanceDij);
            for (auto index : shortestPathIndex) shortestPath.append(elementList[index]);
            return retVal;
Valentin Platzgummer's avatar
Valentin Platzgummer committed
510 511 512 513 514
        } else {
            return false;
        }
    }

515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541
    QVector3DList toQVector3DList(const QPolygonF &polygon)
    {
        QVector3DList list;
        for ( auto vertex : polygon )
            list.append(QVector3D(vertex));

        return list;
    }

    QPolygonF toQPolygonF(const QPointFList &listF)
    {
        QPolygonF polygon;
        for ( auto vertex : listF )
            polygon.append(vertex);

        return polygon;
    }

    QPointFList toQPointFList(const QPolygonF &polygon)
    {
        QPointFList listF;
        for ( auto vertex : polygon )
            listF.append(vertex);

        return listF;
    }

542 543 544 545 546 547
    void reversePath(QPointFList &path)
    {
        QPointFList pathReversed;
        for ( auto element : path) {
            pathReversed.prepend(element);
        }
548
        path = pathReversed;
549 550
    }

551 552 553 554 555 556 557 558 559 560
    void reversePath(QPointFVector &path)
    {
        QPointFVector pathReversed;
        for ( auto element : path) {
            pathReversed.prepend(element);
        }
        path = pathReversed;
    }


Valentin Platzgummer's avatar
Valentin Platzgummer committed
561

562 563 564 565 566 567 568 569 570 571 572 573 574 575 576
    bool containsPathFast(QPolygonF polygon, const QPointF &c1, const QPointF &c2)
    {

        if ( !polygon.isEmpty()) {
            QLineF line(c1, c2);
            if (PlanimetryCalculus::intersectsFast(polygon, line))
                return false;
            return true;
        } else {
            return false;
        }
    }



577 578
} // end PolygonCalculus namespace