[FEATURE] Interactive `Polygon`s

[ibisoda]

Hi,

I'm trying to reimplement an existing Leaflet-based app using flutter. In that app, the developer used Polygons to display the outline of a building, which when clicked/tapped shows additional information. and changes the polygon.

I'm trying to replicate that function, however I noticed there is no onTap Listener, at least for Polygons. Is there a different way to listen to tap events?

[ibrierley]

Interestingly I just read that it may be possible with drawCircle and drawRect, but nothing mentioned about drawPath, so still unsure, but it obviously does a bit more than I originally thought, so may need a test with a complex shape (and maybe a poly with a hole in it too).

[JaffaKetchup]

Good points, especially about the polys with holes. There is no way a GestureDetector could be efficiently used in that case.

[aytunch]

I agree. If we were to use onTap of the whole map, can we atleast iterate through just the Polygons being rendered on the map instead of all polygons present? An optimization like this can help also. I will still look into drawPaths exact gesture detecting possibilities as it is a very interesting topic.

[ibrierley]

Looking at how others do it, they seem to add a method like the following to the CustomPainter ...

@override
  bool hitTest(Offset position) {
    bool hit = path_0.contains(position);
    return hit;
  }

https://api.flutter.dev/flutter/rendering/CustomPainter/hitTest.html
I'm not entirely sure this is the way to go, but worth a ponder...

Now, one of the things I was wondering with the Polys is whether they could have a pxCache type thing similar to the Markers optimisation, then also that cache could somehow be used so that only if its in the cache, it would have a hit test check.

I'd kinda quite like to have a separate plugin where we see how far we can optimise without needing to keep old fluff from the original, but not worry about breaking anything. (I do have something I'm working on separately that can possibly speed up polys and I intend to include hit detection, but that's probably a fair way off, so I think having some solution in the mean time is good).

[aytunch]

I found out from this SO answer that understanding if a hit occurs in a particular polygon is straight forward:

You have to override the hitTest() method of your KeyPathPainter class:

@override
bool hitTest(Offset position) {
    // _path - is the same one we built in paint() method;
    return _path.contains(position);
}

This would also solve the "hole" problem.

in our hitTest, we need to use something similar to this alogirthm from Geodesy package which even takes holes in to account

  /// check if a given geo point is in the a polygon
  /// using even-odd rule algorithm
  bool isGeoPointInPolygon(LatLng l, List<LatLng> polygon) {
    var isInPolygon = false;

    for (var i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
      if ((((polygon[i].latitude <= l.latitude) &&
                  (l.latitude < polygon[j].latitude)) ||
              ((polygon[j].latitude <= l.latitude) &&
                  (l.latitude < polygon[i].latitude))) &&
          (l.longitude <
              (polygon[j].longitude - polygon[i].longitude) *
                      (l.latitude - polygon[i].latitude) /
                      (polygon[j].latitude - polygon[i].latitude) +
                  polygon[i].longitude)) isInPolygon = !isInPolygon;
    }
    return isInPolygon;
  }

[aytunch]

Now, one of the things I was wondering with the Polys is whether they could have a pxCache type thing similar to the Markers optimisation, then also that cache could somehow be used so that only if its in the cache, it would have a hit test check.

This would be a nice optimization. But this would not cover the cases where user is viewing the whole world with all the polygons present in the map.

[aytunch]

@ibrierley as you previously mentioned about SVG's hit testing; "even-odd" is being used and the implementation does not seem to be hard. (Geodesy's code) https://en.wikipedia.org/wiki/Point_in_polygon

[JaffaKetchup]

Maybe a 3rd party package like https://pub.dev/packages/touchable could make things easier? This is also mentioned in the SO thread linked above. Not sure about its performance though?

[aytunch]

@JaffaKetchup under the hood they are using the hitTest too. It seems like a convenient package but might have more things than we need

How Touchable Works

When you draw shapes on the canvas (TouchyCanvas) , it keeps track of the dimensions of each shape you draw and their painting style , stroke , order , clippings etc.

When user performs any gesture on the screen , based on the location of the gesture , the appropriate shape is selected from the lot taking clipping regions , paint , hitTest behaviour etc into account in an optimized way. Callbacks of the corresponding shapes (one or more depending on the hitTest behavior) are executed.

[ibrierley]

Indeed...however, there's also a rendering optimisation in there also (even if all displayed)...just mentioning this, as it's worth bearing in mind, but that can always be added later.

The other thing I was thinking, was it may be possible to do an initial simple point in rect bounding box test as phase 1, then if it thats positive do a full point in poly test (and maybe only on ones that are displayed).

[ibrierley]

In fact, glancing at the code, if polygonCulling is true...I think that would remove the need for hit tests on any none displayed paths if coded in the right place (maybe) ?

[aytunch]

The other thing I was thinking, was it may be possible to do an initial simple point in rect bounding box test as phase 1, then if it thats positive do a full point in poly test (and maybe only on ones that are displayed).

One problem with this is cases as follows: The red triangle will never be able to receive touch events because the grey polygons bounding box contains red's bounding box

[aytunch]

I checked and found no way for a Widget to pass a gesture behind it in a Stack while at the same time receiving it. The only way is to use hitTest and do the path logic inside.

[ibrierley]

The other thing I was thinking, was it may be possible to do an initial simple point in rect bounding box test as phase 1, then if it thats positive do a full point in poly test (and maybe only on ones that are displayed).

One problem with this is cases as follows: The red triangle will never be able to receive touch events because the grey polygons bounding box contains red's bounding box

Sorry, I probably wasn't being clear. That would have to be done for every poly (in display), ie check if tap point is in the reds bounding box, then the grey polys box. Both would pass, so you would do further complete checks on both (but hopefully may have discarded a number of other polys in the process). (I'm away for a few days now, but will try and keep an eye on the discussion)

[JaffaKetchup]

It seems that there might be another temporary workaround, built into the standard libraries:

LatLngBounds.fromPoints([
    // polygon points
]).contains(tappedLocation)

Thanks to @yash-ahir

Note that it may be quite slow according to reports on the discord server.

[ibrierley]

tldr; https://www.youtube.com/shorts/s8GQJRqqBsw

Had a bit of time to have a play this morning with the concept of tapping polys, and how performant (or not) it could be. This is currently more of a proof of concept, there's quite a few moving parts, and not sure when I'll get chance to properly organise it all coherently into one or more packages just yet (happy to accept any help on that score).

The boring stuff...

For displaying.....drawing that many polys on top of the map is pretty intensive, so you can probably see a bit of hitching when everything is in view. That's probably for a separate issue though (note, it can do line simplification for improved performance, but there are issues if there are multiple polys adjacent as it may simplify one adjacent line and not the other, so I've left that off for US states). I'd like to try opengl one day to see out of interest, if it could be hacked in.

It uses the geojson-vt (tile slicing package) that I've converted at https://github.com/ibrierley/geojson-vt-dart (see index.dart in there for options, I'll try and document properly at some point). Currently just works with geojson (may also work with nested geometries, but you can probably just create a geojson file out of your latlong list of points).

That works, by cutting/slicing polys up into tiles. So each tile has its own set of polys, with precalculated projections, so it stores integer points, rather than latlngs etc. (depending on the depth/spread of polys, I suspect the slicing thing isn't needed, it may even be a complete redherring, I haven't decided yet).

For tapping.....what I do is detect the tap, and convert it to a tile point at a certain zoom level like 15 (even if we are at zoom 3 visually). Chances are there are only 2 or 3 polys on a specific tile at zoom 15. Then we loop over those feature/polys which are on that tile (it will need to do a bit of slicing there first time only again if its not indexed that tile before...so there may be a trade off here between whether to use the tile slicing stuff or not, depending on your polys), and do some detection using the code @aytunch posted earlier.

Flaws are, this particular method probably doesn't work so well if you have a dynamically changing set of points on the fly, as this has precalculated a lot of poly slicing, and takes a few seconds each time to calculate (if there's a lot of polys). It may also need a bit of housekeeping to free up. There's probably also a ton of bugs :D.

[JaffaKetchup]

That looks quite good! I see an acceptable amount of lag between tap and detection which was a concern. Maybe we have to have this toggle-able so that more dynamic setups don't have issues like you mentioned. Would even extending the index between app reloads help to give the illusion of faster performance every time? I think definitely to implement this we need to provide a way to convert between GeoJson and LatLngs, but that's probably not a huge job.

[ibrierley]

I've also uploaded the example to https://github.com/ibrierley/slicer_tile_example

I'm a bit unsure what to do with it all, as some of it's basic tile stuff, some is tile slicing stuff, some of its poly/drawing stuff, some is point detection stuff :).

Can't figure if they should be in some separate packages or what, as they all feel a bit separate, but also a bit related in interdepenent, will leave that for another day.

[ibrierley]

That looks quite good! I see an acceptable amount of lag between tap and detection which was a concern. Maybe we have to have this toggle-able so that more dynamic setups don't have issues like you mentioned. Would even extending the index between app reloads help to give the illusion of faster performance every time? I think definitely to implement this we need to provide a way to convert between GeoJson and LatLngs, but that's probably not a huge job.

I guess if someone has a very dynamic setup, they possibly won't have such a large set of polys (naturally someone will prove me wrong!), so maybe they just wouldn't need the whole tile slicing thing..and they could cache up the point projections (a bit like the marker pxCache?) and then run the above collision detection over that ?

[aytunch]

Looking at the provided video with all US cities, I definitely think the performance is acceptable. @ibrierley I saw that in this example none of the polygons overlap they are always neighbors. Would there be any problems with overlapping polygons when the intersection is tapped? Exceptional work btw thanks.

[ibrierley]

I don't think so. As in, ultimately, all the example is doing is looping through the geometries/polys. So theoretically, as long as you test all polys in that area in the same order (and not quit the loop on first positive test), I think the last positive test would be the one which is upper most.

Naturally, there could be some flaw I've not considered!

I don't think it should be too tricky to test, it would be good to gather some test examples for edge cases.

[ibrierley]

(or test in reverse order and quit on first hit would possibly make more sense...if I'm thinking about it all right :D).

[github-actions[bot]]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[dpalmeira]

Hi team, is there some progress on this topic? I'm working with WFS layers with 3K polygons and increasing, I need some way to handle onTap to show a pic + name + some clickable buttons (icons) in polygons when I tap on each one. Is there some way to do that? any idea or suggestion? Thank you for your excellent work!

[ibrierley]

I'm not aware of any work on it. I think this is a bit of a case of either hacking something together outside of flutter_map, like the example I linked earlier (all source code for that is there). Or, maybe I think part of the issue is finding an elegant solution for how flutter_map interfaces its gestures with the layers and plugins, as that feels a bit clunky atm.

I'm happy to try and help anyone who wants to have a stab (at either).

[t0mk]

[edit] I can see that this is same kind of solution as https://github.com/fleaflet/flutter_map/issues/385#issuecomment-1076614472.

Hey, I too needed to trigger functionality on polygon tap. I solved it in onTap handler for the map, where I get coordinates of the tap, and then I go through all the cells in my model, and return the one containing the tapped coords. Cells in my model don't overlap.

I use PolygonUtil from maps_toolkit to test if polygon contains the tapped coords.

import 'package:maps_toolkit/maps_toolkit.dart' as mp;

// in  MapOptions.onTap: (tapPosition, point) 
  cell = model.FindCointainingCell(tapPosition);

// and the method in the model is:

class MyModel {
  List<Cell> cells = [];

  Cell? findContainingCell(LatLng point) {
    final mpPoint = mp.LatLng(point.latitude, point.longitude);
    for (var cell in cells) {
      final mpPolygon =
          cell.points.map((c) => mp.LatLng(c.latitude, c.longitude)).toList();
      if (mp.PolygonUtil.containsLocation(mpPoint, mpPolygon, false)) {
        return cell;
      }
    }
    return null;
  }

When I have the cell/polygon containing the tapped coords, I can use it to run methods (popup) with parameters of the clicked cell.

It's quite naive and brute-force, but it's also simple. I hope this helps someone who needs onTap for polygons.

[allasca]

@t0mk did you try 1000 polygons? and how the performance on brute? thanks in advance. will try your code soon.

[github-actions[bot]]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[t0mk]

@allasca I actually changed my solution a bit. I don't use geneal polygons, but hexagons from Uber H3 (1d geospatial index https://h3geo.org/). In H3, the area of earth is split to hierarchical hexagons, and each hexagon has an ID, usually written in hexadecimal. It's like geohash, but hexagons.

The H3 lib defines mapping between (longitude, latitude, h3_resolution) and cell ID, so I just keep Map<BigInt,Cell> cells, and when I process click, I just do a lookup in the map, based on the lon,lat from the onTap handler. I use https://pub.dev/packages/h3_flutter

  Cell? findContainingCell(LatLng point) {
    final pnt = GeoCoord(lon: point.longitude, lat: point.latitude);
    var h3cell = h3.geoToH3(pnt, h3res);
    return cells[h3cell];
  }

It's quite specific solution, so I'm not sure if this is helpful. I basically took advantage of specific features of the polygons that I use.

[idipak]

So far I have got this. Please suggest some better way.

for(final polygon in samplePolygons){
                    if(LatLngBounds.fromPoints(polygon.points).contains(location)){
                      //Perform some operation
                      break;
                    }
                  }

[iulian0512]

bump

[ibrierley]

Have you tried the solutions above ?

[iulian0512]

Have you tried the solutions above ?

i guess you meant workarounds, answer is no.

[yash-ahir]

So far I have got this. Please suggest some better way.

for(final polygon in samplePolygons){
                    if(LatLngBounds.fromPoints(polygon.points).contains(location)){
                      //Perform some operation
                      break;
                    }
                  }

Hello, I changed around some things on line 44 of https://github.com/ibrierley/geojson_vector_slicer/blob/main/lib/geojson/geojson.dart by @ibrierley to work with LatLng and Polygon, here's the code:

bool isPointInPolygon(LatLng point, Polygon polygon) {
  double x = point.latitude, y = point.longitude;

  bool inside = false;

  for (var i = 0, j = polygon.points.length - 1;
      i < polygon.points.length;
      j = i++) {
    var xi = polygon.points[i].latitude, yi = polygon.points[i].longitude;
    var xj = polygon.points[j].latitude, yj = polygon.points[j].longitude;

    var intersect =
        ((yi > y) != (yj > y)) && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);

    inside = intersect ? !inside : inside;
  }

  return inside;
}

This works better than the old LatLngBounds.fromPoints(...).contains(...) because that method has problems with edge detection, you can test this by putting two triangle shaped polygons on diagonals of a square area and clicking on each of them, you'll see if you click on an area in the center which even if it's outside both the triangles, would still trigger the .contains method on both of them, I'm not an expert and not sure why this happens but it just happened when I was testing that method.

[github-actions[bot]]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[github-actions[bot]]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[github-actions[bot]]

This issue was closed because it has been stalled for 5 days with no activity.

[github-actions[bot]]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[pablojimpas]

Is there any chance we will see this implemented before the v4 release? This is the oldest open issue and the one with most comments right now.

[JaffaKetchup]

cc @ibrierley was monitoring this AFAIK. But it's unlikely: there's a lot of technical hurdles dealing with overlapping and complex polygons - happy to include it if it is ready before release!

[b-cancel]

@JaffaKetchup @ibrierley @pablojimpas I read through everything and it seems like using GEODESY is the solution here https://pub.dev/packages/geodesy

@neokree & @MichalMisiaszek have even implemented their own version of it

HOWEVER I was wondering, is there a reason why nobody has added an optimization step to it? it would take up more space but I think we care about speed here more than anything

all you would need to do is loop through the polygons get the lat and lng bounds then before running the even odd algorithm (what geodesy uses and what @neokree & @MichalMisiaszek have implemented) filter out polygons that don't contain the point within their bounds

this way unless we are dealing with highly overlapping polygons performance isn't an issue regardless of how many polygons we are dealing with

and furthermore... do you @ibrierley or anyone else still have a functional map with tons of polygons drawn on it to test this?

I can have it ready in the next couple hours

[JaffaKetchup]

@b-cancel Thanks for popping in! We're certainly still interested in contributions for this. Just to note, I'm not sure including the entire 'geodesy' library is a good idea - there's a lot of conflicts with things already provided by 'latlong2', and ll2 provides some fundamentals through the Distance() object (which does handle more than just distance). I'm sure we can boil it down after an initial implementation though, so don't worry too much.

In terms of a polygon test page, @ignatz (sorry for the ping), but as you've been putting together a lot of polygon optimizations recently, do you have a testing page with loads of polygons? No worries if not. (I think @ibrierley might have one with the US states as polygons, if it's not already linked above and he hasn't deleted it. He might even have this optimization in one of his plugins, but I'm not sure.)

[b-cancel]

@JaffaKetchup yeah I'm just trying to get this working y'all can always make your own version of the points in polygon algorithm to make this work without geodesy

but I figure I trying and point people to resources by taking a more data science approach I found this article that solves our exact problem https://www.matecdev.com/posts/point-in-polygon.html and this one that explains the limits of the points in polygon algorithm https://saturncloud.io/blog/point-in-polygon-algorithm-explanation/ and this one that explains a simpler version of the optimization https://www.baeldung.com/cs/geofencing-point-inside-polygon

I'll be implementing my own version of this soon an then whoever would like can add it to the library or simply use it as is this is a fairly popular issue so I'm trying to help since I already need to solve this myself

[b-cancel]

Solution Explanation

Geodesy uses the even odd "point in polygon" algorithm https://en.wikipedia.org/wiki/Point_in_polygon it's runtime is O(n) where n is the number of edges

since we are checking if our "tap" is within any of the polygons our runtime is then O(number of edges in polygon 1) + O(number of edges in polygon 2) + ...

which for the sake of simplicity I'm summarizing as a O(n*m) algorithm

• n is the number of polygons
• m is the average amount of edges amongst all of our polygons which is... not great

The Optimization Step

First we make sure that the point is within the polygons axis aligned bounding box that check takes at most 4 steps so this optimization is at most O(4*n) or just O(n) where n is the number of polygons

that will reduce the number of polygons that we are including in the points in polygon algorithm by a HUGE margin so the algorithm is still O(n*m) but n is MUCH smaller (under practical applications)

this optimization should be more than enough for most cases

without: O(n*m)

• n is the number of polygons
• m is the average amount of edges amongst all of our polygons

with: O(n) + O(n2*m2)

• n is the number of polygons
• n2 is the number of polygons that have the point in their axis aligned bounding box
• m2 is the average number of edges for polygons from set n2 n2 will be MUCH smaller than n in practical applications

To Optimize further

data scientist have used R-tree s https://en.wikipedia.org/wiki/R-tree which essentially groups bounding boxes so that you can eliminate entire bounding box groups by using the tree of course this method has even more trade offs and nuances so I'll leave it there

My Implementation... coming soon...

this is secondary to my primary goal so I probably won't go as far as implementing the R-tree unless I really have to

BUT https://github.com/ibrierley seems to have created a map of the US that I'll be using for my own test as I build out my solution

[ignatz]

@JaffaKetchup no worries, always happy to help.

I'm happy to comment especially since I've solved this problem for myself basically doing what's proposed here: identifying candidate polygons first and then applying a more sophisticated polygon algorithm. In practice, performance is a non-concern even for hundreds of thousands of polygons (FWYW, my app has some 22k airspace polygons, happy to share more details). In essence, when I drop frames (which I do quite regularly) it's pretty much always due to raster performance especially since we raster on every frame (as opposed to leaflet which rasters once and then pans/scales the result and only re-rasters on move-end). The majority of my optimizations were focused on reducing raster times, e.g. minimizing the number of GPU draws. Hardly ever am I bottlenecked by the UI thread and even then, an on-tap handler will only run when the user taps and when the user taps they don't usually pan or zoom.... TL;DR: don't worry too much about performance here...

Going more into detail on the proposal to use https://en.wikipedia.org/wiki/Point_in_polygon... that's actually how I started out as well. Computationally, the ray casting approach is super cheap. However, I found it to be maybe too cheap :). For some of my more complex polygons I had a lot of false-positives. Theoretically you can cast more rays and thus reduce the chances of false positives.... but that would be too simple. I ultimately ended up spending too much time on making https://pub.dev/packages/polybool dart3 worthy and that's what I'm using today.

I've never encountered a false-positive/negative and I never felt that it was computationally too expensive for tops a hand full of candidate polygons during an on-tap user event...

If someone wants to provide a most-importantly reliable horizontal on-tap polygon solution, I'm more than happy to throw my solution away.

(One thing a horizontal solution will also have to deal with (which certainly isn't a bit deal at least using the polybool algorithm) is holes.)

[ibrierley]

The long term solution is probably best with an R-tree or something similar like a quadtree. Essentially this is what https://github.com/ibrierley/geojson_vector_slicer does behind the scenes (tilecheck, which is kind of a quadtree). The downside with some of these solutions (and why I haven't suggested including in the core) is that they can be hard to maintain.

Equally the same principle can be kind of applied to everything, polygons, polylines, markers etc. So do we want a separate optimisation for just polys, or potentially used by everything somehow (I've never come up with a good generic solution for it). Worth bearing in mind.

In the interim, I think any optimisation is a worth goal here, especially if it's easy to follow and adapt. Edit: Just read what ignatz says and pretty much agree, but sometimes a vast amount of polys can cause issues, why maybe there's no one solution fits all sometimes.

[JaffaKetchup]

~Ah, thanks @ignatz, I've been meaning to put polybool in the docs somewhere, but couldn't find it again (didn't know it belonged to you).~ EDIT: Just realised my mistake here, ignore me. Already had it in the docs.

In terms of performance, the solutions I've seen took a while to determine the correct polygon - however, I now realize that may have been to do with something I 'fixed' in #1532, where the double tap gesture delayed receipt of the single tap gesture for 250ms (now, if you specify to disallow the double tap gesture, there is no delay). So maybe we need to double check this.

I wonder, would it help to triangulate the polygons? This would help with handling holes (as @ignatz mentioned is a pain point), and from my basic understanding, this is one step of many algorithms anyway. If so, I just so happened to have recently ported a very performant triangulation library to Dart: https://pub.dev/packages/dart_earcut. Interestingly, the original came from the mapbox org - interesting loop back to mapping there :D. ~I wonder how that might fit into FMTC?~

[ignatz]

Ah, thanks @ignatz, I've been meaning to put polybool in the docs somewhere, but couldn't find it again (didn't know it belonged to you).

It doesn't. It was someones 1:1 javascript to dart robo conversion, which didn't care much for nullability. Unfortunately, the owner has admitted to not be comfortable touching the implementation and only maintains the project's README. So I just spend some non-trivial amount of time going through the entire implementation. In the process I did some research and credit goes to:

• polybooljs by velipso@, which is based on
• polybool actionscript by akavel@, which is based on
• an implementation by Mahir Iqbal, which is based on
• F. Martinez' (2008) algorithm (Paper)

If you wanted to go down the polybool route, which I'd be careful with*, I would consider at least forking the code.

(* mostly regarding the state of the project. The algorithm itself is pretty rad and battle tested)

I wonder, would it help to triangulate the polygons? This would help with handling holes (as @ignatz mentioned is a pain point), and from my basic understanding, this is one step of many algorithms anyway. If so, I just so happened to have recently ported a very performant triangulation library to Dart: https://pub.dev/packages/dart_earcut. Interestingly, the original came from the mapbox org - interesting loop back to mapping there :D. I wonder how that might fit into FMTC?

Sorry, I didn't want to make it sound like a huge problem (that's why I put it in parenthesis). I just didn't care for it myself, since airspaces typically don't have holes. With polybool, this can be trivially handled as a set-operation. I'm sure the raycasting can account for it too by running both on the hull and the holes separately.

The long term solution is probably best with an R-tree or something similar like a quadtree. Essentially this is what https://github.com/ibrierley/geojson_vector_slicer does behind the scenes (tilecheck, which is kind of a quadtree). The downside with some of these solutions (and why I haven't suggested including in the core) is that they can be hard to maintain.

I've implemented plygon/marker culling with r-trees before. It felt more worthwhile since culling runs on every frame (unlike on-tap) but in practice it wasn't worth it for me... maybe if you have orders of magnitude, i.e. 1 millions, more objects :shrug:. For more common numbers the impact is more likely to be negative.

[JaffaKetchup]

So I just spend some non-trivial amount of time going through the entire implementation

:D

---

I honestly am not sure what to do here (ping @TesteurManiak @mootw). Leaving it for a plugin is a good way to allow for a massive, performant implementation. Adding to core means more users more happy more quicker.

We can see how @b-cancel's solution works. @ignatz, would you mind sharing your implementation in some way?

[ignatz]

I honestly am not sure what to do here (ping @TesteurManiak @mootw). Leaving it for a plugin is a good way to allow for a massive, performant implementation. Adding to core means more users more happy more quicker.

Sorry, if I caused confusion. I was trying to say:

1. I'd love an onTap handler if it fits my needs
2. Don't worry about performance
3. Worry about accuracy and make sure to test with weirdly shaped polygons

Any algorithm/implementation that meets #3 will do. I do like the polybool algorithm because I haven't encountered any false postives/negatives and I'm probably also suffering from a good amount of Stockholm syndrome.

@ignatz, would you mind sharing your implementation in some way?

I'm not very protective, I just haven't gotten around to open sourcing it plus a few quirks. I pulled out and cleaned up the relevant part, which is just as straight forward as you'd expect:

List<Polygon> findPolygonCollisions(
  FlutterMapState map,
  List<Polygon> polygons,
  CustomPoint<double> point,
) {
  final latlng = map.pointToLatLng(point)!;

  final hits = <Polygon>[];
  for (final polygon in polygons) {
    // First do a quick pass on the rough bounding box envelope to find candidate hits.
    final bounds = LatLngBounds.fromPoints(polygon.points);
    if (bounds.contains(latlng)) {
      final coordinates = 
          polygon.points.map((c) => polybool.Coordinate(c.longitude, c.latitude)).toList()
      // NOTE: Polybool requires polygons to be closed loops, i.e.: c.first == c.last.
      if (coordinates.first != coordinates.last) {
        coordinates.add(coordinates.first);
      }
      final p = polybool.Polygon(regions: [coordinates]);

      const eps = 1e-7;
      final touch = polybool.Polygon(regions: [
        [
          polybool.Coordinate(latlng.longitude, latlng.latitude),
          polybool.Coordinate(latlng.longitude + eps, latlng.latitude),
          polybool.Coordinate(latlng.longitude + eps, latlng.latitude + eps),
          polybool.Coordinate(latlng.longitude, latlng.latitude + eps),
          polybool.Coordinate(latlng.longitude, latlng.latitude),
        ]
      ]);

      final match = p.intersect(touch).regions.isNotEmpty;
      if (match) {
        hits.add(polygon);
      }
    }
  }
  return hits;
}

Note that I'm returning a list of hits, since polygons are over-lapping and I want to show a list of stacked airspaces under the tap area. More traditionally, a on-tap handler would probably only handle hits.last, i.e. the top-most of the overlapping polygons.