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 tolerance. If closed, the closing segment between the last and first points of the polyline is not considered.

point our needle

poly our haystack

closed whether the polyline should be considered closed by a segment connecting the last point back to the first one

geodesic the polyline is composed of great circle segments if geodesic is true, and of Rhumb segments otherwise

toleranceEarth tolerance (in meters)

Returns -1 if point does not lie on or near the polyline.

0 if point is between poly[0] and poly[1] (inclusive),

1 if between poly[1] and poly[2],

poly.size()-2 if between poly[poly.size() - 2] and poly[poly.size() - 1]

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>.generate(3, (index) => 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
              : 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;
}