Trier un nuage de points par rapport à un maillage non structuré de cellules hexaédriques

Question

Comment classeriez-vous un nuage de points par rapport à un maillage non structuré de cellules hexaédriques?

Chaque cellule a un centre et une étiquette unique pour la représenter. Il y a essentiellement deux points de nuage (nuage de points d'origine et un nuage de points des centres cellulaires), mais les informations sur la géométrie des cellules (boîte englobante) peuvent être utiles, je ne suis pas sûr.

Résultats

J'ai fait quelques recherches et recherches dans la littérature:

si le maillage est hexaédrique et non structuré, le problème est réduit à une recherche de plage orthogonale. À cette fin, les arbres kd sont le plus souvent utilisés. Si le maillage est affiné sur la base d'une structure de données octree, l'algorithme de recherche de plage peut être construit autour de lui. Le but est d'éviter de traiter de la géométrie directe du maillage et de se concentrer sur la relation nuage de points A - nuage de points B. Nuage de points A: points de requête, nuage de points B: centres de cellules de maillage.

Remarque importante: cette réponse ne répond pas à la question réelle, mais elle n'a pas été supprimée par demande. Gênant, j'ai confondu hexaédrique et hexagonal. La question concerne le tri des points dans des cellules hexaédriques arbitraires en 3D, tandis que cette solution trie les points dans des cellules hexagonales régulières en 2D ou irrégulières qui correspondent à une tesselation de Voronoï dans n'importe quelle dimension. Cette méthode n'est applicable que si le maillage a été généré en tant que tesselation de Voronoï en premier lieu (ce qui semble être une approche parfois utilisée ).

Je ne suis pas sûr de ce que vous entendez par tri ici, mais je suppose que vous voulez trier le point en bacs hexagonaux dans l'avion.

Mathematica est ce que je sais, donc je vais vous montrer comment le faire dans Mathematica, mais la méthode peut être portée sur d'autres systèmes. L'idée est qu'un réseau hexagonal est le double d'un réseau triangulaire: il peut être généré comme le diagramme de Voronoi d'un point en disposition triangulaire. Un point du nuage appartient à un hexagone donné s'il est plus proche du centre de cet hexagone que du centre de tout autre hexagone.

Cette méthode fonctionnera également pour les maillages de formes différentes, à condition qu'ils puissent être générés comme le diagramme de Voronoi d'une disposition de points. (Par exemple, les hexagones n'ont pas besoin d'être réguliers.)

Générons le maillage. Ceci est un réseau triangulaire:

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]

Son double est celui hexagonal qui nous intéresse:

DiagramPlot[points, LabelPoints -> False]

Cela crée une fonction nfqui trouve l'index du centre de l'hexagone dont un point de nuage est le plus proche. C'est la clé de la méthode:

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

Générons maintenant un nuage de 1000 points aléatoires et trions-les avec nf:

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

indices = First /@ nf /@ cloud;

indicescontient les indices des centres dont chaque point de nuage est le plus proche. Ce sont les informations dont nous avions besoin. Nous pouvons maintenant en faire un histogramme ...

Histogram[indices]

... ou coloriez chacun d'eux ...

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

... ou faites toute sorte de visualisation de fantaisie que nous voulons.

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

Le point clé ici était la fonction qui trouve le point le plus proche de quelque chose ( Nearest). Mathematica a cela intégré, mais il est possible que votre système ne le fasse pas. Si tel est le cas, veuillez consulter cette question sur la façon d'implémenter efficacement une telle fonction (ou tout simplement aller avec l'implémentation de temps linéaire naïf si vous n'avez pas une énorme quantité de points à traiter).