Trova tutti i punti con coordinate intere all'interno del tetraedro

Question

Sto cercando di trovare tutti i punti con le coordinate intere che si trovano all'interno di un tetraedro (voglio in qualche modo essere in grado di scorrere attraverso di loro). Conosco le coordinate dei quattro punti (A, B, C, D) che definiscono il tetraedro.

Quello che sto facendo attualmente è trovare il riquadro di delimitazione del tetraedro (minimo e massimo x, y, z coordinate di A, B, C, D) e quindi fare un ciclo attraverso tutti i punti all'interno del rettangolo di selezione. Per ogni punto, calcolo le coordinate baricentriche (usando the equations from Wikipedia) e controlla se il punto si trova all'interno del tetraedro (se una qualsiasi delle coordinate baricentriche è negativa o maggiore di 1, il punto non è all'interno).

C'è un modo migliore per farlo? Attualmente c'è circa 1/6 di possibilità che il punto che sto testando (dal riquadro di delimitazione) risieda davvero nel tetraedro, quindi penso di fare troppi calcoli inutili.

Sto lavorando con una lista di tetraedri che ho generato triangolando un volume più grande (sto espandendo il volume e voglio interpolare i valori mancanti usando l'interpolazione tetraedrica). Non sto usando nessuna libreria esterna.

Answer 1

Un'altra idea per migliorare:

controllo se un Parrallel "asta" per z (cioè x = 4, y = 6) attraversa il tetraedro. In caso contrario, nessun valore con (x = 4, y = 5, z) può essere all'interno.

Altrimenti, trova dove l'asta interseca il bordo del tetraedro (scoprendo dove si intersecano gli aerei che formano il bordo del tetraedro).

Dire che questi piani si intersecano a z = 1.3 ez = 10.04. Allora sai che tutti i punti (4,5, 2) a (4,5,10) sono all'interno.

Ripetere per tutti i valori di x e y.

Questo dovrebbe essere più veloce in pratica, perché consente di risparmiare 1 ciclo.

Answer 2

Il tuo approccio è quello giusto. Ci sono alcune ottimizzazioni possibili, che potrebbero valerne la pena o meno a seconda dei requisiti. Ad esempio:

Esiste un modo più semplice per verificare se un determinato punto si trova all'interno o all'esterno del tetraedro. Si tratta di controllare il semispazio a cui appartiene il punto rispetto a ciascuno dei 4 lati del tetraedro:

Ogni lato è definito da 3 punti (ad esempio A, B, C). Quindi un piano normale è un (C-A) x (B-A) (è un prodotto incrociato di vettori nel piano). Se queste coordinate sono (a, b, c), l'equazione del piano è F(x,y,z) = ax+by+cz = 0. Per un dato punto (x0, y0, z0) il segno di F (x0, y0, z0) determina a quale semipiano i punti appartengono.

Il punto è che è possibile precomporre le virgolette per ciascun lato del tetraedro e il segno che corrisponde a "esterno" e quindi il controllo per un dato punto equivale a eseguire al massimo 4 valutazioni (una per ciascun lato), ciascuno con 3 moltiplicazioni e 2 aggiunte.