0

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?

Luke Pighetti
  • 109
  • 3
  • This is a proximity analysis. What GIS software are you using? – PolyGeo Dec 31 '20 at 00: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. – Luke Pighetti Dec 31 '20 at 01: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 Dec 31 '20 at 06:06
  • 1
    This is a simple point in polygon test, there are many implementations out there – Ian Turton Dec 31 '20 at 09: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. – Luke Pighetti Dec 31 '20 at 11:12
  • Hi everyone. Using bounding boxes was an easy addition to the even-odd algorithm and reduced search time in my situation from 1,550ms to 120ms. That's without caching the bounding boxes. Thanks for the help. – Luke Pighetti Jan 01 '21 at 18:26

0 Answers0