Method FindBestEdges

libs/routing/index_router.cpp:1293–1374

}

bool IndexRouter::PointsOnEdgesSnapping::FindBestEdges(m2::PointD const & checkpoint, m2::PointD const & direction,
                                                       bool isOutgoing, double closestEdgesRadiusM,
                                                       vector<Edge> & bestEdges,
                                                       bool & bestSegmentIsAlmostCodirectional)
{
  auto const rect = mercator::RectByCenterXYAndSizeInMeters(checkpoint, closestEdgesRadiusM);
  auto closestRoads = m_router.m_roadGraph.FindRoads(rect, [this](FeatureID const & fid)
  {
    auto const & info = fid.m_mwmId.GetInfo();
    return m_router.m_numMwmIds->ContainsFile(info->GetLocalFile().GetCountryFile());
  });

  set<Segment> deadEnds[2];
  // Removing all dead ends from |closestRoads|. Then some candidates will be taken from |closestRoads|.
  // It's necessary to remove all dead ends for all |closestRoads| before IsFencedOff().
  // If to remove all fenced off by other features from |checkpoint| candidates at first,
  // only dead ends candidates may be left. And then the dead end candidates will be removed
  // as well as dead ends. It often happens near airports.
  EraseIfDeadEnd(checkpoint, closestRoads, deadEnds[0]);

  // Sorting from the closest features to the further ones. The idea is the closer
  // a feature to a |checkpoint| the more chances that it crosses the segment
  // |checkpoint|, projections of |checkpoint| on feature edges. It confirmed with benchmarks.
  sort(closestRoads.begin(), closestRoads.end(), [&checkpoint](RoadInfoT const & lhs, RoadInfoT const & rhs)
  {
    auto const & lj = lhs.m_roadInfo.m_junctions;
    auto const & rj = rhs.m_roadInfo.m_junctions;
    ASSERT(!lj.empty() && !rj.empty(), ());

    return checkpoint.SquaredLength(lj[0].GetPoint()) < checkpoint.SquaredLength(rj[0].GetPoint());
  });

  // Note about necessity of removing dead ends twice.
  // At first, only real dead ends and roads which are not correct according to |worldGraph|
  // are removed in EraseIfDeadEnd() function. It's necessary to prepare correct road network
  // (|closestRoads|) which will be used in IsFencedOff() method later and |closestRoads|
  // should contain all roads independently of routing options to prevent crossing roads
  // which are switched off in RoutingOptions.
  // Then in |IsDeadEndCached(..., true /* useRoutingOptions */, ...)| below we ignore
  // candidates if it's a dead end taking into acount routing options. We ignore candidates as well
  // if they don't match RoutingOptions.
  auto const isGood = [&](EdgeProjectionT const & edgeProj)
  {
    auto const segment = GetSegmentByEdge(edgeProj.first);
    if (IsDeadEndCached(segment, isOutgoing, true /* useRoutingOptions */, m_graph, deadEnds[1]) &&
        m_deadEnds[1].count(segment) == 0)
    {
      return false;
    }

    // Removing all candidates which are fenced off by the road graph (|closestRoads|) from |checkpoint|.
    return !IsFencedOff(checkpoint, edgeProj, closestRoads);
  };

  // Getting closest edges from |closestRoads| if they are correct according to isGood() function.
  vector<EdgeProjectionT> candidates;
  RoadsToNearestEdges(checkpoint, closestRoads, isGood, candidates);