search

google / s2-geometry-library-java

Automatically exported from code.google.com/p/s2-geometry-library-java
Apache License 2.0
533 stars 230 forks source link

Request for Guidance - Point in Polygon and S2 #5

Open Brahmasmi opened 7 years ago

Brahmasmi commented 7 years ago

Would it be possible for the good folks here to please help me with a problem that I am trying to solve with the S2 geometry library? I am a complete novice, so please bear with me if I do not make sense.

Problem I am trying to determine the best way to write an offline point-in-polygon check for the Android platform. Essentially, convert (lat,lng) to a country. In future, I plan to increase the granularity to regions, states, provinces, counties and cities/towns.

Research My initial research landed me up on https://github.com/AReallyGoodName/OfflineReverseGeocode with http://download.geonames.org/export/dump/cities1000.zip. From what I understand, this is (lat,lng) to nearest neighbor. Now, I do get the country from this, but it relies on finding the nearest neighbor city with population, which may not be accurate.

Further research led me to S2. It is here that I am struggling, and request your guidance.

Current Approach A) Computation at app startup: 1) Get geojson co-ordinates from http://download.geonames.org/export/dump/shapes_simplified_low.zip. 2) For each country, i) Convert geojson co-ordinates into S2 LatLng and then S2 Loops. ii) Build S2 Polygon using S2 Loops. iii) If MultiPolygon, use S2PolygonBuilder.addPolygon() to add additional polygons.

B) LatLng input during app functioning: 1) Convert Lat Lng Input to S2Point. 2) Iterate over country polygons, checking for S2Polygon.contains(S2Point). 3) Return country.

Questions 1) Some geojson countries are "multipolygon", whereas there is no multipolygon in S2. Are S2 polygons equivalent to multipolygons from geojson? 2) Can the geojson to S2Polygon initial computation result be persisted, to avoid re-computation at app startup? 3) Geonames geojson input does not seem to conform to counter clockwise (CCW) convention. Would S2PolygonBuilder be able to tackle this correctly? 4) Is there a better way to search for point-in-polygon rather than iterating over each countries S2Polygons.contains function call? Does this mechanism also help avoid polygon re-computation? 5) Is there a better way to achieve the offline point-in-polygon check? 6) Is there a better (small, accurate) source for country boundaries for use with S2?

Thank you for your time.

@eengle @hagbard @kluever @cpovirk

eengle commented 7 years ago

Some answers:

  1. The S2Polygon is a suitable multipolygon if you know the parts have no overlap. Otherwise you can use initToUnion to combine them, or just keep multiple polygons per country in your data structure.
  2. This is up to you. I'd expect most of the runtime is parsing json and converting to xyz S2Points, so saving S2Loops instead of the original strings would probably improve startup time.
  3. An easier way to handle orientation might be to add all points to an S2Loop, and then call S2Loop.normalize(). That will reorient the loop if it looks to be too large (but be careful if you could have loops that really should be >half the world area!)
  4. You could always build an index by creating e.g. the S2Cells at level 4, joining country polygons to each cell they touch, and then storing the part of each country in each cell via S2Polygon.initToIntersect(). Then you could eliminate most polygons by first finding which index cell contains your query point. This could radically improve performance, but is a little fancy to implement.
  5. Another popular speedup is to use S2RegionCoverer to generate inner coverings of each polygon. You can easily store these and load them first, instead of the entire polygon. Then you can test if the resulting S2CellUnion contains your point. If it does, then the polygon certainly does. When it doesn't, you still have to load and do an exact polygon test, but this can be a large speedup unless queries are usually close to the boundary. So you can think of an inner covering sort of like a bounding box.
  6. Well, if it's small it won't be accurate, but political territories are a somewhat fraught topic, so I can't really recommend one option over the others. Also license issues about, so be careful that you're using data in a permitted way. That said, gadm.org has administrative boundaries too, and you can always simplify the dataset if it's too complicated to begin with.

Best regards,

On Thu, Mar 16, 2017 at 2:58 PM, Brahmasmi notifications@github.com wrote:

Would it be possible for the good folks here to please help me with a problem that I am trying to solve with the S2 geometry library? I am a complete novice, so please bear with me if I do not make sense.

Problem I am trying to determine the best way to write an offline point-in-polygon check for the Android platform. Essentially, convert (lat,lng) to a country. In future, I plan to increase the granularity to regions, states, provinces, counties and cities/towns.

Research My initial research landed me up on https://github.com/AReallyGoodName/ OfflineReverseGeocode with http://download.geonames.org/ export/dump/cities1000.zip. From what I understand, this is (lat,lng) to nearest neighbor. Now, I do get the country from this, but it relies on finding the nearest neighbor city with population, which may not be accurate.

Further research led me to S2. It is here that I am struggling, and request your guidance.

Current Approach A) Computation at app startup:

  1. Get geojson co-ordinates from http://download.geonames.org/ export/dump/shapes_simplified_low.zip http://download.geonames.org/export/dump/shapes_simplified_low.zip.
  2. For each country, i) Convert geojson co-ordinates into S2 LatLng and then S2 Loops. ii) Build S2 Polygon using S2 Loops. iii) If MultiPolygon, use S2PolygonBuilder.addPolygon() to add additional polygons.

B) LatLng input during app functioning:

  1. Convert Lat Lng Input to S2Point.
  2. Iterate over country polygons, checking for S2Polygon.contains(S2Point).
  3. Return country.

Questions

  1. Some geojson countries are "multipolygon", whereas there is no multipolygon in S2. Are S2 polygons equivalent to multipolygons from geojson?
  2. Can the geojson to S2Polygon initial computation result be persisted, to avoid re-computation at app startup?
  3. Geonames geojson input does not seem to conform to counter clockwise (CCW) convention. Would S2PolygonBuilder be able to tackle this correctly?
  4. Is there a better way to search for point-in-polygon rather than iterating over each countries S2Polygons.contains function call? Does this mechanism also help avoid polygon re-computation?
  5. Is there a better way to achieve the offline point-in-polygon check?
  6. Is there a better (small, accurate) source for country boundaries for use with S2?

Thank you for your time.

@eengle https://github.com/eengle @hagbard https://github.com/hagbard @kluever https://github.com/kluever @cpovirk https://github.com/cpovirk

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/google/s2-geometry-library-java/issues/5, or mute the thread https://github.com/notifications/unsubscribe-auth/ADgwAcZ-n6m1RqcctcFHcVuyrj_QB-NBks5rmbBvgaJpZM4Mf7pu .