Skip to content

Commit a3428e5

Browse files
committedJan 24, 2019
Fix shortest path algorithm can "shortcut" when using network in geographic coordinates
Fixes #20997 (cherry picked from commit e75a888)
1 parent 7e25cea commit a3428e5

File tree

2 files changed

+59
-1
lines changed

2 files changed

+59
-1
lines changed
 

‎src/analysis/network/qgsvectorlayerdirector.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -254,7 +254,7 @@ void QgsVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, const
254254
else
255255
{
256256
thisSegmentClosestDist = additionalPoint.sqrDistToSegment( pt1.x(), pt1.y(),
257-
pt2.x(), pt2.y(), snappedPoint );
257+
pt2.x(), pt2.y(), snappedPoint, 0 );
258258
}
259259

260260
if ( thisSegmentClosestDist < additionalTiePoints[ i ].mLength )

‎tests/src/analysis/testqgsnetworkanalysis.cpp

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,7 @@ class TestQgsNetworkAnalysis : public QObject
4242
void testBuildTolerance();
4343
void dijkkjkjkskkjsktra();
4444
void testRouteFail();
45+
void testRouteFail2();
4546

4647
private:
4748
std::unique_ptr< QgsVectorLayer > buildNetwork();
@@ -517,6 +518,63 @@ void TestQgsNetworkAnalysis::testRouteFail()
517518
QCOMPARE( resultCost.at( endVertexIdx ), 6.0 );
518519
}
519520

521+
void TestQgsNetworkAnalysis::testRouteFail2()
522+
{
523+
std::unique_ptr< QgsVectorLayer > network = qgis::make_unique< QgsVectorLayer >( QStringLiteral( "LineString?crs=epsg:4326&field=cost:int" ), QStringLiteral( "x" ), QStringLiteral( "memory" ) );
524+
525+
QStringList lines = QStringList() << QStringLiteral( "LineString (11.25044997999680874 48.42605439713970128, 11.25044693759680925 48.42603339773970106, 11.25044760759680962 48.42591690773969759, 11.25052289759680946 48.42589190773969676)" )
526+
<< QStringLiteral( "LineString (11.25052289759680946 48.42589190773969676, 11.25050350759680917 48.42586202773969717, 11.25047190759680937 48.42581754773969749, 11.2504146475968092 48.42573849773970096, 11.25038716759680923 48.42569834773969717, 11.2502920175968093 48.42557470773969897, 11.25019984759680902 48.42560406773969817, 11.25020393759680992 48.42571203773970012, 11.2502482875968095 48.42577478773969801, 11.25021922759680848 48.42578442773969982)" )
527+
<< QStringLiteral( "LineString (11.2504146475968092 48.42573849773970096, 11.25048389759681022 48.42572031773969599, 11.25051325759680942 48.42570672773970131)" )
528+
<< QStringLiteral( "LineString (11.25038716759680923 48.42569834773969717, 11.25055288759680927 48.42564748773969541, 11.25052296759680992 48.42560921773969795)" );
529+
QgsFeatureList flist;
530+
int i = 0;
531+
for ( const QString &line : lines )
532+
{
533+
QgsFeature ff( 0 );
534+
QgsGeometry refGeom = QgsGeometry::fromWkt( line );
535+
ff.setGeometry( refGeom );
536+
ff.setAttributes( QgsAttributes() << 1 + 0.001 * i );
537+
i++;
538+
flist << ff;
539+
}
540+
network->dataProvider()->addFeatures( flist );
541+
542+
// build graph
543+
std::unique_ptr< QgsVectorLayerDirector > director = qgis::make_unique< QgsVectorLayerDirector > ( network.get(),
544+
-1, QString(), QString(), QString(), QgsVectorLayerDirector::DirectionBoth );
545+
std::unique_ptr< QgsNetworkStrategy > strategy = qgis::make_unique< TestNetworkStrategy >();
546+
director->addStrategy( strategy.release() );
547+
std::unique_ptr< QgsGraphBuilder > builder = qgis::make_unique< QgsGraphBuilder > ( network->sourceCrs(), true, 0 );
548+
549+
QgsPointXY start( 11.250443581846053, 48.42605665308498 );
550+
QgsPointXY end( 11.250525546822013, 48.42561343506683 );
551+
552+
QVector<QgsPointXY > snapped;
553+
director->makeGraph( builder.get(), QVector<QgsPointXY>() << start << end, snapped );
554+
std::unique_ptr< QgsGraph > graph( builder->graph() );
555+
556+
QgsPointXY snappedStart = snapped.at( 0 );
557+
QGSCOMPARENEAR( snappedStart.x(), 11.250450, 0.000001 );
558+
QGSCOMPARENEAR( snappedStart.y(), 48.426054, 0.000001 );
559+
int startVertexIdx = graph->findVertex( snappedStart );
560+
QVERIFY( startVertexIdx != -1 );
561+
QgsPointXY snappedEnd = snapped.at( 1 );
562+
QGSCOMPARENEAR( snappedEnd.x(), 11.250526, 0.000001 );
563+
QGSCOMPARENEAR( snappedEnd.y(), 48.425613, 0.000001 );
564+
int endVertexIdx = graph->findVertex( snappedEnd );
565+
QVERIFY( endVertexIdx != -1 );
566+
567+
// both directions
568+
QVector<int> resultTree;
569+
QVector<double> resultCost;
570+
QgsGraphAnalyzer::dijkstra( graph.get(), startVertexIdx, 0, &resultTree, &resultCost );
571+
572+
QCOMPARE( resultTree.at( startVertexIdx ), -1 );
573+
QCOMPARE( resultCost.at( startVertexIdx ), 0.0 );
574+
QVERIFY( resultTree.at( endVertexIdx ) != -1 );
575+
QCOMPARE( resultCost.at( endVertexIdx ), 9.01 );
576+
}
577+
520578

521579

522580
QGSTEST_MAIN( TestQgsNetworkAnalysis )

0 commit comments

Comments
 (0)
Please sign in to comment.