Représentation efficace pour les cercles croissants dans l'espace 2D?

Question

Imaginez qu'il y a un espace en 2D et dans cet espace, il y a des cercles qui grandissent à des taux constants différents. Quelle est une structure de données efficace pour stocker ces cercles, de telle sorte que je puisse interroger "Quels cercles intersectent le point p au moment t?"

EDIT: Je réalise que je pourrais stocker l'état initial des cercles dans une structure de données spatiale et effectuer une requête où j'intersecte un cercle au point p avec un rayon de fastest_growth * t, mais cela n'est pas efficace lorsque quelques cercles grandissent extrêmement rapidement tandis que la plupart grandissent lentement.

Édition supplémentaire: Je pourrais encore augmenter l'approche ci-dessus en divisant les cercles et en les regroupant par leur taux de croissance, puis en appliquant l'approche ci-dessus à chaque groupe, mais cela nécessite un temps borné pour être efficace.

Answer 1

Les gens vont faire beaucoup de recommandations sur les types d'indices spatiaux à utiliser, mais je voudrais offrir un peu de conseils orthogonaux.

Je pense qu'il est préférable de construire quelques indices basés sur le temps, c'est-à-dire t_0 < t_1 < t_2 ...

Si un point intersecte un cercle à t_i, il l'intersectera également à t_{i+1}. Si vous connaissez le point à l'avance, vous pouvez éliminer tous les cercles qui intersectent le point à t_i pour tous les calculs à t_{i+1} et ultérieurs.

Si vous ne connaissez pas le point à l'avance, vous pouvez conserver ces arbres temporels (construits en fonction de la taille de chaque cercle à un moment donné). Au moment de la requête (par exemple, t_query), trouvez i tel que t_{i-1} < t_query <= t_i. Si vous vérifiez tous les cercles possibles à t_i, vous n'aurez aucun faux négatif.

C'est un peu une astuce pour une structure de données « consciente de la dynamique temporelle », mais je n'en connais pas. Si vous avez un environnement threadé, alors vous n'avez besoin de maintenir qu'un seul indice spatial et travailler sur le suivant en arrière-plan. Cela vous coûtera beaucoup de calculs pour pouvoir répondre à des requêtes avec une faible latence. Cette solution devrait être comparée au moins à la solution O(n) (parcourir chaque point et vérifier si dist(point, center du cercle) < radius du cercle).

Answer 2

Au lieu de considérer les cercles, vous pouvez tester sur leurs boîtes englobantes pour filtrer ceux qui ne contiennent pas le point. Si vos côtés de boîte englobante sont tous triés, il s'agit essentiellement de quatre recherches binaires.

La partie délicate est de reconstruire les côtés triés pour un temps donné, t. Pour ce faire, vous pouvez commencer avec les points originaux : deux listes pour les côtés gauche et droit avec les coordonnées x, et deux listes pour le haut et le bas avec les coordonnées y. Pour un temps supérieur à 0, tous les points du côté gauche se déplaceront vers la gauche, etc. Vous devez seulement vérifier chaque emplacement à celui à côté pour obtenir des points où l'élément et celui à côté sont échangés. Cela devrait vous donner une liste de points temporels pour modifier vos listes ordonnées. Si vous triez maintenant ces enregistrements de modification par temps, pour un temps de début donné et un temps de fin, vous pouvez extraire tous les enregistrements de modification entre les deux, et les appliquer à vos quatre listes dans l'ordre. Je n'ai pas complètement compris l'algorithme, mais je pense qu'il y aura des cas limites où trois éléments successifs ou plus peuvent se croiser exactement au même moment, donc vous devrez peut-être modifier l'algorithme pour gérer ces cas limites également. Peut-être qu'un enregistrement de modification de liste contenant la position dans la liste et le nombre d'enregistrements à réorganiser suffirait.

Answer 3

Je pense qu'il est possible de créer un arbre binaire qui résout ce problème.

Chaque branche devrait contenir un cercle croissant, un cercle statique pour la partition et le moment le plus récent où le cercle de partitioning partitionne proprement. De plus, le cercle croissant contenu dans un nœud devrait toujours avoir un taux de croissance plus rapide que celui des cercles croissants de ses nœuds enfants.

Pour faire une requête, prenez le nœud racine. Vérifiez d'abord son cercle croissant, si celui-ci contient le point de requête au moment de la requête, ajoutez-le à l'ensemble de réponses. Ensuite, si le temps auquel vous effectuez votre requête est supérieur au moment où la ligne de partition est rompue, interrogez les deux enfants, autrement si le point se trouve dans le cercle de partition, interrogez le nœud gauche, sinon interrogez le nœud droit.

Je n'ai pas tout à fait terminé les détails concernant les insertions, (la partie difficile consiste à mettre à jour le cercle de partition de sorte que le nombre de nœuds à l'intérieur et à l'extérieur soit approximativement égal et que le moment où la partition est rompue soit maximisé).

Answer 4

Pour lutter contre les quelques cercles qui se développent rapidement, vous pouvez trier les cercles par ordre décroissant selon le taux de croissance et vérifier chacun des k développeurs les plus rapides. Pour trouver le bon k donné t, je pense que vous pouvez effectuer une recherche binaire pour trouver l'indice k tel que k*m = (t * taux de croissance de k)^2 où m est un facteur constant que vous devrez trouver par expérimentation. Cela équilibrera la partie qui croît linéairement avec k avec la partie qui diminue quadratiquement avec le taux de croissance.

Answer 5

Si vous représentez, comme déjà suggéré, des cercles croissants par des cônes verticaux en 3D, alors vous pouvez partitionner l'espace comme une grille régulière (peut-être hexagonale) de cylindres verticaux emballés. Pour chaque cylindre, calculez les hauteurs (fois) minimales et maximales d'intersections avec tous les cônes. Si le centre du cercle (sommet du cône) est placé à l'intérieur du cylindre, alors le temps minimal est zéro. Ensuite, triez les cônes par temps d'intersection minimal. En résultat de cet indexage, pour chaque cylindre, vous aurez la séquence ordonnée d'enregistrements avec 3 valeurs : temps minimal, temps maximal et numéro de cercle.

Lorsque vous vérifiez un point dans l'espace 3D, vous prenez le cylindre auquel il appartient et itérez sa séquence jusqu'à ce que le temps minimal stocké dépasse le temps du point donné. Tous les cônes obtenus, dont le temps maximal est inférieur au temps donné également, sont garantis de contenir le point donné. Seuls les cônes, où le temps donné se situe entre les temps d'intersection minimal et maximal, doivent être recalculés.

Il y a un compromis classique entre les coûts d'indexation et d'exécution - moins est le diamètre du cylindre, moins est la plage des temps d'intersection, donc moins de cônes ont besoin d'être recalculés à chaque point, mais plus de cylindres doivent être indexés. Si les centres des cercles sont répartis de manière non uniforme, il peut être utile de rechercher une meilleure configuration de placement de cylindre que la grille régulière.

P.S. Ma première réponse ici - je viens de m'inscrire pour la publier. J'espère qu'il n'est pas trop tard.