Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
[processing] port service area (from point) alg to c++
  • Loading branch information
alexbruy committed Nov 6, 2019
1 parent 1c1ceb1 commit 5970d1c
Show file tree
Hide file tree
Showing 5 changed files with 299 additions and 2 deletions.
4 changes: 2 additions & 2 deletions python/plugins/processing/algs/qgis/QgisAlgorithmProvider.py
Expand Up @@ -113,7 +113,7 @@
from .SelectByAttribute import SelectByAttribute
from .SelectByExpression import SelectByExpression
from .ServiceAreaFromLayer import ServiceAreaFromLayer
from .ServiceAreaFromPoint import ServiceAreaFromPoint
#from .ServiceAreaFromPoint import ServiceAreaFromPoint
from .SetMValue import SetMValue
from .SetRasterStyle import SetRasterStyle
from .SetVectorStyle import SetVectorStyle
Expand Down Expand Up @@ -222,7 +222,7 @@ def getAlgs(self):
SelectByAttribute(),
SelectByExpression(),
ServiceAreaFromLayer(),
ServiceAreaFromPoint(),
#ServiceAreaFromPoint(),
SetMValue(),
SetRasterStyle(),
SetVectorStyle(),
Expand Down
1 change: 1 addition & 0 deletions src/analysis/CMakeLists.txt
Expand Up @@ -100,6 +100,7 @@ SET(QGIS_ANALYSIS_SRCS
processing/qgsalgorithmrotate.cpp
processing/qgsalgorithmsaveselectedfeatures.cpp
processing/qgsalgorithmsegmentize.cpp
processing/qgsalgorithmserviceareafrompoint.cpp
processing/qgsalgorithmshortestpathlayertopoint.cpp
processing/qgsalgorithmshortestpathpointtolayer.cpp
processing/qgsalgorithmshortestpathpointtopoint.cpp
Expand Down
241 changes: 241 additions & 0 deletions src/analysis/processing/qgsalgorithmserviceareafrompoint.cpp
@@ -0,0 +1,241 @@
/***************************************************************************
qgsalgorithmserviceareafrompoint.cpp
---------------------
begin : July 2018
copyright : (C) 2018 by Alexander Bruy
email : alexander dot bruy at gmail dot com
***************************************************************************/

/***************************************************************************
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
***************************************************************************/

#include "qgsalgorithmserviceareafrompoint.h"

#include "qgsgeometryutils.h"
#include "qgsgraphanalyzer.h"

///@cond PRIVATE

QString QgsServiceAreaFromPointAlgorithm::name() const
{
return QStringLiteral( "serviceareafrompoint" );
}

QString QgsServiceAreaFromPointAlgorithm::displayName() const
{
return QObject::tr( "Service area (from point)" );
}

QStringList QgsServiceAreaFromPointAlgorithm::tags() const
{
return QObject::tr( "network,service,area,shortest,fastest" ).split( ',' );
}

QString QgsServiceAreaFromPointAlgorithm::shortHelpString() const
{
return QObject::tr( "This algorithm computes service area from given start point using travel time or distance." );
}

QgsServiceAreaFromPointAlgorithm *QgsServiceAreaFromPointAlgorithm::createInstance() const
{
return new QgsServiceAreaFromPointAlgorithm();
}

void QgsServiceAreaFromPointAlgorithm::initAlgorithm( const QVariantMap & )
{
addCommonParams();
addParameter( new QgsProcessingParameterPoint( QStringLiteral( "START_POINT" ), QObject::tr( "Start point" ) ) );
addParameter( new QgsProcessingParameterNumber( QStringLiteral( "TRAVEL_COST" ), QObject::tr( "Travel cost (distance for 'Shortest', time for 'Fastest')" ),
QgsProcessingParameterNumber::Double, 0, false, 0 ) );

std::unique_ptr< QgsProcessingParameterBoolean > includeBounds = qgis::make_unique< QgsProcessingParameterBoolean >( QStringLiteral( "INCLUDE_BOUNDS" ), QObject::tr( "Include upper/lower bound points" ), false, true );
includeBounds->setFlags( includeBounds->flags() | QgsProcessingParameterDefinition::FlagAdvanced );
addParameter( includeBounds.release() );

std::unique_ptr< QgsProcessingParameterFeatureSink > outputLines = qgis::make_unique< QgsProcessingParameterFeatureSink >( QStringLiteral( "OUTPUT_LINES" ), QObject::tr( "Service area (lines)" ),
QgsProcessing::TypeVectorLine, QVariant(), true );
outputLines->setCreateByDefault( true );
addParameter( outputLines.release() );

std::unique_ptr< QgsProcessingParameterFeatureSink > outputPoints = qgis::make_unique< QgsProcessingParameterFeatureSink >( QStringLiteral( "OUTPUT" ), QObject::tr( "Service area (boundary nodes)" ),
QgsProcessing::TypeVectorPoint, QVariant(), true );
outputPoints->setCreateByDefault( false );
addParameter( outputPoints.release() );
}

QVariantMap QgsServiceAreaFromPointAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
{
loadCommonParams( parameters, context, feedback );

QgsPointXY startPoint = parameterAsPoint( parameters, QStringLiteral( "START_POINT" ), context, mNetwork->sourceCrs() );
double travelCost = parameterAsDouble( parameters, QStringLiteral( "TRAVEL_COST" ), context );

bool includeBounds = true; // default to true to maintain 3.0 API
if ( parameters.contains( QStringLiteral( "INCLUDE_BOUNDS" ) ) )
{
includeBounds = parameterAsBool( parameters, QStringLiteral( "INCLUDE_BOUNDS" ), context );
}

feedback->pushInfo( QObject::tr( "Building graph…" ) );
QVector< QgsPointXY > snappedPoints;
mDirector->makeGraph( mBuilder.get(), QVector< QgsPointXY >() << startPoint, snappedPoints, feedback );

feedback->pushInfo( QObject::tr( "Calculating service area…" ) );
QgsGraph *graph = mBuilder->graph();
int idxStart = graph->findVertex( snappedPoints[0] );

QVector< int > tree;
QVector< double > costs;
QgsGraphAnalyzer::dijkstra( graph, idxStart, 0, &tree, &costs );

QgsMultiPointXY points;
QgsMultiPolylineXY lines;
QSet< int > vertices;

int inboundEdgeIndex;
double startVertexCost, endVertexCost;
QgsPointXY edgeStart, edgeEnd;
QgsGraphEdge edge;

for ( int i = 0; i < costs.size(); i++ )
{
inboundEdgeIndex = tree.at( i );
if ( inboundEdgeIndex == -1 and i != idxStart )
{
// unreachable vertex
continue;
}

startVertexCost = costs.at( i );
if ( startVertexCost > travelCost )
{
// vertex is too expensive, discard
continue;
}

vertices.insert( i );
edgeStart = graph->vertex( i ).point();

// find all edges coming from this vertex
for ( int edgeId : graph->vertex( i ).outgoingEdges() )
{
edge = graph->edge( edgeId );
endVertexCost = startVertexCost + edge.cost( 0 ).toDouble();
edgeEnd = graph->vertex( edge.toVertex() ).point();
if ( endVertexCost <= travelCost )
{
// end vertex is cheap enough to include
vertices.insert( edge.toVertex() );
lines.push_back( QgsPolylineXY() << edgeStart << edgeEnd );
}
else
{
// travelCost sits somewhere on this edge, interpolate position
QgsPointXY interpolatedEndPoint = QgsGeometryUtils::interpolatePointOnLineByValue( edgeStart.x(), edgeStart.y(), startVertexCost,
edgeEnd.x(), edgeEnd.y(), endVertexCost, travelCost );

points.push_back( interpolatedEndPoint );
lines.push_back( QgsPolylineXY() << edgeStart << interpolatedEndPoint );
}
} // edges
} // costs

// convert to list so he have same order of points between algorithm runs
QList< int > verticesList = vertices.toList();
std::sort( verticesList.begin(), verticesList.end() );
for ( int v : verticesList )
{
points.push_back( graph->vertex( v ).point() );
}
// this produces correct results, but order of point is not the same, so tests failed
//QSet< int >::const_iterator it = vertices.constBegin();
//while ( it != vertices.constEnd() )
//{
// points.push_back( graph->vertex( *it ).point() );
// it++;
//}

feedback->pushInfo( QObject::tr( "Writing results…" ) );

QVariantMap outputs;

QgsFields fields;
fields.append( QgsField( QStringLiteral( "type" ), QVariant::String ) );
fields.append( QgsField( QStringLiteral( "start" ), QVariant::String ) );

QgsFeature feat;
feat.setFields( fields );

QString pointsSinkId;
std::unique_ptr< QgsFeatureSink > pointsSink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, pointsSinkId, fields,
QgsWkbTypes::MultiPoint, mNetwork->sourceCrs() ) );

if ( pointsSink )
{
outputs.insert( QStringLiteral( "OUTPUT" ), pointsSinkId );

QgsGeometry geomPoints = QgsGeometry::fromMultiPointXY( points );
feat.setGeometry( geomPoints );
feat.setAttributes( QgsAttributes() << QStringLiteral( "within" ) << startPoint.toString() );
pointsSink->addFeature( feat, QgsFeatureSink::FastInsert );

if ( includeBounds )
{
QgsMultiPointXY upperBoundary, lowerBoundary;
QVector< int > nodes;

int vertexId;
for ( int i = 0; i < costs.size(); i++ )
{
if ( costs.at( i ) > travelCost and tree.at( i ) != -1 )
{
vertexId = graph->edge( tree.at( i ) ).fromVertex();
if ( costs.at( vertexId ) <= travelCost )
{
nodes.push_back( i );
}
}
} // costs

for ( int i : nodes )
{
upperBoundary.push_back( graph->vertex( graph->edge( tree.at( i ) ).toVertex() ).point() );
lowerBoundary.push_back( graph->vertex( graph->edge( tree.at( i ) ).fromVertex() ).point() );
} // nodes

QgsGeometry geomUpper = QgsGeometry::fromMultiPointXY( upperBoundary );
QgsGeometry geomLower = QgsGeometry::fromMultiPointXY( lowerBoundary );

feat.setGeometry( geomUpper );
feat.setAttributes( QgsAttributes() << QStringLiteral( "upper" ) << startPoint.toString() );
pointsSink->addFeature( feat, QgsFeatureSink::FastInsert );

feat.setGeometry( geomLower );
feat.setAttributes( QgsAttributes() << QStringLiteral( "lower" ) << startPoint.toString() );
pointsSink->addFeature( feat, QgsFeatureSink::FastInsert );
} // includeBounds
}

QString linesSinkId;
std::unique_ptr< QgsFeatureSink > linesSink( parameterAsSink( parameters, QStringLiteral( "OUTPUT_LINES" ), context, linesSinkId, fields,
QgsWkbTypes::MultiLineString, mNetwork->sourceCrs() ) );

if ( linesSink )
{
outputs.insert( QStringLiteral( "OUTPUT_LINES" ), linesSinkId );
QgsGeometry geomLines = QgsGeometry::fromMultiPolylineXY( lines );
feat.setGeometry( geomLines );
feat.setAttributes( QgsAttributes() << QStringLiteral( "lines" ) << startPoint.toString() );
linesSink->addFeature( feat, QgsFeatureSink::FastInsert );
}

return outputs;
}

///@endcond
53 changes: 53 additions & 0 deletions src/analysis/processing/qgsalgorithmserviceareafrompoint.h
@@ -0,0 +1,53 @@
/***************************************************************************
qgsalgorithmserviceareafrompoint.h
---------------------
begin : JUly 2018
copyright : (C) 2018 by Alexander Bruy
email : alexander dot bruy at gmail dot com
***************************************************************************/

/***************************************************************************
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
***************************************************************************/

#ifndef QGSALGORITHMSERVICEAREAFROMPOINT_H
#define QGSALGORITHMSERVICEAREAFROMPOINT_H

#define SIP_NO_FILE

#include "qgis.h"
#include "qgsalgorithmnetworkanalysisbase.h"

///@cond PRIVATE

/**
* Native service area (from point) algorithm.
*/
class QgsServiceAreaFromPointAlgorithm : public QgsNetworkAnalysisAlgorithmBase
{

public:

QgsServiceAreaFromPointAlgorithm() = default;
void initAlgorithm( const QVariantMap &configuration = QVariantMap() ) override;
QString name() const override;
QString displayName() const override;
QStringList tags() const override;
QString shortHelpString() const override;
QgsServiceAreaFromPointAlgorithm *createInstance() const override SIP_FACTORY;

protected:

QVariantMap processAlgorithm( const QVariantMap &parameters,
QgsProcessingContext &context, QgsProcessingFeedback *feedback ) override;

};

///@endcond PRIVATE

#endif // QGSALGORITHMSERVICEAREAFROMPOINT_H
2 changes: 2 additions & 0 deletions src/analysis/processing/qgsnativealgorithms.cpp
Expand Up @@ -94,6 +94,7 @@
#include "qgsalgorithmrotate.h"
#include "qgsalgorithmsaveselectedfeatures.h"
#include "qgsalgorithmsegmentize.h"
#include "qgsalgorithmserviceareafrompoint.h"
#include "qgsalgorithmshortestpathlayertopoint.h"
#include "qgsalgorithmshortestpathpointtolayer.h"
#include "qgsalgorithmshortestpathpointtopoint.h"
Expand Down Expand Up @@ -250,6 +251,7 @@ void QgsNativeAlgorithms::loadAlgorithms()
addAlgorithm( new QgsSegmentizeByMaximumAngleAlgorithm() );
addAlgorithm( new QgsSegmentizeByMaximumDistanceAlgorithm() );
addAlgorithm( new QgsSelectByLocationAlgorithm() );
addAlgorithm( new QgsServiceAreaFromPointAlgorithm() );
addAlgorithm( new QgsShortestPathLayerToPointAlgorithm() );
addAlgorithm( new QgsShortestPathPointToLayerAlgorithm() );
addAlgorithm( new QgsShortestPathPointToPointAlgorithm() );
Expand Down

0 comments on commit 5970d1c

Please sign in to comment.