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

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.

algorithms computational-geometry

— 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

@ 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

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

$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