Consider a scenario where you have polygons representing the border of every country in Europe. You also have the Lat/Long of a user's mobile device. You now want to display which country that user is currently located in.

In essence, you have multiple polygons and a single point, and you'd like to find the polygon that contains that point.

Point-in-polygon algorithms are well known, but what are some strategies to reduce the search time?

  • This is a proximity analysis. What GIS software are you using?
    – PolyGeo
    Commented Dec 31, 2020 at 0:09
  • I'm doing this by hand starting with a geojson file. This is on a mobile device and I will probably have to write it from scratch due to lack of packages to assist. The current method is to grab every polygon and do an even-odd analysis to see if the point is inside the bounds. As implemented it is very time consuming. My thoughts are to find the closest polygon first, then test it for geofencing with even-odd. Commented Dec 31, 2020 at 1:18
  • 2
    If you do a simple envelope check, you won't have to test every geometry. That said, reinventing this particular wheel is a huge waste of time. Code libraries is the only way to fly here.
    – Vince
    Commented Dec 31, 2020 at 6:06
  • 1
    This is a simple point in polygon test, there are many implementations out there
    – Ian Turton
    Commented Dec 31, 2020 at 9:01
  • Just to reiterate the particular tooling I'm using for this mobile app doesn't have access to any geoquery libraries that are robust and performant. Best idea I've found, which was also confirmed by @Vince, is to test envelopes first (bounding boxes), get a list of overlapping boxes, then test their corresponding geometries. Will be implementing that today. Commented Dec 31, 2020 at 11:12


Browse other questions tagged or ask your own question.