Fast geospatial search geofencing irregular polygons

Question

I have possibly billions of multipoint (sometimes more than 20) polygonal regions (varying sizes , intersecting, nested) distributed throughout the span of a country. Though, the polygonal regions or 'fences' will not usually be too large and most of them will be negligible in size compared to the span . The points of the polygons are described in terms of it's GPS co-ordinates. I need a fast algorithm to check whether the current GPS location of the device falls within any of the enclosed 'fences'.

I have thought of using RAY CASTING ALGORITHM (point in polygon test) after sufficiently narrowing down on the candidates using some search algorithm. The question now being what method would serve as an efficient 2D SEARCH ALGORITHM keeping the following two considerations-

1. Speed of processing
2. Data structure should be compact as the storage space is limited (flash storage)
3. The regions are static and constant. Hence , the 2 dimensional data can be pre sorted to any requirement before being stored.

The unit is to be put on a vehicle , and hence the search need not be repeated for regions sufficiently far from the vehicle's proximity. It's acceptable to have an initial boot up time provided the successive real-time look-ups are extremely fast.

I initially thought of using KD trees to perform a boundary box query after reducing each 'fence' to a point ( approx. by using a point within it) followed by ray casting algorithm.

I have also been looking at hilbert curves and geo hash for the same.

Another method I'm considering is to use RECTANGLES that just enclose the fences. We choose these rectangles for each fence such that it is aligned to the GRID (sides aligned to the latitude and longitude). That is , find out the max and min value of the latitudes and longitudes for a fence individually , let them be LAT 1, LAT 2, LONG 1 , LONG 2.

Now the points (LAT1, LONG1) , (LAT1, LONG2) , (LAT2, LONG1) , (LAT2, LONG2) are the co-ordinates of the rectangle (aligned to the GRID) that the fence must necessarily be contained in. (I do understand that it will not be a rectangle in the geometrical sense, nonetheless. )

Now use R tree to search for the RECTANGLES that the current gps location falls within. This will narrow the search down to very few results , each of which can be individually tested using RAY CASTING ALGORITHM.

I could also use a hybrid method by using K-D tree for the initial chunk and then applying R tree search. I am more than open to any other method as well.

What do you think is the best way to approach this problem statement?

EDIT - Removed the size restriction on the polygonal fences.

Answer 1

You can try a hierarchical point-in-polygon test for example kirkpatrick data structure but its very complicated. Personaly I would try rectangles, kd-tree, hilbert curves, quadtrees.

Answer 2

It sounds like your set of polygons is static. If so, one of the fastest ways is likely to be binary space partitioning. Very briefly, building a BSP tree means picking a single edge from among your billions of polygons, splitting any polygons that cross this (infinite) line into two halves, partitioning the polygons into those on each side of the line, and recursively building a BSP tree on each side. At the bottommost level of the tree are convex polygons that are wholly inside some set of original polygons -- so e.g. if two original polygons A and B intersect but one doesn't fully contain the other, then this will produce at least 3 "basic" polygons at the lowest level, one for the region A but not B, one for B but not A, and one for A and B. (More may be needed if any of these are not convex.) Each of these can be tagged with the list of original polygons that it is part of.

In the ideal case where no polygons are split, finding the complete set of polygons that you are inside is O(log(total number of edges)) once the BSP tree has been built, since deciding which child to visit next in the tree is just an O(1) test of which side of a line the query point is on.

Building the BSP tree takes quite a bit of work up front, especially if you want to make sure it does as little polygon subdivision as possible. It also requires that your polygons are convex, but if that's not the case, you can easily make them so by triangulating them first.

If your set of polygons grows slowly over time, you can of course complement the above technique with regular point-in-polygon testing for the new polygons, occasionally rebuilding the BSP tree when some threshold is reached.