google maps flutter check if a point inside a polygon

Question

I'm working on flutter project using google-maps-flutter plugin, and I want to check if the user location is inside the polygon that I created on the map. There is an easy way using JavaScript api (containsLocation() method) but for flutter I only found a third party plugin,google_map_polyutil, which is only for android and I get a security worming when I run my app. Is there another way to do so??

Commingle

Check this post : #3070127 – Coach

@Coach That's Javascript. – Broadbent

Answer 1

I found this answer and just modified some minor things to work with dart, I ran a test on a hardcoded polygon. The list _area is my polygon and _polygons is required for my mapcontroller.

final Set<Polygon> _polygons = {};
List<LatLng> _area = [
LatLng(-17.770992200, -63.207739700),
LatLng(-17.776386600, -63.213576200),
LatLng(-17.778348200, -63.213576200),
LatLng(-17.786848100, -63.214262900),
LatLng(-17.798289700, -63.211001300),
LatLng(-17.810547700, -63.200701600),
LatLng(-17.815450600, -63.185252100),
LatLng(-17.816267800, -63.170660900),
LatLng(-17.800741300, -63.153838100),
LatLng(-17.785867400, -63.150919800),
LatLng(-17.770501800, -63.152636400),
LatLng(-17.759712400, -63.160361200),
LatLng(-17.755952300, -63.169802600),
LatLng(-17.752519100, -63.186625400),
LatLng(-17.758404500, -63.195551800),
LatLng(-17.770992200, -63.206538100),
LatLng(-17.770996000, -63.207762500)];

The function ended like this:

bool _checkIfValidMarker(LatLng tap, List<LatLng> vertices) {
    int intersectCount = 0;
    for (int j = 0; j < vertices.length - 1; j++) {
      if (rayCastIntersect(tap, vertices[j], vertices[j + 1])) {
        intersectCount++;
      }
    }

    return ((intersectCount % 2) == 1); // odd = inside, even = outside;
  }

  bool rayCastIntersect(LatLng tap, LatLng vertA, LatLng vertB) {
    double aY = vertA.latitude;
    double bY = vertB.latitude;
    double aX = vertA.longitude;
    double bX = vertB.longitude;
    double pY = tap.latitude;
    double pX = tap.longitude;

    if ((aY > pY && bY > pY) || (aY < pY && bY < pY) || (aX < pX && bX < pX)) {
      return false; // a and b can't both be above or below pt.y, and a or
      // b must be east of pt.x
    }

    double m = (aY - bY) / (aX - bX); // Rise over run
    double bee = (-aX) * m + aY; // y = mx + b
    double x = (pY - bee) / m; // algebra is neat!

    return x > pX;
  }

Notice the polygons property and the onTap method. I was trying to check if the marker created in my map was inside my polygon:

GoogleMap(
                          initialCameraPosition: CameraPosition(
                            target: target, //LatLng(0, 0),
                            zoom: 16,
                          ),
                          zoomGesturesEnabled: true,
                          markers: markers,
                          polygons: _polygons,
                          onMapCreated: (controller) =>
                              _mapController = controller,
                          onTap: (latLng) {
                            _getAddress(latLng);
                          },
                        )

Then i just used the following call in my _getAddress method:

_checkIfValidMarker(latLng, _area);

I hope it helps you to create what you need.

Amon

Doesn't work properly if tap above the map! – Truax

Answer 2

The easiest way to use it - https://pub.dev/packages/maps_toolkit

with isLocationOnPath method.

Truax

I think it best one PolygonUtil.containsLocation – Steelworks

Answer 3

The easiest way to use it - https://pub.dev/packages/maps_toolkit

with PolygonUtil.containsLocation - computes whether the given point lies inside the specified polygon.

Oneal

I used the same and it worked! – Stagemanage

Answer 4

L. Chi's answer really help. But due to I have pretty close points, rayCastIntersect might have wrong boolean return if aX is equal to bX

Therefore, I just add aX == bX condition check before calculate m then it works.

bool rayCastIntersect(LatLng tap, LatLng vertA, LatLng vertB) {
    double aY = vertA.latitude;
    double bY = vertB.latitude;
    double aX = vertA.longitude;
    double bX = vertB.longitude;
    double pY = tap.latitude;
    double pX = tap.longitude;

    if ((aY > pY && bY > pY) || (aY < pY && bY < pY) || (aX < pX && bX < pX)) {
      return false; // a and b can't both be above or below pt.y, and a or
      // b must be east of pt.x
    }

    if (aX == bX) {
      return true;
    }
    double m = (aY - bY) / (aX - bX); // Rise over run
    double bee = (-aX) * m + aY; // y = mx + b
    double x = (pY - bee) / m; // algebra is neat!

    return x > pX;
}

Graehme

Answer 5

I stumbled upon this post because i wanted to solve a similar problem in my code. Unfortunatly both of the answers miss one edgecase, as well as the flutter point in poly library.

If on edge is a vertical edge, m will be Infinity. This can be avoided by also checking, if the point is to the west (or "left") of both points of the edges, because that condition will always be true for a vertical edge. This also improves performance. For fully understanding this problem I recommend this video.

Improved Code:

class Point {
  Point({required this.x, required this.y});

  /// X axis coordinate or longitude
  double x;

  /// Y axis coordinate or latitude
  double y;
}

class Poly {
  /// Check if a Point [point] is inside a polygon representing by a List of Point [vertices]
  /// by using a Ray-Casting algorithm
  static bool isPointInPolygon(Point point, List<Point> vertices) {
    int intersectCount = 0;
    for (int i = 0; i < vertices.length; i += 1) {
      if (Poly.rayCastIntersect(point, vertices[i], vertices[(i + 1)%vertices.length])) {
        intersectCount += 1;
      }
    }
    if( intersectCount != 0){
      print(intersectCount);
    }
    return (intersectCount % 2) == 1;
  }

  /// Ray-Casting algorithm implementation
  /// Calculate whether a horizontal ray cast eastward from [point] 
  /// will intersect with the line between [vertA] and [vertB]
  /// Refer to `https://en.wikipedia.org/wiki/Point_in_polygon` for more explanation
  /// or the example comment bloc at the end of this file
  static bool rayCastIntersect(Point point, Point vertA, Point vertB) {
    final double aY = vertA.y;
    final double bY = vertB.y;
    final double aX = vertA.x;
    final double bX = vertB.x;
    final double pY = point.y;
    final double pX = point.x;

    if ((aY > pY && bY > pY) || (aY < pY && bY < pY) || (aX < pX && bX < pX)) {
      // The case where the ray does not possibly pass through the polygon edge,
      // because both points A and B are above/below the line,
      // or both are to the left/west of the starting point
      // (as the line travels eastward into the polygon).
      // Therefore we should not perform the check and simply return false.
      // If we did not have this check we would get false positives.
      return false;
    }

if (aX == bX) {
  return true;
}
    if (pX < aX && pX < bX) {
      // The case where the point is to the left(west) of both points A and B,
      // So we dont need to check, because the ray will certanly intersect with the polygon edge.
      return true;
    }

    // y = mx + b : Standard linear equation
    // (y-b)/m = x : Formula to solve for x

    // M is rise over run -> the slope or angle between vertices A and B.
    double m = (aY - bY) / (aX - bX);
    // B is the Y-intercept of the line between vertices A and B
    final double b = ((aX * -1) * m) + aY;
    // We want to find the X location at which a flat horizontal ray at Y height
    // of pY would intersect with the line between A and B.
    // So we use our rearranged Y = MX+B, but we use pY as our Y value
    final double x = (pY - b) / m;

    // If the value of X
    // (the x point at which the ray intersects the line created by points A and B)
    // is "ahead" of the point's X value, then the ray can be said to intersect with the polygon.
    return x > pX;
  }
}

Alys