    collections.push_back(collection);
    return collections;
  }
  
  QList<QGeoCoordinate> polyline_to_coordinate_list(const QString &polylineString) {
    QList<QGeoCoordinate> path;
    if (polylineString.isEmpty())
        return path;
  
    QByteArray data = polylineString.toLatin1();
  
    bool parsingLatitude = true;
  
    int shift = 0;
    int value = 0;
  
    QGeoCoordinate coord(0, 0);
  
    for (int i = 0; i < data.length(); ++i) {
        unsigned char c = data.at(i) - 63;
  
        value |= (c & 0x1f) << shift;
        shift += 5;
  
        // another chunk
        if (c & 0x20)
            continue;
  
        int diff = (value & 1) ? ~(value >> 1) : (value >> 1);
  
        if (parsingLatitude) {
            coord.setLatitude(coord.latitude() + (double)diff/1e6);
        } else {
            coord.setLongitude(coord.longitude() + (double)diff/1e6);
            path.append(coord);
        }
  
        parsingLatitude = !parsingLatitude;
  
        value = 0;
        shift = 0;
    }
  
    return path;
  }
  
  static QGeoCoordinate sub(QGeoCoordinate v, QGeoCoordinate w) {
    return QGeoCoordinate(v.latitude() - w.latitude(), v.longitude() - w.longitude());
  }
  
  static QGeoCoordinate add(QGeoCoordinate v, QGeoCoordinate w) {
    return QGeoCoordinate(v.latitude() + w.latitude(), v.longitude() + w.longitude());
  }
  
  static QGeoCoordinate mul(QGeoCoordinate v, float c) {
    return QGeoCoordinate(c * v.latitude(), c * v.longitude());
  }
  
  static float dot(QGeoCoordinate v, QGeoCoordinate w) {
    return v.latitude() * w.latitude() + v.longitude() * w.longitude();
  }
  
  float minimum_distance(QGeoCoordinate a, QGeoCoordinate b, QGeoCoordinate p) {
    // If a and b are the same coordinate the computation below doesn't work
    if (a.distanceTo(b) < 0.01) {
      return a.distanceTo(p);
    }
  
    const QGeoCoordinate ap = sub(p, a);
    const QGeoCoordinate ab = sub(b, a);
    const float t = std::clamp(dot(ap, ab) / dot(ab, ab), 0.0f, 1.0f);
    const QGeoCoordinate projection = add(a, mul(ab, t));
    return projection.distanceTo(p);
  }
  
  float distance_along_geometry(QList<QGeoCoordinate> geometry, QGeoCoordinate pos) {
    if (geometry.size() <= 2) {
      return geometry[0].distanceTo(pos);
    }
  
    // 1. Find segment that is closest to current position
    // 2. Total distance is sum of distance to start of closest segment
    //    + all previous segments
    double total_distance = 0;
    double total_distance_closest = 0;
    double closest_distance = std::numeric_limits<double>::max();
  
    for (int i = 0; i < geometry.size() - 1; i++) {
      double d = minimum_distance(geometry[i], geometry[i+1], pos);
      if (d < closest_distance) {
        closest_distance = d;
        total_distance_closest = total_distance + geometry[i].distanceTo(pos);
      }
      total_distance += geometry[i].distanceTo(geometry[i+1]);
    }
  
    return total_distance_closest;
  }
  
  std::optional<QMapbox::Coordinate> coordinate_from_param(std::string param) {
    QString json_str = QString::fromStdString(Params().get(param));
    if (json_str.isEmpty()) return {};
  
    QJsonDocument doc = QJsonDocument::fromJson(json_str.toUtf8());
 
</s> remove     // TODO: make mapd output YUV
    // hlayout->addWidget(new CameraViewWidget("navd", VISION_STREAM_MAP, false));
 </s> add  </s> remove 
# navd
if maps:
  navd_src = ["navd/main.cc", "navd/route_engine.cc", "navd/map_renderer.cc"]
  qt_env.Program("navd/_navd", navd_src, LIBS=qt_libs + ['common', 'json11'])

  if GetOption('extras'):
    qt_env.SharedLibrary("navd/map_renderer", ["navd/map_renderer.cc"], LIBS=qt_libs + ['common', 'messaging'])
 </s> add  </s> remove       if (TICI and p in ['ui', 'navd']):
 </s> add       if (TICI and p in ['ui',]): </s> remove QList<QGeoCoordinate> polyline_to_coordinate_list(const QString &polylineString);
 </s> add  </s> remove float distance_along_geometry(QList<QGeoCoordinate> geometry, QGeoCoordinate pos);
 </s> add 
    collections.push_back(collection);
    return collections;
  }
  































































































  std::optional<QMapbox::Coordinate> coordinate_from_param(std::string param) {
    QString json_str = QString::fromStdString(Params().get(param));
    if (json_str.isEmpty()) return {};
  
    QJsonDocument doc = QJsonDocument::fromJson(json_str.toUtf8());
keep keep keep keep replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace replace keep keep keep keep keep
 navd: rewrite in python (#24621)

* navd: start python rewrite

* use enum

* send empty instruction packet

* parse banner

* cleanup

* switch to coordinate class

* add segment transition logic

* add recompute logic

* cleanup old navd code

* split out helpers

* cleanup release files

* fix typo

* fix docs

* add typing to helpers

* small fixes

* move outside of ui

* get last pos from param

* add ui restart detection

* check running

* send route

* set navInstruction to invalid with no active route

* whitespace

* do not overwrite response and use ratekeeper

* reuse params object

* remove navd exception 
selfdrive/ui/qt/maps/map_helpers.cc