Search code examples
c#giskdtreer-tree

Which spatial data structure (algorithm) is best for (searching in) a set of regions (spacial data)?

I have a set of regions (geo-fences) which are polygons. This set of data is fixed; so there is no need for insertion and deletion of data. Which data structure can be used for searching for regions that a query point (longitude, latitude) is in it?

Note: I have implemented KD-Tree (In fact a 2D-Tree) successfully for a set of points. But it does not work for this problem. I have implemented an R-Tree then; and it solves the problem but it is slow (or my implementation sucks).

Thank you

Note: I have worked on R-Tree implementation and it works fine now.

Solution

  • A R-Tree data structure can be used for this problem.