Jak w 2D efektywnie znaleźć najbliższy obiekt do punktu?

Mam spory silnik gry i chciałbym znaleźć funkcję znajdującą się najbliżej listy punktów.

Mógłbym po prostu użyć twierdzenia Pitagorasa, aby znaleźć każdą odległość i wybrać minimalną, ale to wymaga iteracji przez wszystkie z nich.

Mam również system kolizji, w którym zasadniczo zmieniam obiekty w mniejsze obiekty na mniejszej siatce (coś w rodzaju minimapy) i tylko jeśli obiekty istnieją w tym samym obszarze siatki, sprawdzam kolizje. Mógłbym to zrobić, tylko zwiększyć odstępy siatki, aby sprawdzić bliskość. (Zamiast sprawdzać każdy pojedynczy obiekt.) Jednak to wymagałoby dodatkowej konfiguracji w mojej klasie podstawowej i zaśmiecało już zaśmiecony obiekt. Czy warto?

Czy jest coś wydajnego i dokładnego, którego mógłbym użyć do wykrycia najbliższego obiektu na podstawie listy punktów i rozmiarów?

Problem z quad / octree w wyszukiwaniu najbliższych sąsiadów polega na tym, że najbliższy obiekt może znajdować się w poprzek podziału między węzłami. W przypadku kolizji jest to w porządku, ponieważ jeśli nie ma go w węźle, nie obchodzi nas to. Ale rozważ ten przykład 2D z quadtree:

Tutaj, mimo że czarny przedmiot i zielony przedmiot znajdują się w tym samym węźle, czarny przedmiot jest najbliżej niebieskiego przedmiotu. odpowiedź ultifinitusa może zagwarantować tylko najbliższemu sąsiadowi, że tylko każdy element w twoim drzewie jest umieszczony w najmniejszym możliwym węźle, który mógłby go zawierać, lub w unikalnym węźle - prowadzi to do bardziej nieefektywnych czworokątów. (Należy pamiętać, że istnieje wiele różnych sposobów implementacji struktury, którą można nazwać quad / octree - bardziej rygorystyczne implementacje mogą działać lepiej w tej aplikacji).

Lepszą opcją byłoby drzewo KD . Drzewa Kd mają bardzo wydajny algorytm wyszukiwania najbliższych sąsiadów , który można wdrożyć i może zawierać dowolną liczbę wymiarów (stąd wymiary „k”).

Świetna i pouczająca animacja z Wikipedii:

Największy problem z używaniem drzew KD, o ile dobrze pamiętam, polega na tym, że trudniej jest je wkładać / wyjmować, zachowując równowagę. Dlatego zalecałbym użycie jednego drzewa KD do obiektów statycznych, takich jak domy i drzewa, które są wysoce zrównoważone, a drugiego zawierającego graczy i pojazdy, które wymagają regularnego równoważenia. Znajdź najbliższy obiekt statyczny i najbliższy obiekt mobilny i porównaj te dwa.

Wreszcie drzewa kd są stosunkowo łatwe do wdrożenia i jestem pewien, że można znaleźć w nich wiele bibliotek C ++. Z tego, co pamiętam, R-drzewa są znacznie bardziej skomplikowane i prawdopodobnie przesadzają, jeśli wszystko, czego potrzebujesz, to proste wyszukiwanie najbliższego sąsiada.

sqrt() jest monotoniczny lub zachowuje porządek dla argumentów nieujemnych, więc:

sqrt(x) < sqrt(y) iff x < y

I wzajemnie.

Więc jeśli chcesz porównać tylko dwie odległości, ale nie jesteś zainteresowany ich rzeczywistymi wartościami, możesz po prostu wyciąć sqrt()-step z Pythagorasa:

pseudoDistanceB = (A.x - B.x)² + (A.y - B.y)²
pseudoDistanceC = (A.x - C.x)² + (A.y - C.y)²
if (pseudoDistanceB < pseudoDistanceC)
{
    A is closest to B!
}
else
{
    A is closest to C!
}

Nie jest tak skuteczny jak drzewo z ośmiornicą, ale jest łatwiejszy do wdrożenia i co najmniej trochę przyspiesza

Musisz wykonać partycjonowanie przestrzenne, w tym przypadku tworzysz wydajną strukturę danych (zwykle oktawę). W takim przypadku każdy obiekt znajduje się w jednej lub więcej przestrzeni (kostkach). A jeśli wiesz, w których przestrzeniach jesteś, możesz spojrzeć w górę O (1), które przestrzenie są sąsiadami.

W takim przypadku najbliższy obiekt można znaleźć, wykonując iterację po wszystkich obiektach w Twojej przestrzeni, szukając najbliższego. Jeśli nikogo tam nie ma, możesz sprawdzić swoich pierwszych sąsiadów, jeśli nikogo tam nie ma, możesz sprawdzić ich sąsiadów itp.

W ten sposób możesz łatwo znaleźć najbliższy obiekt bez konieczności iteracji przez wszystkie obiekty w twoim świecie. Jak zwykle ten wzrost prędkości wymaga nieco księgowości, ale jest naprawdę przydatny do wszelkiego rodzaju rzeczy, więc jeśli masz duży świat, zdecydowanie warto wdrożyć partycjonowanie przestrzenne i oktawę.

Jak zwykle zobacz także artykuł w Wikipedii: http://en.wikipedia.org/wiki/Octree

Może spróbuj uporządkować swoje dane przestrzenne w RTree, które jest trochę jak btree dla rzeczy w kosmosie i pozwala na zapytania takie jak „najbliżsi N sąsiedzi” itp. Http://en.wikipedia.org/wiki/Rtree

Oto moja implementacja Java, aby uzyskać najbliższą z quadTree. Zajmuje się problemem opisanym przez dlras2:

Myślę, że operacja jest naprawdę wydajna. Opiera się na odległości do kwadratu, aby uniknąć wyszukiwania w kwadracie dalej niż najbliższy bieżący.

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

public T getClosest(float x, float y) {

    Closest closest = new Closest();
    getClosest(x, y, closest);

    return closest.item;
}

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

protected void getClosest(float x, float y, Closest closestInfo) {


    if (hasQuads) {

        // we have no starting point yet
        // so get one
        if (closestInfo.item == null) {
            // check all 4 cause there could be a empty one
            for (int i = 0; i < 4; i++) {
                quads[i].getClosest(x, y, closestInfo);
                if (closestInfo.item != null) {
                    // now we have a starting point
                    getClosest(x, y, closestInfo);
                    return;
                }

            }
        }
        else {

            // we have a item set as closest
            // we should check if this quad is
            // closer then the current closest distance
            // let's start with the closest from index

            int closestIndex = getIndex(x, y);

            float d = quads[closestIndex].bounds.distToPointSQ(x, y);

            if (d < closestInfo.dist) {
                quads[closestIndex].getClosest(x, y, closestInfo);
            }

            // check the others
            for (int i = 0; i < 4; i++) {
                if (i == closestIndex) continue;

                d = quads[i].bounds.distToPointSQ(x, y);

                if (d < closestInfo.dist) {
                    quads[i].getClosest(x, y, closestInfo);
                }

            }

        }

    }
    else {

        for (int i = 0; i < items.size(); i++) {

            T item = items.get(i);

            float dist = distSQ(x, y, getXY.x(item), getXY.y(item));

            if (dist < closestInfo.dist) {
                closestInfo.dist = dist;
                closestInfo.item = item;
                closestInfo.tree = this;
            }

        }
    }

}

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


class Closest {

    QuadTree<T> tree;
    T item;
    float dist = Float.MAX_VALUE;

}