Recherche d'intersections

Question

Dans un scénario où il y a des millions de zones de délimitation se chevauchant potentiellement de tailles variables, moins les 5 km de largeur.

Créer une fonction rapide avec les arguments findIntersections (Longitude, Latitude, Radius) et la sortie est une liste de ces boîtes englobantes id où chaque origine de boîte englobante se trouve dans le périmètre des dimensions de l'argument de fonction.

Comment résoudre ce problème avec élégance?

Answer 1

Cela se fait normalement à l'aide d'un module structure de données R-tree

dbs comme mysql ou postgresql ont SIG qui utilisent un r-arbre sous le capot pour récupérer rapidement que dans un certain proximité d'un point sur une carte.

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

R arbres sont des structures de données d'arbre qui sont similaires à B-arbres, mais ils sont utilisés pour les méthodes d'accès spatiales, à savoir, pour indexation de l'information multi-dimensionnelle ; par exemple, les coordonnées (X, Y) de données géographiques. Un l'utilisation réelle du monde pour un R-tree pourrait être: "Trouver tous les musées dans 2 kilomètres (1.2 mi) de mon actuel emplacement".

La structure de données divise l'espace avec hiérarchiquement emboîtés, et peut-être qui se chevauchent, bondissant minimum rectangles (BRM, autrement connu sous le nom boîtes englobantes, soit « rectangle », ce qui le « R » dans R-tree est synonyme de).

Le Priority R-Tree (PR-tree) est une variante qui a un temps de fonctionnement maximum:

"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." 

Dans la pratique requêtes du monde réel la plupart auront un temps d'exécution cas beaucoup plus rapide en moyenne.

FYI, en plus de l'autre grand code affiché, il y a des trucs cool comme SpatiaLite et SQLite R-tree module

Answer 2

PostGIS est une extention SIG open source pour postgresql. Ils ont les fonctions ST_Intersects et ST_Intersection disponibles.

Si vous êtes intéressé, vous pouvez creuser et voir comment il est mis en œuvre là:

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

Answer 3

Cela semble être une meilleure approche plus générale GIST

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