Skip to content

Commit a3a79b9

Browse files
nyalldawsonnyalldawson
committedNov 29, 2017
Fix network analysis routing fails in some cases (refs #11687)
·
ltr-3_40final-3_0_0
1 parent 2a960c5 commit a3a79b9

File tree

2 files changed

+68
-9
lines changed

2 files changed

+68
-9
lines changed
 

‎src/analysis/network/qgsvectorlayerdirector.cpp

Lines changed: 13 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -347,6 +347,9 @@ void QgsVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, const
347347
for ( const QgsPointXY &point : line )
348348
{
349349
pt2 = ct.transform( point );
350+
int pPt2idx = findPointWithinTolerance( pt2 );
351+
Q_ASSERT_X( pPt2idx >= 0, "QgsVectorLayerDirectory::makeGraph", "encountered a vertex which was not present in graph" );
352+
pt2 = graphVertices.at( pPt2idx );
350353

351354
if ( !isFirstPoint )
352355
{
@@ -364,21 +367,22 @@ void QgsVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, const
364367
}
365368
}
366369

367-
QgsPointXY pt1;
368-
QgsPointXY pt2;
370+
QgsPointXY arcPt1;
371+
QgsPointXY arcPt2;
369372
int pt1idx = -1;
370373
int pt2idx = -1;
371374
bool isFirstPoint = true;
372375
for ( auto arcPointIt = pointsOnArc.constBegin(); arcPointIt != pointsOnArc.constEnd(); ++arcPointIt )
373376
{
374-
pt2 = arcPointIt.value();
377+
arcPt2 = arcPointIt.value();
375378

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

379-
if ( !isFirstPoint && pt1 != pt2 )
383+
if ( !isFirstPoint && arcPt1 != arcPt2 )
380384
{
381-
double distance = builder->distanceArea()->measureLine( pt1, pt2 );
385+
double distance = builder->distanceArea()->measureLine( arcPt1, arcPt2 );
382386
QVector< QVariant > prop;
383387
for ( QgsNetworkStrategy *strategy : mStrategies )
384388
{
@@ -388,16 +392,16 @@ void QgsVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, const
388392
if ( direction == Direction::DirectionForward ||
389393
direction == Direction::DirectionBoth )
390394
{
391-
builder->addEdge( pt1idx, pt1, pt2idx, pt2, prop );
395+
builder->addEdge( pt1idx, arcPt1, pt2idx, arcPt2, prop );
392396
}
393397
if ( direction == Direction::DirectionBackward ||
394398
direction == Direction::DirectionBoth )
395399
{
396-
builder->addEdge( pt2idx, pt2, pt1idx, pt1, prop );
400+
builder->addEdge( pt2idx, arcPt2, pt1idx, arcPt1, prop );
397401
}
398402
}
399403
pt1idx = pt2idx;
400-
pt1 = pt2;
404+
arcPt1 = arcPt2;
401405
isFirstPoint = false;
402406
}
403407
}

‎tests/src/analysis/testqgsnetworkanalysis.cpp

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -41,6 +41,7 @@ class TestQgsNetworkAnalysis : public QObject
4141
void testBuild();
4242
void testBuildTolerance();
4343
void dijkkjkjkskkjsktra();
44+
void testRouteFail();
4445

4546
private:
4647
std::unique_ptr< QgsVectorLayer > buildNetwork();
@@ -462,6 +463,60 @@ void TestQgsNetworkAnalysis::dijkkjkjkskkjsktra()
462463
QCOMPARE( graph->edge( resultTree.at( point_0_0_idx ) ).toVertex(), point_0_0_idx );
463464
}
464465

466+
void TestQgsNetworkAnalysis::testRouteFail()
467+
{
468+
std::unique_ptr< QgsVectorLayer > network = qgis::make_unique< QgsVectorLayer >( QStringLiteral( "LineString?crs=epsg:28355&field=cost:int" ), QStringLiteral( "x" ), QStringLiteral( "memory" ) );
469+
470+
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)" )
471+
<< QStringLiteral( "LineString (302081.70763194985920563 5753475.1403581602498889, 301978.24500802176771685 5753368.03299263771623373)" )
472+
<< QStringLiteral( "LineString (302181.69117977644782513 5753576.27856593858450651, 302081.71834095334634185 5753475.14562766999006271)" );
473+
QgsFeatureList flist;
474+
for ( const QString &line : lines )
475+
{
476+
QgsFeature ff( 0 );
477+
QgsGeometry refGeom = QgsGeometry::fromWkt( line );
478+
ff.setGeometry( refGeom );
479+
ff.setAttributes( QgsAttributes() << 1 );
480+
flist << ff;
481+
}
482+
network->dataProvider()->addFeatures( flist );
483+
484+
// build graph
485+
std::unique_ptr< QgsVectorLayerDirector > director = qgis::make_unique< QgsVectorLayerDirector > ( network.get(),
486+
-1, QString(), QString(), QString(), QgsVectorLayerDirector::DirectionBoth );
487+
std::unique_ptr< QgsNetworkStrategy > strategy = qgis::make_unique< TestNetworkStrategy >();
488+
director->addStrategy( strategy.release() );
489+
std::unique_ptr< QgsGraphBuilder > builder = qgis::make_unique< QgsGraphBuilder > ( network->sourceCrs(), true, 1 );
490+
491+
QgsPointXY start( 302131.1053754404, 5753392.757948928 );
492+
QgsPointXY end( 302148.1636281528, 5753541.408436851 );
493+
494+
QVector<QgsPointXY > snapped;
495+
director->makeGraph( builder.get(), QVector<QgsPointXY>() << start << end, snapped );
496+
std::unique_ptr< QgsGraph > graph( builder->graph() );
497+
498+
QgsPointXY snappedStart = snapped.at( 0 );
499+
QGSCOMPARENEAR( snappedStart.x(), 302131.3, 0.1 );
500+
QGSCOMPARENEAR( snappedStart.y(), 5753392.5, 0.1 );
501+
int startVertexIdx = graph->findVertex( snappedStart );
502+
QVERIFY( startVertexIdx != -1 );
503+
QgsPointXY snappedEnd = snapped.at( 1 );
504+
QGSCOMPARENEAR( snappedEnd.x(), 302147.68, 0.1 );
505+
QGSCOMPARENEAR( snappedEnd.y(), 5753541.88, 0.1 );
506+
int endVertexIdx = graph->findVertex( snappedEnd );
507+
QVERIFY( endVertexIdx != -1 );
508+
509+
// both directions
510+
QVector<int> resultTree;
511+
QVector<double> resultCost;
512+
QgsGraphAnalyzer::dijkstra( graph.get(), startVertexIdx, 0, &resultTree, &resultCost );
513+
514+
QCOMPARE( resultTree.at( startVertexIdx ), -1 );
515+
QCOMPARE( resultCost.at( startVertexIdx ), 0.0 );
516+
QVERIFY( resultTree.at( endVertexIdx ) != -1 );
517+
QCOMPARE( resultCost.at( endVertexIdx ), 6.0 );
518+
}
519+
465520

466521

467522
QGSTEST_MAIN( TestQgsNetworkAnalysis )

0 commit comments

Comments
 (0)
Please sign in to comment.