Sortieren Sie eine Punktwolke in Bezug auf ein unstrukturiertes Netz hexaedrischer Zellen

Frage

Wie würden Sie eine Punktwolke in Bezug auf ein unstrukturiertes Netz hexaedrischer Zellen sortieren?

Jede Zelle hat ein Zentrum und eine eindeutige Bezeichnung, um sie darzustellen. Grundsätzlich gibt es zwei Trübungspunkte (ursprüngliche Punktwolke und eine Punktwolke der Zellzentren), aber die Informationen zur Zellgeometrie (Begrenzungsrahmen) können von Nutzen sein, da bin ich mir nicht sicher.

Ergebnisse

Ich habe ein bisschen nachgefragt und die Literatur durchsucht:

Wenn das Netz hexaedrisch und unstrukturiert ist, wird das Problem auf eine orthogonale Bereichssuche reduziert. Zu diesem Zweck werden am häufigsten kd-Bäume verwendet. Wenn das Netz basierend auf einer Octree-Datenstruktur verfeinert wird, kann der Bereichssuchalgorithmus darum herum aufgebaut werden. Ziel ist es, den Umgang mit der direkten Netzgeometrie zu vermeiden und sich auf die Beziehung zwischen Punktwolke A und Punktwolke B zu konzentrieren. Punktwolke A: Abfragepunkte, Punktwolke B: Netzzellzentren.

Wichtiger Hinweis: Diese Antwort beantwortet nicht die eigentliche Frage, wurde jedoch pro Anfrage nicht gelöscht. Peinlicherweise habe ich hexaedrisch und sechseckig verwechselt. Die Frage besteht darin, Punkte in 3D in beliebige hexaedrische Zellen zu sortieren, während diese Lösung Punkte in 2D in reguläre hexagonale Zellen oder in unregelmäßige Zellen sortiert, die einer Voronoi-Tesselation in einer beliebigen Dimension entsprechen. Diese Methode ist nur anwendbar, wenn das Netz in erster Linie als Voronoi-Tesselation erzeugt wurde (was ein gelegentlich verwendeter Ansatz zu sein scheint ).

Ich bin mir nicht sicher, was Sie hier unter Sortieren verstehen, aber ich gehe davon aus, dass Sie den Punkt in sechseckigen Behältern im Flugzeug sortieren möchten.

Mathematica ist das, was ich weiß, daher werde ich Ihnen zeigen, wie es in Mathematica gemacht wird, aber die Methode kann auf andere Systeme portiert werden. Die Idee ist, dass ein hexagonales Gitter das Dual eines dreieckigen ist: Es kann als Voronoi-Diagramm eines Punktes in dreieckiger Anordnung erzeugt werden. Ein Punkt aus der Wolke gehört zu einem bestimmten Sechseck, wenn er näher an der Mitte dieses Sechsecks liegt als an der Mitte eines anderen Sechsecks.

Diese Methode funktioniert auch für Netze unterschiedlicher Form, sofern sie als Voronoi-Diagramm einer Punktanordnung generiert werden können. (ZB müssen die Sechsecke nicht regelmäßig sein.)

Lassen Sie uns das Netz erzeugen. Dies ist ein Dreiecksgitter:

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]

Sein Dual ist das sechseckige, an dem wir interessiert sind:

DiagramPlot[points, LabelPoints -> False]

Dadurch wird eine Funktion erstellt, nfdie den Index des Sechseckzentrums ermittelt, dem ein Trübungspunkt am nächsten liegt. Es ist der Schlüssel zur Methode:

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

Jetzt generieren wir eine Wolke aus 1000 zufälligen Punkten und sortieren sie mit nf:

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

indices = First /@ nf /@ cloud;

indicesenthält die Indizes der Zentren, denen jeder Trübungspunkt am nächsten liegt. Dies sind die Informationen, die wir brauchten. Jetzt können wir daraus ein Histogramm machen ...

Histogram[indices]

... oder färben Sie jeden von ihnen ...

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

... oder machen Sie irgendeine Art von ausgefallener Visualisierung, die wir wollen.

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

Der Schlüsselpunkt hier war die Funktion, die den nächsten Punkt zu etwas findet ( Nearest). Mathematica hat dies eingebaut, aber es besteht die Möglichkeit, dass Ihr System dies nicht tut. Wenn dies der Fall ist, lesen Sie bitte diese Frage , wie Sie eine solche Funktion effizient implementieren können (oder gehen Sie einfach zur naiven linearen Zeitimplementierung, wenn Sie nicht viele Punkte zu verarbeiten haben).