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

Représentez les cercles comme des cônes en 3D, où la troisième dimension est le temps. Ensuite, utilisez un arbre BSP pour les partitionner du mieux que vous pouvez.

En général, je pense que le pire cas pour tester l'intersection est toujours en O(n), où n est le nombre de cercles. La plupart des structures de données spatiales fonctionnent en partitionnant l'espace de manière intelligente pour qu'une fraction des objets (idéalement proche de la moitié) se trouvent dans chaque moitié. Cependant, si les objets se chevauchent, la partition ne peut pas être parfaite; il y aura toujours des cas où plus d'un objet se trouve dans une partition. Si vous pensez simplement au cas de deux cercles se chevauchant, il n'y a aucun moyen de dessiner une ligne de sorte qu'un cercle soit entièrement d'un côté et l'autre cercle soit entièrement de l'autre côté. Mené à l'extrême, en supposant un positionnement arbitraire des cercles et des rayons arbitraires, il n'y a aucun moyen de les partitionner de sorte que le test d'intersection prenne en O(log(n)).

Cela ne signifie pas que, en pratique, vous n'obtiendrez pas un grand avantage en utilisant un arbre, mais l'avantage dépendra de la configuration des cercles et de la distribution des requêtes.

Answer 2

Ceci est une version simplifiée d'un autre problème que j'ai posté il y a environ une semaine : Comment trouver la première intersection d'un rayon avec des cercles en mouvement

Je n'ai pas encore eu le temps de décrire la solution attendue là-bas, mais je vais essayer de la détailler ici (pour ce cas plus simple).

L'approche pour résoudre ce problème est d'utiliser un KD-tree cinétique. Si vous n'êtes pas familier avec les KD trees, il est préférable de d'abord en apprendre davantage sur eux. Vous devez également ajouter le temps comme coordonnée supplémentaire (vous faites de l'espace 3D au lieu de 2D). Je n'ai pas encore mis en œuvre cette idée, mais je crois que c'est la bonne approche.

Answer 3

Désolé, ce n'est pas complètement réfléchi, mais il semble que vous pourriez vous pencher sur les Diagrammes de Voronoi pondérés de manière multiplicative (MWVD). Il semble qu'un adversaire pourrait vous obliger à en calculer un avec une série de requêtes bien placées, ce qui pourrait fournir une borne inférieure à votre problème.

Supposez que vous calculiez le MWVD sur vos données d'entrée. Ensuite, pour une requête, vous obtiendriez le cercle le plus "proche" de votre point de requête. Vous pouvez alors déterminer si ce cercle contient réellement le point de requête au moment de la requête. Si ce n'est pas le cas, alors vous avez terminé : aucun cercle ne contient votre point. Si c'est le cas, vous devriez alors calculer le MWVD sans ce générateur et relancer la même requête. Vous pourriez être en mesure de calculer le nouveau MWVD à partir de l'ancien : la cellule contenant le générateur qui a été supprimé doit être remplie, et il semble (bien que je ne l'ai pas prouvé) que seuls ses voisins peuvent la remplir.

Answer 4

Un certain type d'index spatial, tel qu'un quadtree ou un BSP, vous donnera un temps d'accès en O(log(n)).

Par exemple, chaque nœud dans le quadtree pourrait contenir une liste chaînée de pointeurs vers tous ces cercles qui l'intersectent.

Combien de cercles, d'ailleurs? Pour de petits n, vous pourriez aussi bien les parcourir tous. Si vous devez constamment mettre à jour votre index spatial et sauter partout dans les lignes de cache, il pourrait être plus rapide de simplement tout tester.

Answer 5

Comment les centres de vos cercles sont-ils distribués? S'ils couvrent le plan de manière assez uniforme, vous pouvez discrétiser l'espace et le temps, puis effectuer les étapes suivantes en prétraitement :

for (t=0; t < max_t; t++)
    foreach cercle c, avec centre et rayon (x,y,r) au temps t
        for (int X = x-r; X < x+r; x++)
           for (int Y = x-r; Y < y+r; y++)
               circles_at[X][Y][T].push_back (&c)

(en supposant que vous discrétisez l'espace et le temps le long de limites entières, échelle et décalage selon vos préférences, et vous pouvez ajouter des cercles plus tard ou amortir le coût en différant le calcul pour des valeurs lointaines de t)

Ensuite, votre requête pour le point (x, y) au temps (t) pourrait faire une vérification linéaire brute sur circles_at[x][y][ceil(t)]

Le compromis est évident, augmenter la résolution de l'une des trois dimensions augmentera le temps de prétraitement mais vous donnera un plus petit seau dans circles_at[x][y][t] à tester.