Method GetBestCandidatePaths

tools/openlr/candidate_paths_getter.cpp:176–247

}

void CandidatePathsGetter::GetBestCandidatePaths(vector<LinkPtr> const & allPaths, bool const isLastPoint,
                                                 uint32_t const requiredBearing, double const bearDistM,
                                                 m2::PointD const & startPoint, vector<Graph::EdgeVector> & candidates)
{
  set<CandidatePath> candidatePaths;
  set<CandidatePath> fakeEndingsCandidatePaths;

  BearingPointsSelector pointsSelector(bearDistM, isLastPoint);
  for (auto const & l : allPaths)
  {
    auto const bearStartPoint = pointsSelector.GetStartPoint(l->GetStartEdge());
    auto const startPointsDistance = mercator::DistanceOnEarth(bearStartPoint, startPoint);

    // Number of edges counting from the last one to check bearing on. Accorfing to OpenLR spec
    // we have to check bearing on a point that is no longer than 25 meters traveling down the path.
    // But sometimes we may skip the best place to stop and generate a candidate. So we check several
    // edges before the last one to avoid such a situation. Number of iterations is taken
    // by intuition.
    // Example:
    // o -------- o  { Partners segment. }
    // o ------- o --- o { Our candidate. }
    //               ^ 25m
    //           ^ This one may be better than
    //                 ^ this one.
    // So we want to check them all.
    uint32_t traceBackIterationsLeft = 3;
    for (auto part = l; part; part = part->m_parent)
    {
      if (traceBackIterationsLeft == 0)
        break;

      --traceBackIterationsLeft;

      auto const bearEndPoint = pointsSelector.GetEndPoint(part->m_edge, part->m_distanceM);

      auto const bearing = cpg::Bearing(bearStartPoint, bearEndPoint);
      auto const bearingDiff = AbsDifference(bearing, requiredBearing);
      auto const pathDistDiff = AbsDifference(part->m_distanceM, bearDistM);

      // TODO(mgsergio): Check bearing is within tolerance. Add to canidates if it is.

      if (part->m_hasFake)
        fakeEndingsCandidatePaths.emplace(part, bearingDiff, pathDistDiff, startPointsDistance);
      else
        candidatePaths.emplace(part, bearingDiff, pathDistDiff, startPointsDistance);
    }
  }

  ASSERT(none_of(begin(candidatePaths), end(candidatePaths), mem_fn(&CandidatePath::HasFakeEndings)), ());
  ASSERT(fakeEndingsCandidatePaths.empty() || any_of(begin(fakeEndingsCandidatePaths), end(fakeEndingsCandidatePaths),
                                                     mem_fn(&CandidatePath::HasFakeEndings)),
         ());

  vector<CandidatePath> paths;
  copy_n(begin(candidatePaths), min(static_cast<size_t>(kMaxCandidates), candidatePaths.size()), back_inserter(paths));

  copy_n(begin(fakeEndingsCandidatePaths),
         min(static_cast<size_t>(kMaxFakeCandidates), fakeEndingsCandidatePaths.size()), back_inserter(paths));