Classifique uma nuvem de pontos em relação a uma malha não estruturada de células hexaédricas

11

Questão

Como você classificaria uma nuvem de pontos em relação a uma malha não estruturada de células hexaédricas?

Cada célula possui um centro e um rótulo exclusivo para representá-lo. Existem basicamente dois pontos de nuvem (nuvem de pontos original e uma nuvem de pontos dos centros celulares), mas as informações da geometria da célula (caixa delimitadora) podem ser úteis, não tenho certeza.

Resultados

Eu fiz algumas perguntas e pesquisando na literatura:

se a malha é hexaédrica e não estruturada, o problema é reduzido a uma pesquisa de faixa ortogonal. Para esse fim, as árvores kd são usadas com mais frequência. Se a malha é refinada com base em uma estrutura de dados octree, o algoritmo de pesquisa por intervalo pode ser construído em torno dela. O objetivo é evitar lidar com a geometria direta da malha e se concentrar no relacionamento A da nuvem de pontos A da nuvem de pontos B. Nuvem de pontos A: pontos de consulta, nuvem de pontos B: centros de células de malha.

tmaric
fonte
Você pode esclarecer o que você quer dizer quando diz "classificar com relação a (qualquer tipo de) malha"? Você está procurando um algoritmo de binning (quantos pontos existem em cada célula)?
Szabolcs
Não entendo bem sua pergunta, qual é o objetivo de classificar os pontos? Como tornar a malha mais regular?
Shuhao Cao
Há uma nuvem de pontos separada espalhada pela malha de volume não estruturada. Preciso comunicar dados dos centros celulares para a nuvem de pontos e vice-versa.
tmaric
1
@ tomislav-maric: Você poderia escrever sua solução como resposta e aceitar sua própria resposta? Esse procedimento geralmente é a prática aceita para responder sua própria pergunta de maneira eficaz, em vez de adicionar a tag "[RESOLVIDO]" à pergunta; Além disso, você ganhará mais reputação, porque as pessoas podem aprovar sua resposta.
Geoff Oxberry

Respostas:

8

Nota importante: Esta resposta não responde à pergunta real, mas foi deixada de ser anulada por solicitação. Embaraçosamente, confundi hexaédrico e hexagonal. A pergunta é sobre a classificação de pontos em células hexaédricas arbitrárias em 3D, enquanto essa solução classifica pontos em células hexagonais regulares em 2D, ou irregulares que correspondem a algum mosaico de Voronoi em qualquer dimensão. Este método é aplicável apenas se a malha foi gerada como um mosaico de Voronoi em primeiro lugar (o que parece ser uma abordagem usada ocasionalmente ).


Não sei ao certo o que você quer dizer com classificação aqui, mas presumo que você queira classificar o ponto em caixas hexagonais no avião.

O Mathematica é o que eu sei, então vou mostrar como fazer no Mathematica, mas o método pode ser portado para outros sistemas. A idéia é que uma rede hexagonal seja o dual de uma triangular: ela pode ser gerada como o diagrama de Voronoi de um ponto em arranjo triangular. Um ponto da nuvem pertence a um dado hexágono se estiver mais próximo do centro desse hexágono do que do centro de qualquer outro hexágono.

Este método também funcionará para malhas de diferentes formas, desde que possam ser geradas como o diagrama de Voronoi de algum arranjo de pontos. (Por exemplo, os hexágonos não precisam ser regulares.)


Vamos gerar a malha. Esta é uma estrutura 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]

Gráficos do Mathematica

Seu dual é o hexagonal em que estamos interessados:

DiagramPlot[points, LabelPoints -> False]

Gráficos do Mathematica

Isso cria uma função nfque encontra o índice do centro do hexágono ao qual algum ponto da nuvem está mais próximo. É a chave do método:

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

Agora vamos gerar uma nuvem de 1000 pontos aleatórios e classificá-los com nf:

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

indices = First /@ nf /@ cloud;

indicescontém os índices dos centros aos quais cada ponto da nuvem está mais próximo. Esta é a informação que precisávamos. Agora podemos fazer um histograma com eles ...

Histogram[indices]

Gráficos do Mathematica

... ou colorir cada um deles ...

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

Gráficos do Mathematica

... ou qualquer tipo de visualização sofisticada que desejamos.

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

Gráficos do Mathematica


O ponto principal aqui foi a função que encontra o ponto mais próximo de algo ( Nearest). O Mathematica possui isso, mas há uma chance de seu sistema não. Se for esse o caso, consulte esta pergunta sobre como implementar eficientemente essa função (ou apenas siga a ingênua implementação de tempo linear se você não tiver uma quantidade enorme de pontos a serem processados).

Szabolcs
fonte
Muito obrigado! Basicamente, o que eu preciso é de um relacionamento que mostre uma conexão entre cada ponto e um "bin" como você o chamou (caixa hexaédrica tridimensional). O que você sugere parece muito interessante, mas estou lidando com malhas de milhões de caixas e centenas de milhares de pontos potencialmente. A questão é o que custa mais: criação de malha dupla ou trabalho com caixas delimitadoras das "caixas" e usando um kd árvore para pesquisar. Sou muito novo neste tópico, então realmente não quero ir na direção errada.
tmaric
k
Não o exclua definitivamente, alguém pode achar útil! :) Pode parecer uma solução para o problema, mas ainda não posso aceitá-lo até ler sobre ele.
tmaric
E obrigado por uma resposta tão detalhada, se eu pudesse, daria mais pontos! :)
tmaric
@ tomislav-maric Olhando para os votos, estou preocupado que minha resposta diminua a chance de você ser útil, ou contribua para o mal-entendido. Eu acho que é mais produtivo se eu excluir.
Szabolcs