Provavelmente todo mundo conhece esse algoritmo, mas "as autoridades estavam se escondendo de mim". Encontrei a descrição verbal dele na terceira página do mecanismo de busca no arquivo de traduções automáticas do fórum em inglês. Parece-me que sua descrição detalhada (e com o código) é digna de habrosta.
Assim, por exemplo, você precisa gerar multidões para um brinquedo e em algum lugar do processo para eliminar aqueles que não estão de pé. Para fazer isso, você precisa encontrar o centro de massa da multidão (e isso é quase o mesmo que encontrar seu volume) e garantir que esteja em algum lugar acima das pernas da multidão.
Uma multidão é um poliedro, por simplicidade, acreditamos que um poliedro consiste apenas de triângulos (o algoritmo contém a
fórmula da área gaussiana dentro, para que você possa expandi-lo para qualquer poliedro, mas por que ...). Além disso, o poliedro não deve ter auto-interseções e limitar o volume fechado, como convém aos poliedros decentes.
(bem, assim)Uma pequena UPD explicando por que, no KDPV, o mob certo não está OK, mas o esquerdo está OK:
A imagem certa não está boa porque a multidão cairá para a frente, porque seu centro de massa é estendido além da área de apoio. A área de suporte de um polígono em pé na superfície é definida como o polígono mínimo dentro do qual todos os pontos da superfície estão localizados. No caso esquerdo, a área do suporte é deslocada para o centro de massa e mais (porque as patas dos dinossauros são maiores) e, na figura à direita, a área em si é menor e mais próxima da cauda.
A proporção da área de referência para o centro de massa será mais ou menos assim:
Começarei imediatamente com o código de pesquisa de volume (Python, input - uma lista de pontos e uma matriz de transição):
algum códigodef RecSetDirsTriangles(para, Connects, TR): """ , """
A essência do algoritmo é considerar os volumes de figuras que formam as faces do poliedro que “caem” no plano xy. Para fazer isso, você precisa conhecer a área de projeção do triângulo e o sinal com o qual adicionar o volume da figura (prisma truncado). De fato, se os triângulos são ordenados com antecedência, o volume e o sinal são reduzidos a um único cálculo.
Portanto, a primeira coisa que uma função recursiva coleta triângulos é a entrada. Ele é coletado de maneira que, ao olhar “de fora” para o poliedro, as direções para girar os triângulos são as mesmas (idealmente no sentido anti-horário; se você seguir as direções no sentido horário, o resultado será correto, mas negativo - portanto, o módulo de volume é dado ao retorno).
Isso é muito simples de conseguir - pegue um triângulo (pontos a1, a2, a3), procure seus vizinhos e liste dois vértices correspondentes na ordem inversa (por exemplo, assim: a2, a1, b1).
Acontece algo como isto:
Agora, se projetarmos esse triângulo no plano xy, a ordem de deslocamento para a projeção do triângulo "superior" será a mesma que a originalmente selecionada, e a ordem de deslocamento para a projeção do triângulo "inferior" mudará de direção. Como resultado, ele alterará o sinal e a área desse triângulo, calculados pela fórmula de Gauss. Aqui, o triângulo "inferior" - um conceito condicional - significa que o volume imediatamente abaixo dele não é incluído no volume do poliedro. O triângulo “inferior” de um poliedro não convexo pode ser maior que o triângulo “superior”.
Após essas etapas preliminares, para calcular o volume total do poliedro, basta adicionar (levando em conta o sinal, que é obtido “por si só”) todos os volumes dos prismas truncados coletados das faces e projeções dessas faces no plano xy. E os volumes de prismas são considerados como o produto da área (gaussiana, com um sinal) e as coordenadas z aritméticas médias dos vértices do triângulo.
Se o poliedro cruzar o plano xy, ao calcular o volume, todos os sinais serão cancelados e o resultado permanecerá correto (você só precisa medir a altura do prisma sem um módulo).
(de alguma forma, o prisma truncado "superior" se parece)Com a busca pelo centro de massa, tudo é aproximadamente o mesmo. Da mesma forma, precisamos encontrar os centros de massa para cada prisma truncado e resumir as coordenadas, multiplicando pelo volume do prisma (presume-se que a massa seja distribuída uniformemente por todo o volume e que um possa ser substituído por outro). Para encontrar o centro de massa de um prisma truncado, é necessário calcular os centros de massa de dois tetraedros (função +1) e um prisma comum. O algoritmo também "não se deteriora" se o poliedro cruzar o plano xy (e aqui pode ser uma reprodução de Magritte).
(esses dois tetraedros, marcados em vermelho e vermelho, juntamente com um prisma triangular (abaixo do tetraedro vermelho) formam o prisma truncado desejado. Precisamos encontrar os centros de massa e volumes das três figuras. As designações correspondem aproximadamente às designações no código)Código que conta isso e aquilo:
um pouco mais de código def RecSetDirsTriangles(para, Connects, TR):
Uma parte do algoritmo em que as direções dos triângulos são consideradas e usadas para entender o volume externo e interno é um movimento muito forte, pois pode ser usado bastante quando você trabalha com poliedros. Por exemplo, se você precisar calcular a direção dos normais "fora" - basta saber a direção "anti-horário" para uma face - e pronto!
(adivinhe o filme!)