Geofencing multiple polygons for a single point

[lukepighetti]

I have found it very easy to filter a list of points using a geofence with geojson. Works great!

Unfortunately, my use case is trying to tell a user which geofence they are in. That means one point and multiple geo polygons. Best I've found so far is to search each geo polygon individually for the point using the filtering feature and see which one returns first.

Is there a better way to figure out which geofence a specific point is located in? We're seeing about a 0.8 second calculation time on a 27" iMac and we'd obviously like to bring that way down.

Is there a recommended way to achieve this with performance in mind?

[lukepighetti]

This is the best I've got

extension GeoFenceGeoJsonX on GeoJson {
  Future<GeoJsonFeature> findGeofence(
      GeoJsonFeatureCollection geofences, GeoJsonPoint query) async {
    final futures = [
      for (var geofence in geofences.collection)
        () async {
          final results = await geofencePolygon(
            polygon: geofence.geometry,
            points: [query],
          );

          /// No results
          if (results.isEmpty) return null;

          /// Found a result
          if (results.first.name == query.name) return geofence;
        }(),
    ];

    return Stream.fromFutures(futures)
        .firstWhere((e) => e != null)
        .catchError((e) => null);
  }
}

[lukepighetti]

This is taking about 9 seconds on a physical device (iPhone 8+, debug mode).

There must be a faster way to figure out which geofence covers a given point than what I'm doing. Is there anything we can do in geojson to speed this up? If you can help me put together a plan I can try to execute a PR over the next couple days.

wmd-50m.json.zip

This point is in bounds of feature polygon with properties['IDENTIFIER'] == 26.

GeoJsonPoint(
  name: 'bangor',
  geoPoint: GeoPoint(
    latitude: 44.801613,
    longitude: -68.771225,
  ),
);

[lukepighetti]

In profile mode it drops down to 0.20 seconds, but I'd like to think we can do a lot better.

[lukepighetti]

Somewhat related, I'm also getting errors when trying to launch in debug mode now. Might need a new issue but since it's related to this it might be fine to leave it in here for now.

Exhausted heap space, trying to allocate 298832 bytes.
../../third_party/dart/runtime/vm/object.cc: 2618: error: Out of memory.
../../third_party/dart/runtime/vm/thread_pool.cc: 299: error: Could not start worker thread: result = 35.

[lukepighetti]

Just poking around and I found reference to a super interesting strategy where you pre-compute the bounding boxes of all the geofence polygons. Then you geofence those, and if there's any overlap you do an even-odd on the multiple results. If I can find a quick way to do this then my code above should be significantly faster.

[lukepighetti]

Just a quick note, I have some rudimentary benchmarks that are of interest. iMac 27" debug mode.

Loading file (1.7mb, 40 polygons): 228ms
Generating bounding boxes (n=40): 12ms (!)
Geofencing polygons (n=40): 1,373ms

Assuming:

• geofencing is linear time
• the average number of overlapping bounding boxes is 2
• we generate bounding boxes on the fly without any caching

We should be able to reduce this search time from 1,385ms to 80ms. That's an improvement of 17:1 in this specific use case. This improved search should be doable as a utility method on the GeoJson class which should provide very reasonable performance for many cases.

[lukepighetti]

How I'm generating bounding boxes:

final boundingBoxes = <int, GeoRect>{};

for (var geofence in geofences) {
  final wmdNumber = geofence.wmdNumber;

  double maxLat;
  double minLat;
  double maxLong;
  double minLong;

  for (var geoSerie in geofence.geometry.geoSeries) {
    for (var geoPoint in geoSerie.geoPoints) {
      final lat = geoPoint.latitude;
      final long = geoPoint.longitude;

      /// Make sure they get seeded if they are null
      maxLat ??= lat;
      minLat ??= lat;
      maxLong ??= long;
      minLong ??= long;

      /// Update values
      if (maxLat < lat) maxLat = lat;
      if (minLat > lat) minLat = lat;
      if (maxLong < long) maxLong = long;
      if (minLong > long) minLong = long;
    }
  }

  boundingBoxes[wmdNumber] = GeoRect(
    minLat: minLat,
    maxLong: maxLong,
    maxLat: maxLat,
    minLong: minLong,
  );
}

class GeoRect {
  GeoRect({
    @required this.maxLat,
    @required this.maxLong,
    @required this.minLat,
    @required this.minLong,
  });

  final double maxLat;
  final double maxLong;
  final double minLat;
  final double minLong;

  bool contains(double lat, double long) {
    final containsLat = maxLat >= lat && minLat <= lat;
    final containsLong = maxLong >= long && minLong <= long;
    return containsLat && containsLong;
  }

  @override
  String toString() => 'GeoRect($minLat,$minLong,$maxLat,$maxLong)';
}

[lukepighetti]

Logs from a comparison between the optimized method and the naiive method. This is a 1.7mb geojson file and 40 polygons on an iMac 27" debug mode.

finished reading file 237ms
finished bounding boxes 10ms
finished filtering boxes search, found 1: 5ms
finished filtering geofences 0ms

finished optimized geofence search 93ms
bangor is in WMD #26

finished naiive geofence search 1404ms
bangor is in WMD #26

[lukepighetti]

Here's the final generalized solution as an extension on GeoJson.

Full test coverage available here: https://gist.github.com/lukepighetti/442fca7115c752b9a93b025fc04b4c18

import 'package:flutter/foundation.dart';
import 'package:geojson/geojson.dart';

extension GeoJsonSearchX on GeoJson {
  /// Given a list of polygons, find which one contains a given point.
  ///
  /// If the point isn't within any of these polygons, return `null`.
  Future<List<GeoJsonFeature<GeoJsonPolygon>>> geofenceSearch(
    List<GeoJsonFeature<GeoJsonPolygon>> geofences,
    GeoJsonPoint query,
  ) async {
    final boundingBoxes = getBoundingBoxes(geofences);

    final filteredGeofences = [
      for (var box in boundingBoxes)
        if (box.contains(query.geoPoint.latitude, query.geoPoint.longitude))
          box.feature
    ];

    return await _geofencesContainingPointNaive(filteredGeofences, query);
  }

  /// Return all geofences that contain the point provided.
  ///
  /// Naive implementation. The geofences should be filtered first using a method such
  /// as searching bounding boxes first.
  Future<List<GeoJsonFeature<GeoJsonPolygon>>> _geofencesContainingPointNaive(
    List<GeoJsonFeature<GeoJsonPolygon>> geofences,
    GeoJsonPoint query,
  ) async {
    final futures = [
      for (var geofence in geofences)
        geofencePolygon(
          polygon: geofence.geometry,
          points: [query],
        ).then((results) {
          /// Nothing found
          if (results.isEmpty) return null;

          /// Found a result
          if (results.first.name == query.name) return geofence;
        })
    ];

    final unfilteredResults = await Future.wait(futures);
    return unfilteredResults.where((e) => e != null).toList();
  }

  /// Given a set of geofence polygons, find all of their bounding boxes, and the index at which they were found.
  List<GeoBoundingBox> getBoundingBoxes(
      List<GeoJsonFeature<GeoJsonPolygon>> geofences) {
    final boundingBoxes = <GeoBoundingBox>[];

    for (var i = 0; i <= geofences.length - 1; i++) {
      final geofence = geofences[i];

      double maxLat;
      double minLat;
      double maxLong;
      double minLong;

      for (var geoSerie in geofence.geometry.geoSeries) {
        for (var geoPoint in geoSerie.geoPoints) {
          final lat = geoPoint.latitude;
          final long = geoPoint.longitude;

          /// Make sure they get seeded if they are null
          maxLat ??= lat;
          minLat ??= lat;
          maxLong ??= long;
          minLong ??= long;

          /// Update values
          if (maxLat < lat) maxLat = lat;
          if (minLat > lat) minLat = lat;
          if (maxLong < long) maxLong = long;
          if (minLong > long) minLong = long;
        }
      }

      boundingBoxes.add(GeoBoundingBox(
        feature: geofence,
        minLat: minLat,
        maxLong: maxLong,
        maxLat: maxLat,
        minLong: minLong,
      ));
    }

    return boundingBoxes;
  }
}

class GeoBoundingBox {
  /// A geographical rectangle. Typically used as a bounding box for a polygon
  /// for fast search of point-in-multiple-polygon.
  GeoBoundingBox({
    @required this.feature,
    @required this.maxLat,
    @required this.maxLong,
    @required this.minLat,
    @required this.minLong,
  });

  /// The polygon bounded by this bounding box
  final GeoJsonFeature<GeoJsonPolygon> feature;
  final double maxLat;
  final double maxLong;
  final double minLat;
  final double minLong;

  double get left => minLat;
  double get top => maxLong;
  double get right => maxLat;
  double get bottom => minLong;

  bool contains(double lat, double long) {
    final containsLat = maxLat >= lat && minLat <= lat;
    final containsLong = maxLong >= long && minLong <= long;
    return containsLat && containsLong;
  }

  @override
  String toString() => 'GeoRect($minLat,$minLong,$maxLat,$maxLong)';
}

[lukepighetti]

If you'd like this as a PR, just let me know.

[lukepighetti]

One more note: if only one bounding box is found I believe we can say with 100% confidence that a final search will yield the same result. That means that we could technically skip the final search. In other words, you only need to do the even-odd search if the point is within multiple bounding boxes. I left it naive as I wanted to makes sure we were always doing a final check against the raw polygons, even though mathematically there should be no reason why you'd do this.

[synw]

Hi, thanks for this research. The bounding box check is smart as the geofencing in polygons is expensive yes. It could be good to have this in the lib yes to speed up things, maybe as an option. That said I must find the time to update this lib first, merge some PRs and update dependencies

[lukepighetti]

As it is, anyone can copy paste that extension into their project and get this feature, so until you're ready for a PR that can be an acceptable solution imho.

[lukepighetti]

I have full test coverage for this feature now. Just ping me whenever you're ready for a PR. I updated the previously posted source to match my latest tested code. I posted test coverage here: https://gist.github.com/lukepighetti/442fca7115c752b9a93b025fc04b4c18

Also, you cannot skip the even-odd search if you only get one bounding box. Consider the scenario where a point is within the bounding box, but not within the polygon.