locationIndexOnEdgeOrPath static method

int locationIndexOnEdgeOrPath(Point<num> point, List<Point<num>> poly, bool closed, bool geodesic, num 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)

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

0 if point is between poly0 and poly1 (inclusive),

1 if between poly1 and poly2,

poly.size()-2 if between polypoly.size() - 2 and polypoly.size() - 1

Implementation

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

  num tolerance = toleranceEarth / MathUtils.earthRadius;
  num havTolerance = MathUtils.hav(tolerance);
  num lat3 = SphericalUtils.toRadians(point.x);
  num lng3 = SphericalUtils.toRadians(point.y);
  Point prev = poly[closed ? size - 1 : 0];
  num lat1 = SphericalUtils.toRadians(prev.x);
  num lng1 = SphericalUtils.toRadians(prev.y);
  int idx = 0;
  if (geodesic) {
    for (final point2 in poly) {
      num lat2 = SphericalUtils.toRadians(point2.x);
      num 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.
    num minAcceptable = lat3 - tolerance;
    num maxAcceptable = lat3 + tolerance;
    num y1 = MathUtils.mercator(lat1);
    num y3 = MathUtils.mercator(lat3);
    List<num> xTry = List.generate(3, (index) => 0);
    for (final point2 in poly) {
      num lat2 = SphericalUtils.toRadians(point2.x);
      num y2 = MathUtils.mercator(lat2);
      num lng2 = SphericalUtils.toRadians(point2.y);
      if (max(lat1, lat2) >= minAcceptable &&
          min(lat1, lat2) <= maxAcceptable) {
        // We offset ys by -lng1; the implicit x1 is 0.
        num x2 = MathUtils.wrap(lng2 - lng1, -pi, pi);
        num 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) {
          num dy = y2 - y1;
          num len2 = x2 * x2 + dy * dy;
          num t = len2 <= 0
              ? 0
              : MathUtils.clamp((x3 * x2 + (y3 - y1) * dy) / len2, 0, 1);
          num xClosest = t * x2;
          num yClosest = y1 + t * dy;
          num latClosest = MathUtils.inverseMercator(yClosest);
          num havDist =
              MathUtils.havDistance(lat3, latClosest, x3 - xClosest);

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