Najbliższe wyszukiwanie sąsiadów z okresowymi warunkami brzegowymi

Question

W sześciennym pudle mam duże punkty zbiórki w R^3. Chciałbym znaleźć najbliższych sąsiadów dla każdego punktu. Normalnie myślę, że używam czegoś takiego jak drzewo k-d, ale w tym przypadku mam okresowe warunki brzegowe. Jak rozumiem, drzewo k-d działa poprzez podział przestrzeni na partycje, przecinając je w hiper-płaszczyzny o jednym mniejszym wymiarze, tj. W 3D dzielimy przestrzeń rysując płaszczyzny 2D. Dla dowolnego punktu jest albo na płaszczyźnie, nad nią, albo pod nią. Jednak, gdy podzielisz przestrzeń z okresowymi warunkami brzegowymi, punkt może być uważany za znajdujący się po obu stronach!

Jaka jest najskuteczniejsza metoda znajdowania i utrzymywania listy najbliższych sąsiadów z okresowymi warunkami brzegowymi w R^3?

Aproksymacje są niewystarczające, a punkty będą przenoszone tylko po jednym na raz (nie przypominają symulacji N-body Monte Carlo).

Answer 1

Nawet w przypadku Euklidesa punkt i jego najbliższy sąsiad mogą znajdować się po przeciwnych stronach hiperpłaszczyzny. Rdzeń wyszukiwania najbliższego sąsiada w drzewie k-d jest prymitywem, który określa odległość między punktem a polem; jedyną modyfikacją niezbędną w twoim przypadku jest uwzględnienie możliwości zawijania.

Można również zaimplementować drzewa osłon, które działają na dowolne dane.

Answer 2

(jestem delegowania tę odpowiedź, chociaż nie jestem całkowicie pewien, że to działa. Intuicyjnie wydaje się w porządku, ale nie może być przypadek krawędź nie uznały)

Jeśli pracujesz z okresowe warunki brzegowe, wtedy można myśleć o przestrzeni jako pociętej na serię bloków o stałym rozmiarze, które następnie nakłada się na siebie nawzajem. Załóżmy, że jesteśmy w R . Wtedy jedną z opcji byłoby powtórzenie tego bloku dziewięć razy i ułożenie go w siatkę 3x3 duplikatów bloku. Biorąc to pod uwagę, jeśli mamy znaleźć najbliższy sąsiad jakiegokolwiek pojedynczego węzła na centralnym placu, a następnie albo

1. Najbliższy sąsiad jest wewnątrz centralnego placu, w którym to przypadku sąsiad jest najbliższy sąsiad lub
2. The najbliższy sąsiad znajduje się na placu innym niż centralny plac. W takim przypadku, jeśli znajdziemy punkt w centralnym kwadracie, do którego odnosi się sąsiad, punkt ten powinien być najbliższym sąsiadem pierwotnego punktu testowego w okresowym warunku brzegowym.

Innymi słowy, wystarczy tylko powtórzyć elementy, aby odległość euklidesowa między punktami pozwoliła nam znaleźć odpowiednią odległość w przestrzeni modulo.

w n wymiarów, trzeba by zrobić 3 ⁿ kopie wszystkich punktów, które brzmi jak dużo, ale dla R jest tylko 27x wzrost w stosunku do oryginalnego rozmiaru danych. Jest to z pewnością ogromny wzrost, ale jeśli jest w dopuszczalnych granicach, powinieneś być w stanie użyć tej sztuczki, aby wykorzystać standardowe drzewo kd (lub inne drzewo przestrzenne).

Mam nadzieję, że to pomoże! (Mam nadzieję, że to prawda!)