How to make subquery to find all overlapping circles in radius of central circle?

[eBartek]

How to find in mongodb all entities that doesn't relate only to the center position but also include radius around if the circle overlaps with other circles? I suppose subquery can be made on raw mongodb javascript?

Now I can obtain only this circles within central point lies in searched area of circle:

var search = [[30, 30], 10]

db.places.find({circle : {"$within" : {"$center" : [search]}}})

I can't put on circle a special index so I created example data with location (special index) and radius:

{ "_id" : 1, "name" : "a", "circle" : [ [ 5, 5 ], 40 ], "latlng" : [ 5, 5 ], "radius" : 40 }

{ "_id" : 2, "name" : "b", "circle" : [ [ 10, 10 ], 5 ], "latlng" : [ 10, 10 ], "radius" : 5 }

{ "_id" : 3, "name" : "c", "circle" : [ [ 20, 20 ], 5 ], "latlng" : [ 20, 20 ], "radius" : 5 }

{ "_id" : 4, "name" : "d", "circle" : [ [ 30, 30 ], 50 ], "latlng" : [ 30, 30 ], "radius" : 50 }

{ "_id" : 5, "name" : "e", "circle" : [ [ 80, 80 ], 30 ], "latlng" : [ 80, 80 ], "radius" : 30 }

{ "_id" : 6, "name" : "f", "circle" : [ [ 80, 80 ], 20 ], "latlng" : [ 80, 80 ], "radius" : 20 }

Desired query result:

{ "_id" : 1, "name" : "a", "circle" : [ [ 5, 5 ], 40 ], "latlng" : [ 5, 5 ], "radius" : 40 }

{ "_id" : 3, "name" : "c", "circle" : [ [ 20, 20 ], 5 ], "latlng" : [ 20, 20 ], "radius" : 5 }

{ "_id" : 4, "name" : "d", "circle" : [ [ 30, 30 ], 50 ], "latlng" : [ 30, 30 ], "radius" : 50 }

{ "_id" : 5, "name" : "e", "circle" : [ [ 80, 80 ], 30 ], "latlng" : [ 80, 80 ], "radius" : 30 }

[Greg Studer]

Not 100% sure I understand fully, but it seems like you want to do an intersection or overlap query - what circles overlap my search region?  As you mention, this isn't supported by mongodb geo indices (we only index points, not shapes, right now).  If you have a max radius, one workaround would be to search using that max radius from the central point, then filter on the app side.

Another workaround would be to approximate the circle by "filling it in" with a number of points spaced at the min search radius and indexing those - the more additional points you add the more accurate the $within search becomes.  This won't work well for asymmetrical shape searches, but for similarly-sized circles it may be all you need.

[eBartek]

Well you put into words what I'd like. I thought that it is possible to make whole filter queries only in mongodb because ruby is slower. Your second solution looks interesting but I don't know how to make it in practice. In my application I have specified stiff radius eg. 5, 10, 15, 20 until 10000 but this looks to many for indexing.

[Asya Kamsky]

As Greg said, there is currently no capability in mongo to directly query about overlapping objects, only points within objects.

You can implement some work-arounds (I believe you asked the same question on stackoverflow where I posted this answer):

Here is a work-around in the shell based on that calculation:

function distance(a, b) {
    return Math.pow(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2), 0.5);
}

On your sample data inserted into collection 'circle':

> db.circle.find().forEach(
    function(c) {  
        if ( (distance(c.latlng, search.latlng) < c.radius + search.radius) ) 
          {   
               print(c.name); 
          } 
    } )
a
c
d
> 

Hope that helps,

Asya