locationIndexOnEdgeOrPath static method

int locationIndexOnEdgeOrPath(Point<double> point, List<Point<double>> poly, bool closed, bool geodesic, double toleranceEarth,)

Computes whether (and where) a given point lies on or near a polyline, within a specified toleranceEarth in meters.

If closed, the closing segment between the last and first points of the polyline is considered.

Returns -1 if the point does not lie on or near the polyline. Returns 0 if the point is between poly[0] and poly[1] (inclusive), 1 if between poly[1] and poly[2], etc.

Implementation

static int locationIndexOnEdgeOrPath(
    Point<double> point,
    List<Point<double>> poly,
    bool closed,
    bool geodesic,
    double toleranceEarth) {
  final size = poly.length;
  if (size == 0) {
    return -1;
  }

  final tolerance = toleranceEarth / MathUtils.earthRadius;
  final havTolerance = MathUtils.hav(tolerance);
  final lat3 = SphericalUtils.toRadians(point.x);
  final lng3 = SphericalUtils.toRadians(point.y);
  final prev = poly[closed ? size - 1 : 0];
  double lat1 = SphericalUtils.toRadians(prev.x);
  double lng1 = SphericalUtils.toRadians(prev.y);
  int idx = 0;
  if (geodesic) {
    for (final point2 in poly) {
      final lat2 = SphericalUtils.toRadians(point2.x);
      final lng2 = SphericalUtils.toRadians(point2.y);
      if (_isOnSegmentGC(lat1, lng1, lat2, lng2, lat3, lng3, havTolerance)) {
        return max(0, idx - 1);
      }
      lat1 = lat2;
      lng1 = lng2;
      idx++;
    }
  } else {
    // We project the points to mercator space, where the Rhumb segment is a
    // straight line, and compute the geodesic distance between point3 and the
    // closest point on the segment. This method is an approximation, because
    // it uses "closest" in mercator space which is not "closest" on the
    // sphere — but the error is small because "tolerance" is small.
    final minAcceptable = lat3 - tolerance;
    final maxAcceptable = lat3 + tolerance;
    double y1 = MathUtils.mercator(lat1);
    final y3 = MathUtils.mercator(lat3);
    final xTry = List<double>.filled(3, 0.0);
    for (final point2 in poly) {
      final lat2 = SphericalUtils.toRadians(point2.x);
      final y2 = MathUtils.mercator(lat2);
      final lng2 = SphericalUtils.toRadians(point2.y);
      if (max(lat1, lat2) >= minAcceptable &&
          min(lat1, lat2) <= maxAcceptable) {
        // We offset ys by -lng1; the implicit x1 is 0.
        final x2 = MathUtils.wrap(lng2 - lng1, -pi, pi);
        final x3Base = MathUtils.wrap(lng3 - lng1, -pi, pi);
        xTry[0] = x3Base;
        // Also explore wrapping of x3Base around the world in both directions.
        xTry[1] = x3Base + 2 * pi;
        xTry[2] = x3Base - 2 * pi;
        for (final x3 in xTry) {
          final dy = y2 - y1;
          final len2 = x2 * x2 + dy * dy;
          final t = len2 <= 0
              ? 0.0
              : MathUtils.clamp((x3 * x2 + (y3 - y1) * dy) / len2, 0, 1);
          final xClosest = t * x2;
          final yClosest = y1 + t * dy;
          final latClosest = MathUtils.inverseMercator(yClosest);
          final havDist =
              MathUtils.havDistance(lat3, latClosest, x3 - xClosest);

          if (havDist < havTolerance) return max(0, idx - 1);
        }
      }
      lat1 = lat2;
      lng1 = lng2;
      y1 = y2;
      idx++;
    }
  }
  return -1;
}