Skip to content

Commit

Permalink
Fix network analysis routing fails in some cases (refs #11687)
Browse files Browse the repository at this point in the history
  • Loading branch information
@nyalldawson
nyalldawson committed Nov 29, 2017
1 parent 2a960c5 commit a3a79b9
Show file tree
Hide file tree
Showing 2 changed files with 68 additions and 9 deletions.
22 changes: 13 additions & 9 deletions src/analysis/network/qgsvectorlayerdirector.cpp
View file
Expand Up @@ -347,6 +347,9 @@ void QgsVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, const
for ( const QgsPointXY &point : line )
{
pt2 = ct.transform( point );
int pPt2idx = findPointWithinTolerance( pt2 );
Q_ASSERT_X( pPt2idx >= 0, "QgsVectorLayerDirectory::makeGraph", "encountered a vertex which was not present in graph" );
pt2 = graphVertices.at( pPt2idx );

if ( !isFirstPoint )
{
Expand All @@ -364,21 +367,22 @@ void QgsVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, const
}
}

QgsPointXY pt1;
QgsPointXY pt2;
QgsPointXY arcPt1;
QgsPointXY arcPt2;
int pt1idx = -1;
int pt2idx = -1;
bool isFirstPoint = true;
for ( auto arcPointIt = pointsOnArc.constBegin(); arcPointIt != pointsOnArc.constEnd(); ++arcPointIt )
{
pt2 = arcPointIt.value();
arcPt2 = arcPointIt.value();

pt2idx = findPointWithinTolerance( pt2 );
pt2idx = findPointWithinTolerance( arcPt2 );
Q_ASSERT_X( pt2idx >= 0, "QgsVectorLayerDirectory::makeGraph", "encountered a vertex which was not present in graph" );
arcPt2 = graphVertices.at( pt2idx );

if ( !isFirstPoint && pt1 != pt2 )
if ( !isFirstPoint && arcPt1 != arcPt2 )
{
double distance = builder->distanceArea()->measureLine( pt1, pt2 );
double distance = builder->distanceArea()->measureLine( arcPt1, arcPt2 );
QVector< QVariant > prop;
for ( QgsNetworkStrategy *strategy : mStrategies )
{
Expand All @@ -388,16 +392,16 @@ void QgsVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, const
if ( direction == Direction::DirectionForward ||
direction == Direction::DirectionBoth )
{
builder->addEdge( pt1idx, pt1, pt2idx, pt2, prop );
builder->addEdge( pt1idx, arcPt1, pt2idx, arcPt2, prop );
}
if ( direction == Direction::DirectionBackward ||
direction == Direction::DirectionBoth )
{
builder->addEdge( pt2idx, pt2, pt1idx, pt1, prop );
builder->addEdge( pt2idx, arcPt2, pt1idx, arcPt1, prop );
}
}
pt1idx = pt2idx;
pt1 = pt2;
arcPt1 = arcPt2;
isFirstPoint = false;
}
}
Expand Down
55 changes: 55 additions & 0 deletions tests/src/analysis/testqgsnetworkanalysis.cpp
View file
Expand Up @@ -41,6 +41,7 @@ class TestQgsNetworkAnalysis : public QObject
void testBuild();
void testBuildTolerance();
void dijkkjkjkskkjsktra();
void testRouteFail();

private:
std::unique_ptr< QgsVectorLayer > buildNetwork();
Expand Down Expand Up @@ -462,6 +463,60 @@ void TestQgsNetworkAnalysis::dijkkjkjkskkjsktra()
QCOMPARE( graph->edge( resultTree.at( point_0_0_idx ) ).toVertex(), point_0_0_idx );
}

void TestQgsNetworkAnalysis::testRouteFail()
{
std::unique_ptr< QgsVectorLayer > network = qgis::make_unique< QgsVectorLayer >( QStringLiteral( "LineString?crs=epsg:28355&field=cost:int" ), QStringLiteral( "x" ), QStringLiteral( "memory" ) );

QStringList lines = QStringList() << QStringLiteral( "LineString (302081.71116495534079149 5753475.15082756895571947, 302140.54234686412382871 5753417.70564490929245949, 302143.24717211339157075 5753412.57312887348234653, 302143.17789465241366997 5753406.77192200440913439, 302140.35127420048229396 5753401.70546196680516005, 302078.46200818457873538 5753338.31098813004791737, 302038.17299743194598705 5753309.50200006738305092)" )
<< QStringLiteral( "LineString (302081.70763194985920563 5753475.1403581602498889, 301978.24500802176771685 5753368.03299263771623373)" )
<< QStringLiteral( "LineString (302181.69117977644782513 5753576.27856593858450651, 302081.71834095334634185 5753475.14562766999006271)" );
QgsFeatureList flist;
for ( const QString &line : lines )
{
QgsFeature ff( 0 );
QgsGeometry refGeom = QgsGeometry::fromWkt( line );
ff.setGeometry( refGeom );
ff.setAttributes( QgsAttributes() << 1 );
flist << ff;
}
network->dataProvider()->addFeatures( flist );

// build graph
std::unique_ptr< QgsVectorLayerDirector > director = qgis::make_unique< QgsVectorLayerDirector > ( network.get(),
-1, QString(), QString(), QString(), QgsVectorLayerDirector::DirectionBoth );
std::unique_ptr< QgsNetworkStrategy > strategy = qgis::make_unique< TestNetworkStrategy >();
director->addStrategy( strategy.release() );
std::unique_ptr< QgsGraphBuilder > builder = qgis::make_unique< QgsGraphBuilder > ( network->sourceCrs(), true, 1 );

QgsPointXY start( 302131.1053754404, 5753392.757948928 );
QgsPointXY end( 302148.1636281528, 5753541.408436851 );

QVector<QgsPointXY > snapped;
director->makeGraph( builder.get(), QVector<QgsPointXY>() << start << end, snapped );
std::unique_ptr< QgsGraph > graph( builder->graph() );

QgsPointXY snappedStart = snapped.at( 0 );
QGSCOMPARENEAR( snappedStart.x(), 302131.3, 0.1 );
QGSCOMPARENEAR( snappedStart.y(), 5753392.5, 0.1 );
int startVertexIdx = graph->findVertex( snappedStart );
QVERIFY( startVertexIdx != -1 );
QgsPointXY snappedEnd = snapped.at( 1 );
QGSCOMPARENEAR( snappedEnd.x(), 302147.68, 0.1 );
QGSCOMPARENEAR( snappedEnd.y(), 5753541.88, 0.1 );
int endVertexIdx = graph->findVertex( snappedEnd );
QVERIFY( endVertexIdx != -1 );

// both directions
QVector<int> resultTree;
QVector<double> resultCost;
QgsGraphAnalyzer::dijkstra( graph.get(), startVertexIdx, 0, &resultTree, &resultCost );

QCOMPARE( resultTree.at( startVertexIdx ), -1 );
QCOMPARE( resultCost.at( startVertexIdx ), 0.0 );
QVERIFY( resultTree.at( endVertexIdx ) != -1 );
QCOMPARE( resultCost.at( endVertexIdx ), 6.0 );
}



QGSTEST_MAIN( TestQgsNetworkAnalysis )
Expand Down

0 comments on commit a3a79b9

Please sign in to comment.