Ordenar una nube de puntos con respecto a una malla no estructurada de células hexaédricas

Pregunta

¿Cómo ordenaría una nube de puntos con respecto a una malla no estructurada de células hexaédricas?

Cada celda tiene un centro y una etiqueta única para representarlo. Básicamente, hay dos puntos de nube (nube de puntos original y una nube de puntos de los centros celulares), pero la información de geometría celular (cuadro delimitador) puede ser útil, no estoy seguro.

Resultados

He hecho algunas preguntas y busqué en la literatura:

Si la malla es hexaédrica y no estructurada, el problema se reduce a una búsqueda de rango ortogonal. Para este propósito, los árboles kd se usan con mayor frecuencia. Si la malla se refina en base a una estructura de datos de octree, el algoritmo de búsqueda de rango se puede construir a su alrededor. El objetivo es evitar tratar con la geometría de malla directa y concentrarse en la nube de puntos A - relación de la nube de puntos B. Nube de puntos A: puntos de consulta, nube de puntos B: centros de celdas de malla.

Nota importante: esta respuesta no responde la pregunta real, pero se dejó sin recuperar por solicitud. Vergonzosamente confundí hexaédrica y hexagonal. La pregunta es sobre la clasificación de puntos en celdas hexaédricas arbitrarias en 3D, mientras que esta solución clasifica los puntos en celdas hexagonales regulares en 2D o irregulares que corresponden a alguna teselación de Voronoi en cualquier dimensión. Este método es aplicable solo si la malla se generó como una teselación de Voronoi en primer lugar (lo que parece ser un enfoque utilizado ocasionalmente ).

No estoy seguro de qué quieres decir con ordenar aquí, pero supongo que quieres ordenar el punto en contenedores hexagonales en el avión.

Mathematica es lo que sé, por lo que le mostraré cómo hacerlo en Mathematica, pero el método se puede transferir a otros sistemas. La idea es que una red hexagonal es la dual de una triangular: se puede generar como el diagrama de Voronoi de puntos en disposición triangular. Un punto de la nube pertenece a un hexágono dado si está más cerca del centro de ese hexágono que del centro de cualquier otro hexágono.

Este método también funcionará para mallas de diferentes formas, siempre que se puedan generar como el diagrama de Voronoi de algún arreglo de puntos. (Por ejemplo, los hexágonos no necesitan ser regulares).

Generemos la malla. Esta es una red triangular:

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]

Su dual es el hexagonal que nos interesa:

DiagramPlot[points, LabelPoints -> False]

Esto crea una función nfque encuentra el índice del centro del hexágono al que algún punto de la nube está más cercano. Es la clave del método:

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

Ahora generemos una nube de 1000 puntos aleatorios y ordénelos con nf:

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

indices = First /@ nf /@ cloud;

indicescontiene los índices de los centros a los que cada punto de nube está más cercano. Esta es la información que necesitábamos. Ahora podemos hacer un histograma con ellos ...

Histogram[indices]

... o colorear cada uno de ellos ...

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

... o hacer cualquier tipo de visualización elegante que queramos.

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

El punto clave aquí fue la función que encuentra el punto más cercano a algo ( Nearest). Mathematica tiene esto incorporado, pero existe la posibilidad de que su sistema no. Si este es el caso, vea esta pregunta sobre cómo implementar eficientemente dicha función (o simplemente siga con la ingenua implementación de tiempo lineal si no tiene una gran cantidad de puntos para procesar).