Effective overlap query

[google]

Effective overlap query

[jmr]

You say overlap query, but you seem to be describing a point containment query. Maybe I'm just not familiar with the terminology.

Does S2ContainsPointQuery do what you want? Look at s2contains_point_query_test.cc for example uses.

Do all of your polygons fit in memory?

[benstadin]

Thanks for the link. I think the test case starting at line 107 is what I'm looking for.

Yes, the polygons should all fit into memory. I want to create static set of regions from polygons of varying shape (will always be regular simple type polygons), and test if a moving location coordinate (position) is inside on of the indexed fences. Indexed regions may also overlap each other sometimes.

What is the Big O for the query round about?

By overlap I mean an intersection test, which also includes the border of the indexed polygon and not only tests if it's contained within. It is important for me that the intersection test between the original defined polygon region and position coordinate is exact.

[jmr]

What is the Big O for the query round about?

You can think of it as O(log(num_shapes)).

It is important for me that the intersection test between the original defined polygon region and position coordinate is exact.

I'm not sure of the exact guarantees, but you don't have the input geometry exactly, and the conversion from lat/lng to S2Point also isn't exact, so maybe rethink this.