locationIndexOnEdgeOrPath static method

int locationIndexOnEdgeOrPath(
  1. Point<num> point,
  2. List<Point<num>> poly,
  3. bool closed,
  4. bool geodesic,
  5. 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)

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, double toleranceEarth) {
  int size = poly.length;
  if (size == 0) {
    return -1;
  }

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

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