SphereCalculus.cc

#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
*/