5

I'm hoping someone can point me in the right direction.

We have millions of records flowing/streaming through where we need to do a quick lookup to determine which country polygon they fall into.

Could someone recommend a complete JAVA based approach to do this. From what I can tell I would use JTS and/or geotools? My thoughts are to take all of the country polygons and possibly split them up using like a FishNet or Grid to make them smaller for better performance. I would then load these into a java based in-memory spatial index...As the records stream through I would do a lookup into the java spatial index to see what country they fall into. (Maybe like a Spatial Feature collection).

Does this approach sound resonable for lots of data? From a java standpoint how would I implement this? Is this just using JTS and/or Geotools? What type of index would I create. (The polygon data will be static after loading as it will just contain country borders)

From reading geotools documentation its hard to decipher the spatial index and how well it performs and whether it should be used?

Any help or guidance would be appreciated.

Thanks

user2092856
  • 301
  • 5
  • 13

2 Answers2

3

The problem you're trying to solve is called the point in polygon problem. A previous answer gave an example of testing if one point is in one polygon, using JTS (Java Topology Suite).

I don't know if there's a more efficient solution for multiple polygons. You might want to test the polygons in turn, sorted by distance from your point.

Community
  • 1
  • 1
Stuart Caie
  • 2,803
  • 14
  • 15
1

Short answer: Building up a trapezoidal map from your countries and point location is O(log n) where n is the number of line segments.

Reference: Chapter 6 of Computational Geometry: Algorithms and Applications, Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars

knivil
  • 916
  • 5
  • 10