Finding intersections

Given a scenario where there are millions of potentially overlapping bounding boxes of variable sizes less the 5km in width.

Create a fast function with the arguments findIntersections(Longitude,Latitude,Radius) and the output is a list of those bounding boxes ids where each bounding box origin is inside the perimeter of the function argument dime开发者_StackOverflow中文版nsions.

How do I solve this problem elegantly?

---

This is normally done using an R-tree data structure

dbs like mysql or postgresql have GIS modules that use an r-tree under the hood to quickly retrieve locations within a certain proximity to a point on a map.

From http://en.wikipedia.org/wiki/R-tree:

R-trees are tree data structures that are similar to B-trees, but are used for spatial access methods, i.e., for indexing multi-dimensional information; for example, the (X, Y) coordinates of geographical data. A common real-world usage for an R-tree might be: "Find all museums within 2 kilometres (1.2 mi) of my current location".

The data structure splits space with hierarchically nested, and possibly overlapping, minimum bounding rectangles (MBRs, otherwise known as bounding boxes, i.e. "rectangle", what the "R" in R-tree stands for).

The Priority R-Tree (PR-tree) is a variant that has a maximum running time of:

"O((N/B)^(1-1/d)+T/B) I/Os, where N is the number of d-dimensional (hyper-)
rectangles stored in the R-tree, B is the disk block size, and T is the output
size."

In practice most real-world queries will have a much quicker average case run time.

fyi, in addition to the other great code posted, there's some cool stuff like SpatiaLite and SQLite R-tree module

---

PostGIS is an open-source GIS extention for postgresql.

They have ST_Intersects and ST_Intersection functions available.

If your interested you can dig around and see how it's implemented there:

http://svn.osgeo.org/postgis/trunk/postgis/

---

This seems like a better more general approach GiST

http://en.wikipedia.org/wiki/GiST