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

11

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.

tmaric
la source
Pouvez-vous préciser ce que vous voulez dire lorsque vous dites "trier par rapport à (tout type de) maillage"? Recherchez-vous un algorithme de binning (combien de points y a-t-il dans chaque cellule)?
Szabolcs
Je ne comprends pas très bien votre question, quel est le but du tri des points? Vous aimez rendre le maillage plus régulier?
Shuhao Cao
Il y a un nuage de points séparé dispersé à travers le maillage de volume non structuré. J'ai besoin de communiquer les données des centres cellulaires au nuage de points et vice versa.
tmaric
1
@ tomislav-maric: Pourriez-vous s'il vous plaît écrire votre solution comme réponse, puis accepter votre propre réponse? Cette procédure est généralement la pratique acceptée pour répondre efficacement à votre propre question, plutôt que d'ajouter la balise "[RESOLU]" à la question; aussi, cela vous fera gagner plus de réputation, car les gens peuvent voter pour votre réponse.
Geoff Oxberry

Réponses:

8

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]

Graphiques Mathematica

Son double est celui hexagonal qui nous intéresse:

DiagramPlot[points, LabelPoints -> False]

Graphiques Mathematica

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]

Graphiques Mathematica

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

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

Graphiques Mathematica

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

Graphiques Mathematica


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

Szabolcs
la source
Merci beaucoup! Fondamentalement, ce dont j'ai besoin est une relation qui montre une connexion entre chaque point et un "bac" comme vous l'avez appelé (boîte hexaédrique tridimensionnelle). Ce que vous suggérez semble très intéressant, mais j'ai affaire à des mailles de millions de boîtes et de centaines de milliers de points potentiellement. arbre de recherche. Je suis très nouveau sur ce sujet, donc je ne veux vraiment pas aller dans la mauvaise direction.
tmaric
k
Ne le supprimez pas définitivement, quelqu'un pourrait le trouver utile! :) Cela peut tourner la moue pour être la solution au problème, c'est juste que je ne peux pas encore l'accepter jusqu'à ce que je le lise.
tmaric
Et merci pour une réponse aussi détaillée, si je pouvais, je vous donnerais plus de points! :)
tmaric
@ tomislav-maric En regardant les votes, je crains que ma réponse ne diminue les chances que vous en obteniez une utile, ou qu'elle contribue au malentendu. Je pense que c'est plus productif si je supprime.
Szabolcs