fluttergoogle-mapspolygongoogle-maps-flutter

How to define self-intersection of polygon in google maps (flutter)


I am making an application in which the user can draw a polygon on a map by points. I need to somehow make sure that the polygon does not have self-intersections. I know it is possible to manually check each line. There are various methods for this. But I noticed that Google Maps automatically fills polygons that do not have self-intersections. Is it possible to get this value from the plugin somehow?

i am using google_maps_flutter

without self-intersection

with self-intersection


Solution

  • Perhaps this will be useful to someone. I did not find a built-in function in the plugins listed in the question. So I wrote my own function:

    true - there are self-intersections

    bool isNotSimplePolygon(List<LatLng> polygon){
      if(polygon.length <= 3)
        return false;
    
      for(int i = 0; i < polygon.length - 2; i++){
        double x1 = polygon[i].latitude;
        double y1 = polygon[i].longitude;
        double x2 = polygon[i + 1].latitude;
        double y2 = polygon[i + 1].longitude;
    
        double maxx1 = max(x1, x2), maxy1 = max(y1, y2);
        double minx1 = min(x1, x2), miny1 = min(y1, y2);
    
        for (int j = i + 2; j < polygon.length; j++) {
          double x21 = polygon[j].latitude;
          double y21 = polygon[j].longitude;
          double x22 = polygon[(j + 1) == polygon.length ? 0 : (j + 1)].latitude;
          double y22 = polygon[(j + 1) == polygon.length ? 0 : (j + 1)].longitude;
    
          double maxx2 = max(x21, x22), maxy2 = max(y21, y22);
          double minx2 = min(x21, x22), miny2 = min(y21, y22);
    
          if ((x1 == x21 && y1 == y21) || (x2 == x22 && y2 == y22) || (x1 == x22 && y1 == y22) || (x2 == x21 && y2 == y21))
            continue;
    
          if (minx1 > maxx2 || maxx1 < minx2 || miny1 > maxy2 || maxy1 < miny2)
            continue;  // The moment when the lines have one common vertex...
    
    
          double dx1 = x2-x1, dy1 = y2-y1; // The length of the projections of the first line on the x and y axes
          double dx2 = x22-x21, dy2 = y22-y21; // The length of the projections of the second line on the x and y axes
          double dxx = x1-x21, dyy = y1-y21;
    
          double div = dy2 * dx1 - dx2 * dy1;
          double mul1 = dx1 * dyy - dy1 * dxx;
          double mul2 = dx2 * dyy - dy2 * dxx;
    
          if (div == 0)
            continue; // Lines are parallel...
    
          if (div > 0) {
            if (mul1 < 0 || mul1 > div)
              continue; // The first segment intersects beyond its boundaries...
            if (mul2 < 0 || mul2 > div)
              continue; // // The second segment intersects beyond its borders...
          }
          else{
            if (-mul1 < 0 || -mul1 > -div)
              continue; // The first segment intersects beyond its boundaries...
            if (-mul2 < 0 || -mul2 > -div)
              continue; // The second segment intersects beyond its borders...
          }
          return true;
        }
      }
      return false;
    }