Méthodes d'indexation alternatives pour les opérations d'ensemble de points

17

Il est courant d'utiliser un index spatial de boîte englobante pour améliorer les performances lorsque vous travaillez avec un grand nombre de fonctionnalités. Lorsque des opérations sont effectuées sur des géométries individuelles avec un grand nombre de sommets, existe-t-il des stratégies d'optimisation similaires?

Par exemple, existe-t-il des structures de données qui peuvent accélérer le point dans un polygone ou les opérations d'union?

algorithm optimization indexing Matthew Snape
la source
1
Sous le capot, les SIG utilisent de nombreuses structures de données spécialisées, y compris diverses formes de quadrilatères, DCEL, etc., qui sont décrites dans les manuels de géométrie computationnelle. Demandez-vous ces détails d'implémentation ou demandez-vous des méthodes qui pourraient être utilisées par les utilisateurs dans les langages de script?
whuber
Merci, je pense que je dois lire les manuels. Le point de ma question était de savoir comment ces structures de données peuvent être précalculées à l'avance. Existe-t-il des implémentations précalculées?
Matthew Snape
Matthew, c'est une excellente question. Un SIG véritablement axé sur les performances offrirait aux utilisateurs des options de précalcul des structures de données pour des applications répétées. Dans l'état actuel des choses, les logiciels qui se présentent sous le nom de "SIG" n'offrent généralement ce type de précalcul que sous la forme d '"index spatiaux", tandis que les logiciels plus polyvalents qui peuvent également effectuer des analyses SIG, comme Mathematica (ou dans une certaine mesure R), offriront à l'utilisateur beaucoup plus de contrôle sur de telles choses.
whuber
Je pense que le problème est basé sur la «nature fractale» des objets 2D et la densité incertaine et déséquilibrée de l'information sur la distribution.
huckfinn

Réponses:

2

OK pour Point dans le polygone uniquement:

Je pense que le problème est basé sur la "nature fractale" des objets 2D et la distribution incertaine et déséquilibrée de l'information spatiale. Si vous avez une grille régulière, il est facile de calculer la position ou la relation d'une cellule. Mais une isoline d'un modèle de terrain peut avoir des parties simples sur le côté et des parties mathématiquement compliquées de l'autre côté (parties morphologiquement actives sur les crêtes, les vallées ...).

L'indexation tente de gérer deux choses:

  1. Une routine rapide qui vous donne un ensemble de seaux dans lequel vous collectez des objets que vous pouvez distinguer spatialement (les seaux!). Et les BBox sont faciles à calculer et à manipuler.

  2. Un ensemble de relations (chevauchement, toucher) pour distinguer ou relier les éléments spatiaux (les objets).

Malheureusement, les BBox ne vous donneront aucune indication, combien de points se trouvent dans chaque BBox, comment les objets sont façonnés (trous, convexes, ...) et comment les informations sont distribuées localement (90% des points dans le coin supérieur gauche du BBox). Ainsi, vous pouvez trouver des membres d'opération rapide au niveau de l'objet et perdre beaucoup de temps dans la construction de relations du test.

Pour utiliser une approche plus irrégulière, la triangulation IMO en combinaison avec et quadtrees est l'une des stratégies, où vous pouvez rapprocher le bucketing et la partie construction de relations d'un index (bucketing == construction de relations).

Pour l'exemple Point-in-Polygon-Test, il est possible de créer un cache irrégulier en utilisant:

  1. ! triangulation delaunay contrainte de votre couverture poly, avec des points de maillage de bordure supplémentaires pour la détection en dehors de la couverture
  2. mettre cela dans un schéma d'indexation à quatre arbres avec pas plus de N triangles par boîte (seaux fractals)
  3. trouver l'ensemble de triangles auquel le point appartient - la feuille dans le quadtree
  4. trouver le triangle dans lequel se trouve le point (la partie test sur max. N triangles)
  5. et demander les ID de polygone des sommets du triangle
  6. si l'ID est unique le point appartient au polygone, sinon il est en dehors

Le coût de construction de l'étain et des quadtrees est très élevé et difficile à calculer et le quadtree doit équilibrer les grands et les petits triangles (triangles qui ne rentreront pas dans des boîtes de sous-arbres plus petites).

Quelques outils et liens:

Triangle - Triangulation par polygone de contrainte

Quadtrees - Avec des exemples de sources

Dépôt de Stony Brook - Structures de données et géométrie du disque

huckfinn
la source