Jak kształty (prostokąty) działają na poczwórnych drzewach?

Powiedziano mi, że drzewo quad jest idealną strukturą danych dla mojej gry, ale mam problem ze zrozumieniem, jak dokładnie kształty działają w drzewach quad.

Robię to w JavaScript, ale myślę, że te pytania mogą dotyczyć drzew quadów w dowolnym języku.

Myślę, że głównie rozumiem, jak podstawowe (x, y) punkty i wstawianie punktów działają w drzewach quad i że mogę to zrobić na papierze.

Oto JSfiddle mojego eksperymentowania z punktami.

Oprócz jednego przypadku moje testy z punktami działają zgodnie z oczekiwaniami.

Ale moje zamieszanie zaczyna się, gdy w grę wchodzą kształty takie jak prostokąty. Czy podczas pobierania z drzewa quad z kształtami sprawdza on każdy punkt kształtu i do jakich węzłów się one mieszczą? Jak działają wstawki kształtów, jeśli akceptują parametry (x, y, szerokość, wysokość) dla każdego kształtu? Czy używa szerokości / wysokości od punktu początkowego do obliczania innych punktów narożnych, które są następnie rozdzielane na odpowiednie węzły? Jeśli wstawiony kształt rozciąga się na cztery węzły, czy dane tego kształtu są zapisywane we wszystkich czterech węzłach?

A kiedy metoda pobierania przyjmuje kształt jako parametr (x, y, szerokość, wysokość), co się właściwie dzieje? Czy najpierw widzi, do jakich węzłów byłby kształt, gdyby miał zostać wstawiony, a następnie pobiera wszystkie obiekty tych węzłów?

Mam JSfiddle pracujący z kształtami , ale jestem całkowicie zdezorientowany wynikami moich testów. Dostaję zwracane duplikaty obiektów!

Na przykład czerwony kwadrat jest narysowanym odpowiednikiem parametrów, które wprowadzam do mojej metody wyszukiwania. Myślę, że skoro ten czerwony kwadrat obejmuje wszystkie cztery węzły, powinien zwrócić każdy obiekt w drzewie quadów! Ale tak nie jest i mam problem z racjonalizacją tego, co powraca. Mam wiele innych testów, które są obecnie komentowane, ale możesz cofnąć komentarz i uruchomić je, aby zobaczyć bardziej mylące wyniki!

Jak powiedzmy, jeśli chcę zwrócić wszystkie punkty z drzewa quadów, jak miałbym to zrobić? Metoda pobierania wykorzystująca kształt całego rozmiaru granic? Na przykład odzyskać (0, 0, canvas.width, canvas.height)?

Biblioteka JavaScript QuadTree Używam została przekazana przez różnych innych źródeł, więc zakładam, rzeczywista implementacja jest poprawna i godna zaufania.

Myślę, że wiele moich nieporozumień może wynikać z niezrozumienia terminologii quad tree. Na przykład, dlaczego mówią granice zamiast wymiarów, skoro „punkt” ma również parametry szerokości / wysokości? Czy to kwestia konwencji / krótkiego układu, czy też są to zupełnie inne pojęcia?

Dziękuję za Twój czas!

Czworokąty zazwyczaj przechowują i pobierają prostokąty. Punkt jest szczególnym przypadkiem, w którym szerokość i wysokość wynoszą zero. Poniższa logika służy do znalezienia domu dla nowych prostokątów w drzewie, zaczynając od węzła głównego:

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
    }
}

Pamiętaj, że prostokąty można przechowywać na dowolnej głębokości, nie musi to być kwadratowy liść. Jeśli prostokąt styka się z granicą bezpośrednio na poziomie głównym, poczwórny kwadrat zapisze prostokąt.

Na przykład czerwony kwadrat jest narysowanym odpowiednikiem parametrów, które wprowadzam do mojej metody wyszukiwania. Myślę, że skoro ten czerwony kwadrat obejmuje wszystkie cztery węzły, powinien zwrócić każdy obiekt w drzewie quadów! Ale tak nie jest i mam problem z racjonalizacją tego, co powraca.

Podczas zapytania do kwadratu zwraca tylko prostokąty zawarte w zapytaniu. W twoim przykładzie wymuszasz bardziej szczegółowe przeglądanie każdego z 4 podrzędnych quadów, ponieważ czerwony prostokąt zapytania przecina każdy z podrzędnych quadów. Ponieważ dzieci nie mają kolejnych dzieci, każdy z prostokątów w tych dziecięcych quadach zostanie porównany z czerwonym prostokątem. Ponieważ żaden z prostokątów w drzewie nie koliduje z czerwonym prostokątem zapytania, nic nie powinno być zwracane.

Naprawdę zaczynasz dostrzegać zalety czworokątów, gdy masz dużo obiektów i dużo miejsca na istnienie obiektów w porównaniu z obszarami zapytań. W takich przypadkach mały obszar zapytań może szybko wyeliminować rozległe fragmenty drzewa quadów. Tylko quady, które przecinają się z prostokątem zapytania, będą kiedykolwiek oglądane bardziej szczegółowo.

EDYTOWAĆ

Pobieranie odbywa się zwykle w następujący sposób:

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;
}

W twojej bibliotece nie wydaje się jednak sprawdzać, czy zwracane prostokąty przecinają się z zapytaniem, więc musisz to dodać samodzielnie.