itinero / routing

The routing core of itinero.
Apache License 2.0
221 stars 69 forks source link

Hilbert Search misses close vertex #117

Closed ironromeo closed 7 years ago

ironromeo commented 7 years ago

I tested HilbertExtensions.Search and found that it misses most close vertex under some conditions. My test below shows that after adding one more vertex to Graph and resorting, the number of found close vertices become less. I debugged code and find bug in HilbertExtensions.cs line 558. It seems to me that

          vertex = vertex1;
          count = 0;//must be: count = 1;
          return true;

Please run my test and check my proposed fix.

[Test] public void SearchCloseVerticesTest() {

        var DefaultHilbertSteps = (int)System.Math.Pow(2, 15);

        // build locations.
        var locations = new List<Coordinate>();
        locations.Add(new Coordinate(53.06905f, 29.40519f));
        locations.Add(new Coordinate(53.1183f, 29.31932f));
        locations.Add(new Coordinate(53.08611f, 29.37143f));
        locations.Add(new Coordinate(53.05757f, 29.44653f));

        // build graph.
        var graph = new GeometricGraph(1);
        int vertex = 0;
        for (vertex = 0; vertex < locations.Count; vertex++)
        {
            graph.AddVertex((uint)vertex, locations[vertex].Latitude,
                locations[vertex].Longitude);
        }

        // build a sorted version in-place.
        graph.Sort(DefaultHilbertSteps);
        var closelist1 = graph.Search(53.0695f, 29.40594f, 0.1f);
        Assert.AreEqual(3, closelist1.Count);

        locations.Add(new Coordinate());
        graph.AddVertex((uint)vertex, 52.7362f, 29.4935f);

        // build a sorted version in-place.
        graph.Sort(DefaultHilbertSteps);
        var closelist2 = graph.Search(53.0695f, 29.40594f, 0.1f);
        Assert.IsTrue(closelist2.Count >= 3, "some close vertex missed");

    }