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.

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]

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

DiagramPlot[points, LabelPoints -> False]

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]

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

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

... 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 - #] &)]

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).