locationIndexOnEdgeOrPath static method
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.
@param point our needle
@param poly our haystack
@param closed whether the polyline should be considered closed by
a segment connecting the last point back to the
first one
@param geodesic the polyline is composed of great circle segments if
geodesic is true, and of Rhumb segments otherwise
@param 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(LatLng point, List<LatLng> poly,
bool closed, bool geodesic, num toleranceEarth) {
if (poly.isEmpty) {
return -1;
}
final tolerance = toleranceEarth / earthRadius;
final havTolerance = MathUtil.hav(tolerance);
final lat3 = MathUtil.toRadians(point.latitude);
final lng3 = MathUtil.toRadians(point.longitude);
final prev = closed ? poly.last : poly.first;
var lat1 = MathUtil.toRadians(prev.latitude);
var lng1 = MathUtil.toRadians(prev.longitude);
var idx = 0;
if (geodesic) {
for (final point2 in poly) {
final lat2 = MathUtil.toRadians(point2.latitude);
final lng2 = MathUtil.toRadians(point2.longitude);
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;
var y1 = MathUtil.mercator(lat1);
final y3 = MathUtil.mercator(lat3);
final xTry = List<num?>.generate(3, (index) => null);
for (final point2 in poly) {
final lat2 = MathUtil.toRadians(point2.latitude);
final y2 = MathUtil.mercator(lat2);
final lng2 = MathUtil.toRadians(point2.longitude);
if (max(lat1, lat2) >= minAcceptable &&
min(lat1, lat2) <= maxAcceptable) {
// We offset longitudes by -lng1; the implicit x1 is 0.
final x2 = MathUtil.wrap(lng2 - lng1, -pi, pi);
final x3Base = MathUtil.wrap(lng3 - lng1, -pi, pi);
xTry[0] = x3Base;
// Also explore MathUtil.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
: MathUtil.clamp((x3! * x2 + (y3 - y1) * dy) / len2, 0, 1);
final xClosest = t * x2;
final yClosest = y1 + t * dy;
final latClosest = MathUtil.inverseMercator(yClosest);
final havDist =
MathUtil.havDistance(lat3, latClosest, x3! - xClosest);
if (havDist < havTolerance) {
return max(0, idx - 1);
}
}
}
lat1 = lat2;
lng1 = lng2;
y1 = y2;
idx++;
}
}
return -1;
}