Testando se um tetraedro está dentro de um poliedro

15

Eu tenho um tetraedro e um poliedro p . t é restringido de forma que sempre compartilhe todos os seus vértices com p . Quero determinar se t está dentro de p .t ptpt p

Gostaria de acrescentar um detalhe ao problema, caso ele possa contribuir para a solução: é um tetraedro de Delaunay e as faces de p são triangulares e são fortemente Delaunay, ambas em relação aos vértices de p . Um tetraedro é Delaunay se a circunsfera de seus vértices não contiver outro vértice dentro dele. Uma face é fortemente Delaunay se existe uma circumsphere contendo vértices desse cara na sua superfície, mas nenhum outro vértice em ou dentro dela.tpp

As figuras a seguir mostram o mesmo problema no espaço : 2D

O polígono original p :

insira a descrição da imagem aqui

Triangulação de Delaunay dos vértices de p :

insira a descrição da imagem aqui

Resultado do teste interno / externo dos triângulos t (os triângulos sombreados estão dentro de e o resto está fora ):p

insira a descrição da imagem aqui

Resultado desejado (poda de triângulos externos ) :

insira a descrição da imagem aqui


Meu problema original está no espaço 3D, então os triângulos nas figuras acima se traduzem em tetraedros e o polígono p se traduz em um poliedro arbitrário p . Eu descobri algumas formulações desse problema:tpp

Formulação 1
As únicas partes de que podem estar fora de p são suas bordas e faces triangulares, mas em geral pode existir um p que tenha bordas de todos os t 's externos em sua superfície; portanto, alternativamente, esse problema também pode ser formulado como testar se para um tetraedro t existe uma face que se encontra fora de p ?tpp tt p

Formulação 2
Tenho outra perspectiva possível em relação a esse problema, mas sem qualquer idéia formal:
Geometricamente, se estiver do lado de fora, ele sempre ficará grudado na superfície externa de p . Portanto, se pudermos calcular os contornos (informalmente, o limite externo) C V e C V p de modo que V = V tV p e V t , V p sejam conjuntos de vértices em t , p respectivamente, então CtpCVCVpV=VtVpVt,Vpt,p ssetmentiras dentrop. CV=CVp tp

Eu gostaria de saber:

  • Como posso resolver a Formulação 1 ou a Formulação 2 ?
  • Ou existe alguma abordagem completamente diferente para resolver isso?

Atualização:
Agora percebo que esse problema pode ser reduzido a ponto no problema do poliedro . Como um tetraedro externo terá pelo menos uma face que fica fora de p , então qualquer ponto arbitrário nessa face (exceto seus vértices, em geral) sempre estará fora de p . Portanto, para cada face de t , preciso tomar um ponto arbitrário e testar se esse ponto está fora de p .tp pt p

A partir do ponto no artigo de polígono, eu vim a conhecer o algoritmo de fundição de Ray e o algoritmo de número de enrolamento . A projeção de raios não é numericamente estável nos casos em que o ponto está na superfície de . Mas a robustez numérica do algoritmo de número de enrolamento não foi abordada lá. p

Com base no exposto, meu problema principal agora parece ser (sugira se for feito como uma pergunta separada):
Existe algum algoritmo numericamente robusto para apontar no problema de polígono ?

Pranav
fonte
Só para esclarecer: 1) Pode o poliedro ser não-convexo, e 2) se t e p compartilham uma face ou uma aresta (ou parte dela), faz que desqualificamptp de estar "dentro" de p ? (Obviamente, com base em suas necessidades, t e p deve ser permitido vértices ações.)tptp
Ilmari Karonen
tptp
11
p
11
a não-convexidade tem a estranheza de que todos os vértices podem estar dentro do poliedro e, no entanto, o tetraedro pode estar fora (uma vez que uma aresta não precisa estar no interior como um todo). Algoritmo possível, ver se bordas (entre poliedro e tetraedro) pode ter cruzamentos => prov que mentiras tetraedro fora é grande
Nikos M.
11
Você viu o algoritmo de distância Gilbert – Johnson – Keerthi? Você precisaria decompor o polígono / poliedro em formas convexas primeiro (como você observou, um complexo simples faria o trabalho). Sabe-se que o GJK é muito estável e muito rápido.
Pseudônimo

Respostas:

2

Recentemente, encontrei uma solução para esse problema em um artigo 'Segmentação robusta de dentro para fora usando números de enrolamento generalizados' de Alec Jacobson et al., Aqui . Ele resolve o problema de localizar se um ponto está dentro (ou fora) de uma malha poligonal arbitrária (com interseções automáticas, não manifold, superfícies abertas etc.) usando a noção de número de enrolamento generalizado .

tp

Pranav
fonte
ptpptppttp