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

11

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.

tmaric
quelle
Können Sie klarstellen, was Sie meinen, wenn Sie "Sortieren in Bezug auf (jede Art von) Netz" sagen? Suchen Sie nach einem Binning-Algorithmus (wie viele Punkte befinden sich in jeder Zelle)?
Szabolcs
Ich verstehe Ihre Frage nicht ganz klar, was ist das Ziel, die Punkte zu sortieren? Möchten Sie das Netz regelmäßiger machen?
Shuhao Cao
Es gibt eine separate Punktwolke, die über das unstrukturierte Volumennetz verstreut ist. Ich muss Daten von den Zellzentren an die Punktwolke und umgekehrt übertragen.
Tmaric
1
@ tomislav-maric: Könnten Sie bitte Ihre Lösung als Antwort schreiben und dann Ihre eigene Antwort akzeptieren? Dieses Verfahren ist im Allgemeinen die akzeptierte Praxis, um Ihre eigene Frage effektiv zu beantworten, anstatt der Frage das Tag "[SOLVED]" hinzuzufügen. Außerdem wird es Ihnen mehr Ansehen einbringen, weil die Leute Ihre Antwort positiv bewerten können.
Geoff Oxberry

Antworten:

8

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]

Mathematica-Grafiken

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

DiagramPlot[points, LabelPoints -> False]

Mathematica-Grafiken

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]

Mathematica-Grafiken

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

Mathematica-Grafiken

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

Mathematica-Grafiken


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

Szabolcs
quelle
Danke vielmals! Grundsätzlich brauche ich eine Beziehung, die eine Verbindung zwischen jedem Punkt und einem "Bin" zeigt, wie Sie es genannt haben (3-dimensionale hexaedrische Box). Was Sie vorschlagen, scheint sehr interessant zu sein, aber ich habe es möglicherweise mit Maschen von Millionen von Boxen und Hunderttausenden von Punkten zu tun. Die Frage ist, was mehr kostet: Dual-Mesh-Erstellung oder Arbeiten mit Begrenzungsboxen der "Bins" und Verwenden eines kd Baum zum Suchen. Ich bin sehr neu in diesem Thema, also möchte ich wirklich nicht in die falsche Richtung gehen.
Tmaric
k
Löschen Sie es nicht definitiv, jemand könnte es nützlich finden! :) Es könnte sich herausstellen, dass Schmollmund die Lösung für das Problem ist. Ich kann es nur noch nicht akzeptieren, bis ich darüber gelesen habe.
Tmaric
Und danke für eine so ausführliche Antwort, wenn ich könnte, würde ich Ihnen mehr Punkte geben! :)
Tmaric
@ tomislav-maric Wenn ich mir die Stimmen ansehe, mache ich mir Sorgen, dass meine Antwort die Wahrscheinlichkeit verringert, dass Sie eine nützliche erhalten, oder zum Missverständnis beiträgt. Ich denke, es ist produktiver, wenn ich lösche.
Szabolcs