Posortuj chmurę punktów w odniesieniu do nieustrukturyzowanej siatki komórek sześciościennych

11

Pytanie

Jak posortowałbyś chmurę punktów w odniesieniu do nieustrukturyzowanej siatki komórek sześciościennych?

Każda komórka ma centrum i unikalną etykietę do jej reprezentowania. Zasadniczo istnieją dwa punkty chmurowe (pierwotna chmura punktów i chmura punktów centrów komórek), ale informacje o geometrii komórki (obwiednia) mogą być przydatne, nie jestem pewien.

Wyniki

Zadałem trochę pytań i przeszukałem literaturę:

jeśli siatka jest sześciokątna i nieustrukturyzowana, problem zostaje zredukowany do wyszukiwania zakresu ortogonalnego. W tym celu najczęściej stosuje się drzewa KD. Jeśli siatka jest udoskonalona w oparciu o strukturę danych o liczbie oktetów, wokół niej można zbudować algorytm wyszukiwania zakresu. Celem jest uniknięcie zajmowania się bezpośrednią geometrią siatki i skoncentrowanie się na chmurze punktów A - relacja chmury punktów B. Chmura punktów A: punkty zapytania, chmura punktów B: centra komórek siatki.

tmaric
źródło
Czy możesz wyjaśnić, co masz na myśli mówiąc „sortuj według (dowolnego rodzaju) siatki”? Szukasz algorytmu binowania (ile punktów jest w każdej komórce)?
Szabolcs
Nie do końca rozumiem twoje pytanie, jaki jest cel sortowania punktów? Czy chcesz, aby siatka była bardziej regularna?
Shuhao Cao
Oddzielna chmura punktów jest rozproszona w nieustrukturyzowanej siatce objętości. Muszę przekazywać dane z centrów komórkowych do chmury punktów i odwrotnie.
tmaric
1
@ tomislav-maric: Czy możesz napisać swoje rozwiązanie jako odpowiedź, a następnie zaakceptować własną odpowiedź? Ta procedura jest ogólnie przyjętą praktyką skutecznego odpowiadania na twoje pytanie, zamiast dodawania do pytania znacznika „[ROZWIĄZANO]”; zapewni ci też lepszą reputację, ponieważ ludzie mogą głosować za twoją odpowiedzią.
Geoff Oxberry

Odpowiedzi:

8

Ważna uwaga: ta odpowiedź nie odpowiada na rzeczywiste pytanie, ale nie została usunięta na żądanie. Zawstydzająco pomyliłem sześciokąt i sześciokąt. Pytanie dotyczy sortowania punktów do dowolnych komórek heksaedrycznych w 3D, podczas gdy to rozwiązanie sortuje punkty do regularnych komórek heksagonalnych w 2D lub nieregularnych, które odpowiadają pewnej teselacji Voronoi w dowolnym wymiarze. Ta metoda ma zastosowanie tylko wtedy, gdy siatka została wygenerowana jako teselacja Voronoi w pierwszej kolejności (co wydaje się być podejściem sporadycznym ).


Nie jestem pewien, co masz na myśli przez sortowanie tutaj, ale zakładam, że chcesz posortować punkt w sześciokątne pojemniki na płaszczyźnie.

Mathematica jest tym, co wiem, więc pokażę ci, jak to zrobić w Mathematica, ale metodę można przenieść na inne systemy. Chodzi o to, że sieć sześciokątna jest podwójna z trójkątną: może być wygenerowana jako schemat Voronoi punktów w układzie trójkątnym. Punkt z chmury należy do danego sześciokąta, jeśli znajduje się bliżej środka tego sześciokąta niż do środka dowolnego innego sześciokąta.

Ta metoda będzie działać również w przypadku siatek o różnych kształtach, o ile można je wygenerować jako diagram Voronoi o pewnym układzie punktów. (Np. Sześciokąty nie muszą być regularne.)


Wygenerujmy siatkę. To jest trójkątna sieć:

pts = Join @@ Table[{x, Sqrt[3] y}, {x, 0, 4}, {y, 0, 2}];

points = Join[pts, TranslationTransform[{1/2, Sqrt[3]/2}] /@ pts];

Needs["ComputationalGeometry`"]
PlanarGraphPlot[points, LabelPoints -> False]

Grafika matematyczna

Jego podwójny jest sześciokątny, którym jesteśmy zainteresowani:

DiagramPlot[points, LabelPoints -> False]

Grafika matematyczna

To buduje funkcję, nfktóra znajduje indeks środka sześciokąta, do którego najbliższy punkt chmurowy. Jest to klucz do metody:

nf = Nearest[N[points] -> Range@Length[points]];

Teraz wygenerujemy chmurę 1000 losowych punktów i posortujemy je nf:

cloud = RandomReal[{-1/2, 5}, {1000, 2}];

indices = First /@ nf /@ cloud;

indiceszawiera wskaźniki centrów, do których każdy punkt chmurowy jest najbliżej. To jest informacja, której potrzebujemy. Teraz możemy zrobić z nich histogram ...

Histogram[indices]

Grafika matematyczna

... lub pokoloruj każdego z nich ...

Show[
 DiagramPlot[points, LabelPoints -> False],
 Graphics@MapThread[{ColorData[3][#1], Point[#2]} &, {indices, cloud}],
 PlotRange -> All, AspectRatio -> Automatic
 ]

Grafika matematyczna

... lub wykonaj dowolną fantazyjną wizualizację.

tally = Tally[indices];

ListDensityPlot[Join[points, List /@ Sort[tally][[All, 2]], 2], 
 InterpolationOrder -> 0, 
 Epilog -> (Text[#2, points[[#1]]] & @@@ tally), 
 PlotRange -> {{-.5, 5}, {-.5, 5}}, Mesh -> All, 
 ColorFunction -> (ColorData["BeachColors"][1 - #] &)]

Grafika matematyczna


Kluczowym punktem tutaj była funkcja, która znajduje najbliższy punkt do czegoś ( Nearest). Mathematica ma to wbudowane, ale istnieje szansa, że ​​Twój system tego nie zrobi. W takim przypadku zapoznaj się z tym pytaniem, jak skutecznie wdrożyć taką funkcję (lub po prostu zastosuj naiwną liniową implementację czasu, jeśli nie masz dużej liczby punktów do przetworzenia).

Szabolcs
źródło
Wielkie dzięki! Zasadniczo potrzebuję relacji, która pokazuje połączenie między każdym punktem a „bin”, jak go nazwałeś (trójwymiarowe sześciokątne pudełko). To, co sugerujesz, wydaje się bardzo interesujące, ale mam do czynienia z siatkami milionów pudełek i potencjalnie setkami tysięcy punktów. Pytanie brzmi: co kosztuje więcej: tworzenie podwójnej siatki lub praca z ramkami granicznymi „pojemników” i używanie kd drzewo do wyszukiwania. Jestem bardzo nowy w tym temacie, więc naprawdę nie chcę iść w złym kierunku.
tmaric
k
Nie usuwaj go zdecydowanie, ktoś może uznać to za przydatne! :) Może to okazać się rozwiązaniem problemu, po prostu nie mogę go jeszcze zaakceptować, dopóki o nim nie przeczytam.
tmaric
I dziękuję za tak szczegółową odpowiedź, gdybym mógł, dałbym wam więcej punktów! :)
tmaric
@ tomislav-maric Patrząc na głosy, martwię się, że moja odpowiedź zmniejszy szansę na uzyskanie użytecznej lub przyczyni się do nieporozumień. Myślę, że to bardziej produktywne, jeśli usunę.
Szabolcs