Branch data     Line data    Source code

       1                 :            : /***************************************************************************
       2                 :            :                          qgsalgorithmshortestpathlayertopoint.cpp
       3                 :            :                          ---------------------
       4                 :            :     begin                : July 2018
       5                 :            :     copyright            : (C) 2018 by Alexander Bruy
       6                 :            :     email                : alexander dot bruy at gmail dot com
       7                 :            :  ***************************************************************************/
       8                 :            : 
       9                 :            : /***************************************************************************
      10                 :            :  *                                                                         *
      11                 :            :  *   This program is free software; you can redistribute it and/or modify  *
      12                 :            :  *   it under the terms of the GNU General Public License as published by  *
      13                 :            :  *   the Free Software Foundation; either version 2 of the License, or     *
      14                 :            :  *   (at your option) any later version.                                   *
      15                 :            :  *                                                                         *
      16                 :            :  ***************************************************************************/
      17                 :            : 
      18                 :            : #include "qgsalgorithmshortestpathlayertopoint.h"
      19                 :            : 
      20                 :            : #include "qgsgraphanalyzer.h"
      21                 :            : 
      22                 :            : #include "qgsmessagelog.h"
      23                 :            : 
      24                 :            : ///@cond PRIVATE
      25                 :            : 
      26                 :          0 : QString QgsShortestPathLayerToPointAlgorithm::name() const
      27                 :            : {
      28                 :          0 :   return QStringLiteral( "shortestpathlayertopoint" );
      29                 :            : }
      30                 :            : 
      31                 :          0 : QString QgsShortestPathLayerToPointAlgorithm::displayName() const
      32                 :            : {
      33                 :          0 :   return QObject::tr( "Shortest path (layer to point)" );
      34                 :            : }
      35                 :            : 
      36                 :          0 : QStringList QgsShortestPathLayerToPointAlgorithm::tags() const
      37                 :            : {
      38                 :          0 :   return QObject::tr( "network,path,shortest,fastest" ).split( ',' );
      39                 :          0 : }
      40                 :            : 
      41                 :          0 : QString QgsShortestPathLayerToPointAlgorithm::shortHelpString() const
      42                 :            : {
      43                 :          0 :   return QObject::tr( "This algorithm computes optimal (shortest or fastest) route from multiple start points defined by vector layer and given end point." );
      44                 :            : }
      45                 :            : 
      46                 :          0 : QgsShortestPathLayerToPointAlgorithm *QgsShortestPathLayerToPointAlgorithm::createInstance() const
      47                 :            : {
      48                 :          0 :   return new QgsShortestPathLayerToPointAlgorithm();
      49                 :            : }
      50                 :            : 
      51                 :          0 : void QgsShortestPathLayerToPointAlgorithm::initAlgorithm( const QVariantMap & )
      52                 :            : {
      53                 :          0 :   addCommonParams();
      54                 :          0 :   addParameter( new QgsProcessingParameterFeatureSource( QStringLiteral( "START_POINTS" ), QObject::tr( "Vector layer with start points" ), QList< int >() << QgsProcessing::TypeVectorPoint ) );
      55                 :          0 :   addParameter( new QgsProcessingParameterPoint( QStringLiteral( "END_POINT" ), QObject::tr( "End point" ) ) );
      56                 :            : 
      57                 :          0 :   addParameter( new QgsProcessingParameterFeatureSink( QStringLiteral( "OUTPUT" ), QObject::tr( "Shortest path" ), QgsProcessing::TypeVectorLine ) );
      58                 :          0 : }
      59                 :            : 
      60                 :          0 : QVariantMap QgsShortestPathLayerToPointAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
      61                 :            : {
      62                 :          0 :   loadCommonParams( parameters, context, feedback );
      63                 :            : 
      64                 :          0 :   QgsPointXY endPoint = parameterAsPoint( parameters, QStringLiteral( "END_POINT" ), context, mNetwork->sourceCrs() );
      65                 :            : 
      66                 :          0 :   std::unique_ptr< QgsFeatureSource > startPoints( parameterAsSource( parameters, QStringLiteral( "START_POINTS" ), context ) );
      67                 :          0 :   if ( !startPoints )
      68                 :          0 :     throw QgsProcessingException( invalidSourceError( parameters, QStringLiteral( "START_POINTS" ) ) );
      69                 :            : 
      70                 :          0 :   QgsFields fields = startPoints->fields();
      71                 :          0 :   fields.append( QgsField( QStringLiteral( "start" ), QVariant::String ) );
      72                 :          0 :   fields.append( QgsField( QStringLiteral( "end" ), QVariant::String ) );
      73                 :          0 :   fields.append( QgsField( QStringLiteral( "cost" ), QVariant::Double ) );
      74                 :            : 
      75                 :          0 :   QString dest;
      76                 :          0 :   std::unique_ptr< QgsFeatureSink > sink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, dest, fields, QgsWkbTypes::LineString, mNetwork->sourceCrs() ) );
      77                 :          0 :   if ( !sink )
      78                 :          0 :     throw QgsProcessingException( invalidSinkError( parameters, QStringLiteral( "OUTPUT" ) ) );
      79                 :            : 
      80                 :          0 :   QVector< QgsPointXY > points;
      81                 :          0 :   points.push_front( endPoint );
      82                 :          0 :   QHash< int, QgsAttributes > sourceAttributes;
      83                 :          0 :   loadPoints( startPoints.get(), points, sourceAttributes, context, feedback );
      84                 :            : 
      85                 :          0 :   feedback->pushInfo( QObject::tr( "Building graph…" ) );
      86                 :          0 :   QVector< QgsPointXY > snappedPoints;
      87                 :          0 :   mDirector->makeGraph( mBuilder.get(), points, snappedPoints, feedback );
      88                 :            : 
      89                 :          0 :   feedback->pushInfo( QObject::tr( "Calculating shortest paths…" ) );
      90                 :          0 :   QgsGraph *graph = mBuilder->graph();
      91                 :          0 :   int idxEnd = graph->findVertex( snappedPoints[0] );
      92                 :            :   int idxStart;
      93                 :            :   int currentIdx;
      94                 :            : 
      95                 :          0 :   QVector< int > tree;
      96                 :          0 :   QVector< double > costs;
      97                 :            : 
      98                 :          0 :   QVector<QgsPointXY> route;
      99                 :            :   double cost;
     100                 :            : 
     101                 :          0 :   QgsFeature feat;
     102                 :          0 :   feat.setFields( fields );
     103                 :          0 :   QgsAttributes attributes;
     104                 :            : 
     105                 :          0 :   int step =  points.size() > 0 ? 100.0 / points.size() : 1;
     106                 :          0 :   for ( int i = 1; i < points.size(); i++ )
     107                 :            :   {
     108                 :          0 :     if ( feedback->isCanceled() )
     109                 :            :     {
     110                 :          0 :       break;
     111                 :            :     }
     112                 :            : 
     113                 :          0 :     idxStart = graph->findVertex( snappedPoints[i] );
     114                 :          0 :     QgsGraphAnalyzer::dijkstra( graph, idxStart, 0, &tree, &costs );
     115                 :            : 
     116                 :          0 :     if ( tree.at( idxEnd ) == -1 )
     117                 :            :     {
     118                 :          0 :       feedback->reportError( QObject::tr( "There is no route from start point (%1) to end point (%2)." )
     119                 :          0 :                              .arg( points[i].toString(),
     120                 :          0 :                                    endPoint.toString() ) );
     121                 :          0 :       feat.clearGeometry();
     122                 :          0 :       attributes = sourceAttributes.value( i );
     123                 :          0 :       attributes.append( points[i].toString() );
     124                 :          0 :       feat.setAttributes( attributes );
     125                 :          0 :       sink->addFeature( feat, QgsFeatureSink::FastInsert );
     126                 :          0 :       continue;
     127                 :            :     }
     128                 :            : 
     129                 :          0 :     route.clear();
     130                 :          0 :     route.push_front( graph->vertex( idxEnd ).point() );
     131                 :          0 :     cost = costs.at( idxEnd );
     132                 :          0 :     currentIdx = idxEnd;
     133                 :          0 :     while ( currentIdx != idxStart )
     134                 :            :     {
     135                 :          0 :       currentIdx = graph->edge( tree.at( currentIdx ) ).fromVertex();
     136                 :          0 :       route.push_front( graph->vertex( currentIdx ).point() );
     137                 :            :     }
     138                 :            : 
     139                 :          0 :     QgsGeometry geom = QgsGeometry::fromPolylineXY( route );
     140                 :          0 :     QgsFeature feat;
     141                 :          0 :     feat.setFields( fields );
     142                 :          0 :     attributes = sourceAttributes.value( i );
     143                 :          0 :     attributes.append( points[i].toString() );
     144                 :          0 :     attributes.append( endPoint.toString() );
     145                 :          0 :     attributes.append( cost / mMultiplier );
     146                 :          0 :     feat.setAttributes( attributes );
     147                 :          0 :     feat.setGeometry( geom );
     148                 :          0 :     sink->addFeature( feat, QgsFeatureSink::FastInsert );
     149                 :            : 
     150                 :          0 :     feedback->setProgress( i * step );
     151                 :          0 :   }
     152                 :            : 
     153                 :          0 :   QVariantMap outputs;
     154                 :          0 :   outputs.insert( QStringLiteral( "OUTPUT" ), dest );
     155                 :          0 :   return outputs;
     156                 :          0 : }
     157                 :            : 
     158                 :            : ///@endcond