What is the most efficient way to find a list of markers within a radius search using Google Maps?

Question

Using Google maps on android, I have a location, and around 1000+ markers on a mapview. I need to identify which markers fall within a radius of a location. So, far it seems brute force search is used and a typical answer looks like this. But this is not efficient when there are a lot of markers.

My search of the Google maps API for android has not revealed an sdk method that performs an efficient search of list of markers, and returns a subset of markers that fits within a radius... Does Google maps sdk support this type of query ? If not, is a brute force search the only option ? And if brute force is only possible, what would be the most efficient implementation.

Answer 1

Keep your markers in a quadtree instead of storing them in a regular List. That way, you just need to check the markers inside the nodes of the tree that are affected by the desired radius.