CHRouter sets incorrect distance and time values for Route segments for intermediate entries

[alexander233]

The problem can be replicated by calculating a route from node with ID -62 to node with ID -8 in the test_network.osm file. The sixth segment lists a distance of 95meters from the start, the seventh segment drops back to just 17meters. The problem only occurs when using CHRouter, not with Dykstra. The total route distances and timings are not affected by this error; they are the same with both routing algorithms.

CHRouter:

Segment: @0s 0m Segment: @1,22709441184998s 17,0429787700109m Segment: @2,24791181087494s 31,2209982068424m Segment: @4,3176816701889s 59,9678012744044m Segment: @6,16946989297867s 85,6870834878305m Segment: @6,84394156932831s 95,0547459161303m Segment: @1,24382378390504s 17,2753296060065m <===== Error! Segment: @9,67500197887421s 134,375027729583m Segment: @11,0058872699738s 152,859544867631m

The same route for Dykstra:

Segment: @0s 0m Segment: @1,22709441184998s 17,0429787700109m Segment: @2,24791193008423s 31,2209982068424m Segment: @4,31768178939819s 59,9678012744044m Segment: @6,16947031021118s 85,6870834878305m Segment: @6,84394216537476s 95,0547459161303m Segment: @8,08776569366455s 112,330075521527m <=== This is correct! Segment: @9,6750020980835s 134,375027727877m Segment: @11,0058870315552s 152,859544865926m

The problem seems to have to do with intermediate entries that belong to a complex path.

Here are unit test cases:

File: OsmSharp.Test.UnitTests\Routing\RoutingTests.cs

       /// <summary>
       /// Tests that path segment distances are correct for route from node -62 to node -8.
       /// </summary>
        protected void DoTestShortest6()
        {
            //real distances between the nodes
            double[] expected = { 0, 16.7666155465965, 30.8934316881801, 59.62534437702, 85.3371751213439, 94.6996171212966, 112.29063491294, 134.335805089703, 152.80981483087 };

            var interpreter = new OsmRoutingInterpreter();
            IRoutingAlgorithmData<TEdgeData> data = this.BuildData(interpreter, "OsmSharp.Test.Unittests.test_network.osm");
            IRoutingAlgorithm<TEdgeData> basic_router = this.BuildBasicRouter(data);
            Router router = this.BuildRouter(
                data, interpreter, basic_router);
            RouterPoint source = router.Resolve(Vehicle.Car, new GeoCoordinate(51.05812699559792, 3.7188938047970472));
            RouterPoint target = router.Resolve(Vehicle.Car, new GeoCoordinate(51.0578518, 3.7195654));

            Route route = router.Calculate(Vehicle.Car, source, target);
            Assert.IsNotNull(route);

            Assert.AreEqual(9, route.Segments.Length);

            for (int i = 0; i < route.Segments.Length; i++)
            {
                Assert.AreEqual(expected[i], route.Segments[i].Distance, 2); //2.0m of tolerance
            }

        }

File: OsmSharp.Test.UnitTests\Routing\CH\CHEdgeDifferenceRoutingTest.cs (This test currently fails!)

       /// <summary>
       /// Tests that path segment distances are correct for route from node -62 to node -8.
       /// </summary>
        [Test]
        public void TestDykstraShortest6()
        {
            this.DoTestShortest6();
        }

File: OsmSharp.Test.UnitTests\Routing\DykstraRoutingTests.cs (This test passes)

       /// <summary>
       /// Tests that path segment distances are correct for route from node -62 to node -8.
       /// </summary>
        [Test]
        public void TestCHEdgeDifferenceShortest6()
        {
            this.DoTestShortest6();
        }