Comment fonctionnent les formes (rectangles) dans les arbres quadruples?

On m'a dit qu'un arbre quadruple est la structure de données idéale pour mon jeu, mais j'ai du mal à comprendre comment fonctionnent exactement les formes dans les arbres quadruples.

Je fais cela en JavaScript, mais je pense que ces questions pourraient s'appliquer aux arbres quadruples dans n'importe quelle langue.

Je pense que je comprends surtout comment les points de base (x, y) et l' insertion de points fonctionnent dans les arbres quadruples, et que je pourrais le faire sur papier.

Voici un JSfiddle de mon expérience avec les points.

Mis à part un cas, mes tests avec des points fonctionnent comme prévu.

Mais ma confusion commence lorsque des formes comme des rectangles sont impliquées. Lorsque vous récupérez à partir d'un arbre quadruple avec des formes, vérifie-t-il chaque point de la forme et dans quels nœuds ils tombent? Et comment fonctionnent les insertions de formes, même si elles acceptent les paramètres (x, y, largeur, hauteur) pour chaque forme? Utilise-t-il la largeur / hauteur du point de départ pour calculer d'autres points d'angle, qui sont ensuite distribués dans les nœuds appropriés? Si une forme insérée s'étend sur quatre nœuds, les données de cette forme sont-elles enregistrées dans les quatre nœuds?

Et lorsqu'une méthode de récupération accepte une forme comme paramètre (x, y, largeur, hauteur), que se passe-t-il réellement? Est-ce qu'il voit d'abord à quels nœuds la forme s'étendrait s'il devait être inséré, puis récupère tous les objets de ces nœuds?

J'ai un JSfiddle qui travaille avec des formes , mais je suis complètement confus sur les résultats de mes tests. Je reçois des objets en double retournés!

Par exemple, le carré rouge est un équivalent dessiné des paramètres que j'entre dans ma méthode de récupération. Je pense que puisque ce carré rouge s'étend sur les quatre nœuds, il devrait renvoyer chaque objet dans l'arbre quadruple! Mais ce n'est pas le cas, et j'ai du mal à rationaliser ce qu'il retourne. J'ai un certain nombre d'autres tests qui sont actuellement commentés, mais vous pouvez annuler le commentaire et les exécuter pour voir des résultats plus confus!

Comme dire, si je veux retourner tous les points dans un arbre quadruple, comment ferais-je cela? Une méthode de récupération utilisant une forme de toute la taille des limites? Par exemple, récupérer (0, 0, canvas.width, canvas.height)?

La bibliothèque JavaScript QuadTree que j'utilise a été mentionnée par diverses autres sources, donc je suppose que la mise en œuvre réelle est correcte et réputée.

Je pense qu'une grande partie de ma confusion peut provenir d'un malentendu de la terminologie de l'arbre quadruple. Par exemple, pourquoi disent-ils des limites plutôt que des dimensions, lorsqu'un "point" a également des paramètres largeur / hauteur? Est-ce une question de convention / raccourci, ou s'agit-il de concepts complètement différents?

Merci pour votre temps!

Les Quadtrees stockent et récupèrent généralement des rectangles. Un point est un cas spécifique où la largeur et la hauteur sont nulles. La logique suivante est utilisée pour trouver la maison de nouveaux rectangles dans l'arborescence, en commençant par le nœud racine:

void Store(Rectangle rect)
{
    if(I have children nodes)
    {
        bool storedInChild = false;
        foreach(Node childNode in nodes)
        {
            if(this rectangle fits entirely inside the childNode bounds)
            {
                childNode.Store(rect);   // Go deeper into the tree
                storedInChild = true;
                break;
            }
        }
        if(not storedInChild)
        {
            Add this rectangle to the current node
        }
    }
    else
    {
        Add this rectangle to the current node
    }
}

Notez que les rectangles peuvent être stockés à n'importe quelle profondeur, il ne doit pas nécessairement s'agir d'un quadrilatère. Si le rectangle chevauche la frontière au niveau racine, le quadruple racine stockera le rectangle.

Par exemple, le carré rouge est un équivalent dessiné des paramètres que j'entre dans ma méthode de récupération. Je pense que puisque ce carré rouge s'étend sur les quatre nœuds, il devrait renvoyer chaque objet dans l'arbre quadruple! Mais ce n'est pas le cas, et j'ai du mal à rationaliser ce qu'il retourne.

Lorsque vous interrogez le quadtree, il ne renvoie que des rectangles contenus dans la requête. Dans votre exemple, vous forcez chacun des 4 quadrants enfants à être examiné plus en détail car le rectangle de requête rouge coupe chaque quadruple enfant. Étant donné que les enfants n'ont plus d'autres enfants, chacun des rectangles de ces quads enfants sera comparé au rectangle rouge. Étant donné qu'aucun des rectangles de l'arborescence n'entre en collision avec le rectangle de requête rouge, rien ne doit être retourné.

Vous commencez vraiment à voir les avantages des arbres quadruples lorsque vous avez beaucoup d'objets et beaucoup d'espace pour que les objets existent par rapport aux zones de requête. Dans ces cas, une petite zone de requête peut rapidement éliminer de vastes portions de l'arbre quadruple. Seuls les quadrilatères qui coupent le rectangle de requête seront examinés plus en détail.

ÉDITER

La récupération se fait généralement comme suit:

List<Rectangle> Query(Rectangle queryRect)
{
    List<Rectangle> results;
    foreach(Node childNode in children)
    {
        if(queryRect intersects with childNode bounds)
        {
            results += childNode.Query(queryRect);   // Dig deeper into the tree
        }
    }

    foreach(Rectangle I have stored in this quad)
    {
        if(queryRect intersects with rect)  // Your library doesn't do this
        {
            results += rect;
        }
    }

    return results;
}

Cependant, dans votre bibliothèque, il ne semble pas vérifier si les rectangles renvoyés se croisent avec la requête, vous devrez donc l'ajouter vous-même.